Коды Грея

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

Код Грея (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]

Псевдокод

GrayCode — двумерный массив, в котором GrayCode[a, b] — [math]b[/math]-ый бит в [math]a[/math]-ом коде Грея. buildCode(n): GrayCode[1, n] = 0 GrayCode[2, n] = 1 {построение кода длины 1} p = 2 {p — количество уже имеющихся кодов} 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 - i, n + 1 - i] = 0 GrayCode[k, n + 1 - i] = 1 {добавление 0 и 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 (\lfloor i / 2 \rfloor)[/math] при нумерации кодов с нуля.

Доказательство:

[math]\triangleright[/math]

Для кода длиной 1 бит утверждение проверяется непосредственно. Пусть существует зеркальный двоичный код Грея [math]M[/math] длины [math]n[/math], для которого выполнено, что для любого [math]i \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 \enskip L_x = 0M_x = 0(x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) =[/math] [math] 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1} = x \oplus (\lfloor x / 2 \rfloor)[/math] Для любого [math]x \geq 2^n \enskip L_x = 1M_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] [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}) = 1x_{n-1}x_{n-2}...x_{0}[/math] [math] \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} =[/math] [math] x \oplus (\lfloor x / 2 \rfloor)[/math] Таким образом, шаг индукции доказан, следовательно, теорема верна.

[math]\triangleleft[/math]

Специальные типы кодов Грея

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

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

Код Беккета-Грея

Код Беккета-Грея был назван в честь ирландского писателя Сэмюэла Беккета, который интересовался симметрией. Его пьеса "Quad" содержала в себе четырёх актёров и была разделена на 16 временных периодов. Каждый период заканчивался, когда один из четырёх актёров выходил на сцену или же, наоборот, уходил с неё. Пьеса начиналась на пустой сцене, и Беккет хотел, чтобы каждое подмножество актёров появлялось ровно один раз. Ясно, что множество актёров, находящихся в данное время на сцене может быть представлено в виде 4-битного двоичного кода Грея. Беккет, однако, добавил дополнительное условие в сценарий: чтобы со сцены уходил всегда тот из актеров, кто находился на ней дольше остальных. Актёры могли быть представлены как FIFO очередь так, что (из всех актёров на сцене) уходил всегда тот актёр, который был первым в этой очереди. Беккет не смог найти код Беккета-Грея для своей пьесы, да и вообще, исчерпывающее перечисление всех возможных последовательностей показывает, что такой код не существует для n = 4. Известно, что сегодня такие коды существуют для n = 2, 5, 6, 7, и 8, и не существуют для n = 3 или 4.

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

Еще один вид кода Грея - это Однодорожечный Код Грея. Разработан Спеддингом и уточнен Хильтгеном, Патерсоном и Брандестини в работе "Single-track Gray codes"(1996). Код является циклическим списоком P уникальных двоичных кодировок длины n так, что два последовательных слова отличаются ровно в одной позиции, и когда список рассматривается как [math]P_{xn}[/math] матрица, каждая колонка - это циклический сдвиг первого столбца. Название происходит от их использования датчиками вращения, где количество дорожек в настоящее время измеряется с помощью контактов, в результате для каждой дорожки на выход подаётся 0 или 1. Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в 1 градус нужно, по крайней мере, 360 различных позиций на оборот, который требует минимум 9 бит данных, и тем самым такое же количество контактов.

Применение

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

   Пусть n — количество дисков. Начнём с кода Грея длины n, состоящего из одних нулей (т.е. G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i+1)). Поставим в соответствие каждому i-ому биту               
 текущего кода Грея i-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем 
 понимать изменение бита i как перемещение i-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для 
 наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если n нечётно, то последовательность перемещений наименьшего диска имеет вид 
 [math]f \rightarrow t \rightarrow r \rightarrow f \rightarrow t \rightarrow r \rightarrow \ldots .[/math](где f — стартовый стержень, t — финальный стержень, r — оставшийся стержень), а если n чётно, то [math]f \rightarrow r \rightarrow t \rightarrow f \rightarrow r \rightarrow t \rightarrow \ldots.[/math]

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

Источники

• Gray code, From Wikipedia, the free encyclopedia

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