Коды Грея

Материал из Викиконспекты
Версия от 05:42, 1 ноября 2011; Rybak (обсуждение | вклад) (предлагаю такой вариант (с float у таблицы))
Перейти к: навигация, поиск

Определение

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


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

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

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

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

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

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

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

Явная формула для получения зеркального двоичного кода Грея

Теорема:
В двоичном зеркальном коде Грея [math]i[/math]-ый код может быть получен по формуле [math]G_i = i \oplus (i \div 2)[/math] при нумерации кодов с нуля.
Доказательство:
[math]\triangleright[/math]

Для кода длиной 1 бит утверждение очевидно. Пусть существует зеркальный двоичный код Грея [math]M[/math] длины [math]n[/math], для которого выполнено [math]\forall i \enskip M_i = i \oplus (i \div 2)[/math]

Обозначим за [math]L[/math] код длины [math]n + 1[/math], полученный из [math]M[/math] описанным выше алгоритмом. Тогда:

[math]\forall x \lt 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)[/math]

[math]\forall x \geq 2^n \enskip L_x = 1M_y[/math], где [math]y = 2^{n+1} - 1 - x = \neg x[/math], то есть

[math]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)[/math]

Таким образом, по теореме о математической индукции требуемое доказано.
[math]\triangleleft[/math]

Применение

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

  • датчиках-энкодерах ( устройства, преобразующие угол поворота вала в электрический сигнал );
  • как способ решения задачи о Ханойских башнях ( дано три стержня, на первом из них нанизано 8 колец разного размера в виде пирамиды; цель — перенести пирамиду на другой стержень, сохранив упорядоченность );
  • в генетических алгоритмах;
  • в Картах Карно ( при передаче в карту переменные сортируются в Код Грея );
  • в кодах, исправляющих ошибки;
  • для связи систем с различной частотой работы.


Источники