Коды Грея

Материал из Викиконспекты
Версия от 18:48, 14 января 2015; Zernov (обсуждение | вклад) (→‎Задача о Ханойских башнях)
Перейти к: навигация, поиск
Определение:
Код Грея (англ. Gray code) — такое упорядочение [math]k[/math]-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде.


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

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

Получение зеркального двоичного кода Грея.


Существует несколько видов кода Грея, самый простой из них — так называемый зеркальный двоичный код Грея. Строится он так:

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

Псевдокод

[math]GrayCode[/math] — двумерный массив, в котором [math]GrayCode[a, b][/math] — [math]b[/math]-ый бит в [math]a[/math]-ом коде Грея. 

buildCode(n):
   GrayCode[1, n] = 0
   GrayCode[2, n] = 1                 // Построение кода длины 1 
   p = 2                              // Где p — количество уже имеющихся кодов 
   for i = 2 to n
      t = p
      p = p * 2
      for k = (p / 2 + 1) to p
         GrayCode[k] = GrayCode[t]    // Отражение имеющихся кодов 
         GrayCode[t, n + 1 - i] = 0
         GrayCode[k, n + 1 - i] = 1   // Добавление 0 и 1 в начало 
         t--

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

По индукции:

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

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

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

Существует ещё несколько видов кода Грея — сбалансированный код Грея, код Баркера-Грея, одноколейный код Грея.[1] Кроме того, коды Грея используются для упорядочения перестановок.

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

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

Для кода длиной [math]1[/math] бит утверждение проверяется непосредственно.

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

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

Для любого [math]x \lt 2^n[/math] выполняется [math]\enskip L_x = 0M_x[/math] и, по условию, равно

[math]L_x = 0(x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1})[/math] раскрыв скобки, получим новое выражение [math]L_x[/math]:

[math]= 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1}[/math] что равно (второе слагаемое равно первому, побитово сдвинутого вправо.)

[math]= x \oplus (\lfloor x / 2 \rfloor)[/math]

Для любого [math]x \geq 2^n[/math] выполняется [math]\enskip L_x = 1[/math][math]M_y[/math], где [math]y = 2^{n+1} - 1 - x = \neg x[/math], то есть

[math]L_x = 1(\overline {x_{n-1} x_{n-2}... x_{0}} \oplus 0 \overline {x_{n-1} x_{n-2}... x_{1}})[/math] что по свойству xor ([math]\neg x \oplus \neg y = x \oplus y[/math]) равно

[math]= 1(\overline {x_{n-1}}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1})[/math] или (все по тому же свойству)

[math]= 1(x_{n-1}x_{n-2}...x_{0} \oplus 1x_{n-1}x_{n-2}...x_{1})[/math] раскрыв скобки, получим

[math]= 1x_{n-1}x_{n-2}...x_{0} \oplus 01x_{n-1}x_{n-2}...x_{1}[/math] откуда получаем, зная из условия, что старший разряд [math]L_x[/math] равен [math]1[/math]

[math]= x_{n}x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n}x_{n-1}x_{n-2}...x_{1}[/math] что, аналогично первому пункту, равно

[math]= x \oplus (\lfloor x / 2 \rfloor)[/math]

Таким образом, шаг индукции доказан, следовательно, теорема верна.
[math]\triangleleft[/math]
Пример однодорожечного кода грея.

Сбалансированный код Грея

Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия "однородности". В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно.

Чтобы показать это точнее, пусть [math]G[/math] — это [math]R[/math]-ичный полный цикл Грея, имеющий последовательность перехода [math](\delta_k)[/math], которая определяет различие последующего бита в коде Грея с предыдущим(и различие последнего с первым); отсчёты переходов (спектры) [math]G[/math] являются наборами целых чисел, определенных как [math]\lambda_k = |\{ j \in \mathbb{Z}_{R^n} : \delta_j = k \}| \,[/math] для [math] k \in \mathbb{Z}_R[/math].

