Коды Грея — различия между версиями
(Основа) |
(Дополнение) |
||
| Строка 4: | Строка 4: | ||
== Алгоритм построения == | == Алгоритм построения == | ||
| − | Существует несколько | + | Существует несколько видов Кода Грея, самый простой из них - так называемый зеркальный двоичный Код Грея, строится он так: |
Для получения кода длины n производится n шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй - "1". Таким образом с каждым шагом длина векторов увеличивается на 1, и их количество вдвое. | Для получения кода длины n производится n шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй - "1". Таким образом с каждым шагом длина векторов увеличивается на 1, и их количество вдвое. | ||
Таким образом количество векторов длины n равно <math>2^n</math>. | Таким образом количество векторов длины n равно <math>2^n</math>. | ||
| + | |||
| + | '''Доказательсво правильности работы алгоритма''' | ||
| + | |||
| + | По индукции: | ||
| + | |||
| + | -на первом шаге код отвечеат условиям | ||
| + | |||
| + | -предположим, что получившийся код на шаге i есть Код Грея | ||
| + | |||
| + | -тогда на шаге i+1: первая половина кода будет корректна, так как она совпадает с кодом с шага i за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она явлеятся зеракальным отражением первой половины, только добавлена везде 1. На стыке: i бит совпадают в силу зеркальности, отличается последний. | ||
| + | Таким образом этот код - Код Грея. Индукционное предположение доказанно, алгоритм работает верно. | ||
| + | |||
| + | Этот алгоритм можно обобщить и для k-ичных векторов. | ||
| + | Сущестует ещё несколько видов Кода Грея - сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея. | ||
Версия 05:32, 12 ноября 2010
Код Грея - такое упорядочение k-ичных (обычно двоичных) векторов, что соседние вектора отличалются только в одном разряде. Код назван в честь Френка Грея, который в 1947 году получил патент на "отраженный двоичный код". Изначально он предназначался для избавления от паразитных состояний в электромеханических переключателях, однако сейчас область его применения гораздо шире.
Алгоритм построения
Существует несколько видов Кода Грея, самый простой из них - так называемый зеркальный двоичный Код Грея, строится он так: Для получения кода длины n производится n шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй - "1". Таким образом с каждым шагом длина векторов увеличивается на 1, и их количество вдвое. Таким образом количество векторов длины n равно .
Доказательсво правильности работы алгоритма
По индукции:
-на первом шаге код отвечеат условиям
-предположим, что получившийся код на шаге i есть Код Грея
-тогда на шаге i+1: первая половина кода будет корректна, так как она совпадает с кодом с шага i за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она явлеятся зеракальным отражением первой половины, только добавлена везде 1. На стыке: i бит совпадают в силу зеркальности, отличается последний. Таким образом этот код - Код Грея. Индукционное предположение доказанно, алгоритм работает верно.
Этот алгоритм можно обобщить и для k-ичных векторов. Сущестует ещё несколько видов Кода Грея - сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.
