Коды Грея

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

Определение

Определение:

Код Грея (Gray code) — такое упорядочение [math]k[/math]-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде.

Код назван в честь Фрэнка Грея, который в 1947-ом году получил патент на "отражённый двоичный код". Изначально он предназначался для избавления от паразитных состояний в электромеханических переключателях, однако сейчас область его применения гораздо шире.

Алгоритм построения

Существует несколько видов Кода Грея, самый простой из них — так называемый зеркальный двоичный Код Грея. Строится он так: Для получения кода длины [math]n[/math] производится [math]n[/math] шагов. На первом шаге код имеет длину 1 и состоит из двух векторов (0) и (1). На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается "0", а ко второй — "1". С каждым шагом длина векторов увеличивается на 1, а их количество — вдвое. Таким образом, количество векторов длины [math]n[/math] равно [math]2^n.[/math]

Доказательство правильности работы алгоритма

По индукции:

• на первом шаге код отвечает условиям
• предположим, что код, получившийся на [math]i[/math]-ом шаге, является Кодом Грея
• тогда на шаге [math]i + 1[/math]: первая половина кода будет корректна, так как она совпадает с кодом с шага [math]i[/math] за исключением добавленного последнего бита 0. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит 1. На стыке: первые [math]i[/math] бит совпадают в силу зеркальности, последние различны по построению.

Таким образом, этот код — Код Грея. Индукционное предположение доказано, алгоритм работает верно.

Псевдокод

 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

Этот алгоритм можно обобщить и для [math]k[/math]-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код Грея.

Существует ещё несколько видов Кода Грея — сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея.

Применение

Код Грея применяется в:

• датчиках-энкодерах ( устройства, преобразующие угол поворота вала в электрический сигнал );

• как способ решения задачи о Ханойских башнях ( дано три стержня, на первом из них нанизано 8 колец разного размера в виде пирамиды; цель — перенести

пирамиду на другой стержень, сохранив упорядоченность );

• в генетических алгоритмах;

• в Картах Карно ( при передаче в карту переменные сортируются в Код Грея );

• в кодах, исправляющих ошибки;

• для связи систем с различной частотой работы.

Источники

• Gray code, From Wikipedia, the free encyclopedia

• Код Грея, Материал из Википедии — свободной энциклопедии