Коды Грея — различия между версиями
Gromak (обсуждение | вклад) (Небольшие косметические изменения и добавление псевдокода) |
Gromak (обсуждение | вклад) (Явная формула и немного косметики) |
||
Строка 38: | Строка 38: | ||
{{Определение | {{Определение | ||
+ | |id = def1. | ||
|neat = 1 | |neat = 1 | ||
|definition = | |definition = | ||
Строка 54: | Строка 55: | ||
Для получения кода длины <tex>n</tex> производится <tex>n</tex> шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй {{---}} "1". С каждым шагом длина векторов увеличивается на 1, а их количество {{---}} вдвое. | Для получения кода длины <tex>n</tex> производится <tex>n</tex> шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй {{---}} "1". С каждым шагом длина векторов увеличивается на 1, а их количество {{---}} вдвое. | ||
Таким образом, количество векторов длины <tex>n</tex> равно <tex>2^n.</tex> | Таким образом, количество векторов длины <tex>n</tex> равно <tex>2^n.</tex> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=== Псевдокод === | === Псевдокод === | ||
Строка 77: | Строка 69: | ||
GrayCode[k, n + 1 - i] = 1 | GrayCode[k, n + 1 - i] = 1 | ||
</font> | </font> | ||
+ | |||
+ | === Доказательство правильности работы алгоритма === | ||
+ | |||
+ | По индукции: | ||
+ | |||
+ | * на первом шаге код отвечает условиям | ||
+ | * предположим, что код, получившийся на <tex>i</tex>-ом шаге, является Кодом Грея | ||
+ | * тогда на шаге <tex>i + 1</tex>: первая половина кода будет корректна, так как она совпадает с кодом с шага <tex>i</tex> за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые <tex>i</tex> бит совпадают в силу зеркальности, последние различны по построению. | ||
+ | Таким образом, этот код {{---}} Код Грея. Индукционное предположение доказано, алгоритм работает верно. | ||
Этот алгоритм можно обобщить и для <tex>k</tex>-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея. | Этот алгоритм можно обобщить и для <tex>k</tex>-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея. | ||
Строка 82: | Строка 83: | ||
Существует ещё несколько видов Кода Грея {{---}} сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея. | Существует ещё несколько видов Кода Грея {{---}} сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея. | ||
+ | == Явная формула для получения зеркального двоичного кода Грея == | ||
+ | |||
+ | {{Теорема | ||
+ | |id = th1. | ||
+ | |statement = | ||
+ | В двоичном зеркальном коде Грея <tex>i</tex>-ый код может быть получен по формуле <tex>G_i = i \oplus (i \div 2)</tex> при нумерации кодов с нуля. | ||
+ | |proof = | ||
+ | Для кода длиной 1 бит утверждение очевидно. | ||
+ | Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено <tex>\forall i \enskip M_i = i \oplus (i \div 2)</tex> | ||
+ | |||
+ | Обозначим за <tex>L</tex> код длины <tex>n + 1</tex>, полученный из <tex>M</tex> описанным выше алгоритмом. Тогда: | ||
+ | |||
+ | <tex>\forall x < 2^n \enskip L_x = 0M_x = 0(x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) = 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1} = x \oplus (x \div 2)</tex> | ||
+ | |||
+ | <tex>\forall x \geq 2^n \enskip L_x = 1M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть <tex>L_x = 1(\neg x_{n-1} \neg x_{n-2}... \neg x_{0} \oplus 0 \neg x_{n-1} \neg x_{n-2}... \neg x_{1}) = 1(\neg x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) = 1(x_{n-1}x_{n-2}...x_{0} \oplus 1x_{n-1}x_{n-2}...x_{1}) = 1x_{n-1}x_{n-2}...x_{0} \oplus 01x_{n-1}x_{n-2}...x_{1} = x_{n}x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n}x_{n-1}x_{n-2}...x_{1} = x \oplus (x \div 2)</tex> | ||
+ | |||
+ | Таким образом, по теореме о математической индукции требуемое доказано. | ||
+ | }} | ||
== Применение == | == Применение == |
Версия 04:41, 31 октября 2011
2-битный код Грея
00 01 11 10 |
3-битный код Грея
000 001 011 010 110 111 101 100 |
4-битный код Грея
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 |
Содержание
Определение
Код назван в честь Фрэнка Грея, который в 1947-ом году получил патент на "отражённый двоичный код". Изначально он предназначался для избавления от паразитных состояний в электромеханических переключателях, однако сейчас область его применения гораздо шире.
Алгоритм построения
Существует несколько видов Кода Грея, самый простой из них — так называемый зеркальный двоичный Код Грея. Строится он так: Для получения кода длины
производится шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй — "1". С каждым шагом длина векторов увеличивается на 1, а их количество — вдвое. Таким образом, количество векторов длины равноПсевдокод
buildCode(n): GrayCode[1, n] = 0 GrayCode[2, n] = 1 p = 2 for (i = 2, i <= n, i++): p = p * 2 for (k = i + 1, k <= 2 * i, k++): GrayCode[k] = GrayCode[p + 1 - k] GrayCode[k, n + 1 - i] = 1
Доказательство правильности работы алгоритма
По индукции:
- на первом шаге код отвечает условиям
- предположим, что код, получившийся на -ом шаге, является Кодом Грея
- тогда на шаге : первая половина кода будет корректна, так как она совпадает с кодом с шага за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые бит совпадают в силу зеркальности, последние различны по построению.
Таким образом, этот код — Код Грея. Индукционное предположение доказано, алгоритм работает верно.
Этот алгоритм можно обобщить и для
-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.Существует ещё несколько видов Кода Грея — сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.
Явная формула для получения зеркального двоичного кода Грея
Теорема: |
В двоичном зеркальном коде Грея -ый код может быть получен по формуле при нумерации кодов с нуля. |
Доказательство: |
Для кода длиной 1 бит утверждение очевидно. Пусть существует зеркальный двоичный код Грея длины , для которого выполненоОбозначим за код длины , полученный из описанным выше алгоритмом. Тогда:
Таким образом, по теореме о математической индукции требуемое доказано. , где , то есть |
Применение
Код Грея применяется в:
- датчиках-энкодерах ( устройства, преобразующие угол поворота вала в электрический сигнал );
- как способ решения задачи о Ханойских башнях ( дано три стержня, на первом из них нанизано 8 колец разного размера в виде пирамиды; цель — перенести
пирамиду на другой стержень, сохранив упорядоченность );
- в генетических алгоритмах;
- в Картах Карно ( при передаче в карту переменные сортируются в Код Грея );
- в кодах, исправляющих ошибки;
- для связи систем с различной частотой работы.