Код Грея является однородным или равномерно сбалансированным, если все его отсчёты переходов равны, и в этом случае у нас есть [math]\lambda_k = R^n / n[/math] для всех [math]k[/math]. Ясно, что при [math]R = 2[/math], такие коды существуют только при [math]n = 2[/math]. В противном случае, если [math]R^n[/math] не делится на [math]n[/math] равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо [math]\lfloor R^n / n \rfloor [/math] либо [math] \lceil R^n / n \rceil[/math].

Коды Грея также могут быть экспоненциально сбалансироваными, если все их отсчеты переходов являются смежными степеням двойки, и такие коды существуют для каждой степени двойки.

Однодорожечный код Грея

Еще один вид кода Грея — это однодорожечный код Грея, разработанный Спеддингом и уточнен Хильтгеном, Патерсоном и Брандестини.

Однодорожечный код Грея является циклическим списком уникальных двоичных кодировок длины [math]n[/math] так, что два последовательных слова отличаются ровно в одной позиции, и когда список рассматривается как [math]P_{xn}[/math] матрица, каждая колонка — это циклический сдвиг первого столбца. Название происходит от их использования датчиками вращения, где количество дорожек в настоящее время измеряется с помощью контактов, в результате для каждой дорожки на выход подаётся [math]0[/math] или [math]1[/math].

Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в [math]1[/math] градус нужно, по крайней мере, [math]360[/math] различных позиций на оборот, который требует минимум [math]9[/math] бит данных, и тем самым такое же количество контактов.

Не путать с цепными кодами., получаемых циклическим сдвигом

Применение

Фрэнк Грей изобрел метод для преобразования аналоговых сигналов в отраженные двоичные кодовые группы с использованием аппарата на основе вакуумной трубки. Способ и устройство были запатентованы в 1953 году, а код получил название код Грея. "PCM трубка" — аппарат, запатентованный Греем, был сделан Раймондом У. Сирсом из (англ.) Bell Labs, работая с Греем и Уильямом М. Гудоллом.

  • В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках-энкодерах [2]).

В частности, коды Грея и были открыты в связи с этим применением. (Код Грея — это код преобразования бинарных символов в [math]M[/math]-арные, такие, что двоичные последовательности, соответствующие соседним символам (сдвигам фаз), отличаются только одним битом. Обычная бинарная кодировка сравнивается с кодировкой Грея. При появлении ошибки в [math]M[/math]-арном символе наиболее вероятными являются ближайшие соседние символы, отличающиеся от переданного лишь одним битом, если используется кодировка Грея.

Таким образом, высока вероятность того, что при кодировании с помощью кода Грея в случае возникновения ошибки ошибочным будет только один из [math]k = \log_2 M[/math] переданных битов.)

  • Коды Грея используются для кодирования номера дорожек в жёстких дисках.
  • Коды Грея широко применяются в теории генетических алгоритмов [3] для кодирования генетических признаков, представленных целыми числами.
  • Коды Грея используются в Картах Карно[4] (при передаче в карту переменные сортируются в код Грея).
  • Алгоритм модуляции 2B1Q (англ. 2 Binary 1 Quandary) [5]
  • Код Грея можно использовать также и для решения следующей задачи[6]:

Задача о Ханойских башнях

Задача:
Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Решение:

Пусть [math]n[/math] — количество дисков. Начнём с кода Грея длины [math]n[/math], состоящего из одних нулей (т.е. [math]G(0)[/math]), и будем двигаться по кодам Грея (от [math]G(i)[/math] переходить к [math]G(i+1)[/math]).

Поставим в соответствие каждому [math]i[/math]-ому биту текущего кода Грея [math]i[/math]-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита [math]i[/math] как перемещение [math]i[/math]-го диска.

Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций), т.к. два варианта хода означают, что свободны два оставшихся стержня, а это значит, что на самом верху исходного лежит наименьший(по условию). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если [math]n[/math] нечётно, то последовательность перемещений наименьшего диска имеет вид [math]r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow \ldots .[/math](где [math]r_{1}[/math] — стартовый стержень, [math]r_{3}[/math] — финальный стержень, [math]r_{2}[/math] — оставшийся стержень), а если [math]n[/math] чётно, то [math]r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow \ldots.[/math]

Примечания

Источники информации

См. Также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Коды_Грея&oldid=44475»