Коды Грея

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

Код Грея (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]. Коды Грея также могут быть экспоненциально сбалансироваными, если все их отсчеты переходов являются смежными степеням двойки, и такие коды существуют для каждой степени двойки.

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

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

Применение

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

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

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

Задача:

Пусть 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

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