317
правок
Изменения
7, 12, 15
[[Файл:Gray_Code.png|360px|thumb|right|Иллюстрация получения зеркального двоичного кода Грея.]]
Существует несколько видов Кода кода Грея, самый простой из них {{---}} так называемый зеркальный двоичный Код код Грея. Строится он так:
Для получения кода длины <tex>n</tex> производится <tex>n</tex> шагов. На первом шаге код имеет длину <tex>1</tex> и состоит из двух векторов <tex>0</tex> и <tex>1</tex>. На каждом следующем шаге в конец списка заносятся все уже имеющиеся вектора в обратном порядке, и затем к первой половине получившихся векторов дописывается <tex>0</tex>, а ко второй <tex>1</tex>. С каждым шагом длина векторов увеличивается на <tex>1</tex>, а их количество {{---}} вдвое.
* на первом шаге код отвечает условиям
* предположим, что код, получившийся на <tex>i</tex>-ом шаге, является Кодом кодом Грея
* тогда на шаге <tex>i + 1</tex>: первая половина кода будет корректна, так как она совпадает с кодом с шага <tex>i</tex> за исключением добавленного последнего бита <tex>0</tex>. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит <tex>1</tex>. На стыке: первые <tex>i</tex> бит совпадают в силу зеркальности, последние различны по построению.
Таким образом, этот код {{---}} Код код Грея. Индукционное предположение доказано, алгоритм работает верно.
Этот алгоритм можно обобщить и для <tex>k</tex>-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код код Грея.
Существует ещё несколько видов Кода кода Грея {{---}} сбалансированный Код код Грея, код БеккетаБаркера-Грея, одноколейный Код код Грея.
== Явная формула для получения зеркального двоичного кода Грея ==
Обозначим за <tex>L</tex> код длины <tex>n + 1</tex>, полученный из <tex>M</tex> описанным выше алгоритмом. Тогда:
Для любого <tex>x < 2^n \enskip L_x = 0M_x 0 M_x = 0(x_{n-1}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}...x_{1}) =</tex>
<tex> 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1} = x \oplus (\lfloor x / 2 \rfloor)</tex>
Для любого <tex>x \geq 2^n \enskip L_x = 1M_y1 M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть
<tex>L_x = 1(\overline {x_{n-1} x_{n-2}... x_{0}} \oplus 0 \overline {x_{n-1} x_{n-2}... x_{1}}) =</tex>
== Специальные типы кодов Грея ==
=== Сбалансированный код Грея ===
Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия "однородности". В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно. Чтобы показать это точнее, пусть <tex>G</tex> {{- --}} это <tex>R<//tex>-ичный полный цикл Грея, имеющий последовательность перехода <texmath> (\delta_k)</texmath>; отсчёты переходов(спектры) <tex>G</tex> являются наборами целых чисел, определенных как <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>. Ясно, что при <tex>R = 2</tex>, такие коды существуют только при <tex>n = 2</tex>. В противном случае, если <tex>R^n</tex> не делится на <tex>n</tex> равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо <math>\lfloor R^n / n \rfloor </math> либо <math> \lceil R^n / n \rceil</math>. Коды Грея также могут быть экспоненциально сбалансироваными, если все их отсчеты переходов являются смежными степеням двойки, и такие коды существуют для каждой степени двойки.
=== Однодорожечный код Грея ===
Еще один вид кода Грея {{--- }} это однодорожечный код Грея. Разработан Спеддингом и уточнен Хильтгеном, Патерсоном и Брандестини. Однодорожечный код Грея является циклическим списком уникальных двоичных кодировок длины <tex>n</tex> так, что два последовательных слова отличаются ровно в одной позиции, и когда список рассматривается как <tex>P_{xn}</tex> матрица, каждая колонка {{--- }} это циклический сдвиг первого столбца. Название происходит от их использования датчиками вращения, где количество дорожек в настоящее время измеряется с помощью контактов, в результате для каждой дорожки на выход подаётся <tex>0</tex> или <tex>1</tex>. Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в <tex>1</tex> градус нужно, по крайней мере, <tex>360</tex> различных позиций на оборот, который требует минимум <tex>9</tex> бит данных, и тем самым такое же количество контактов.
== Применение ==
Фрэнк Грей изобрел метод для преобразования аналоговых сигналов в отраженные двоичные кодовые группы с использованием аппарата на основе вакуумной трубки. Способ и устройство были запатентованы в 1953 году, а код получил название код Грея. "PCM трубка" {{- --}} аппарат, запатентованный Греем, был сделан Раймондом У. Сирсом из Bell Labs, работая с Греем и Уильямом М. Гудоллом.
[[Файл:PCM_Tube.png|500px|thumb|center|Часть первой страницы патента Грея, показывающая PCM трубку с отраженным двоичным кодом в тарелке.]]
* В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в [http://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D0%BA%D0%BE%D0%B4%D0%B5%D1%80 датчиках-энкодерах]). В частности, коды Грея и были открыты в связи с этим применением. (Код Грея — это код преобразования бинарных символов в <tex>M</tex>-арные, такие, что двоичные последовательности, соответствующие соседним символам (сдвигам фаз), отличаются только одним битом. Обычная бинарная кодировка сравнивается с кодировкой Грея. При появлении ошибки в <tex>M</tex>-арном символе наиболее вероятными являются ближайшие соседние символы, отличающиеся от переданного лишь одним битом, если используется кодировка Грея. Таким образом, высока вероятность того, что при кодировании с помощью кода Грея в случае возникновения ошибки ошибочным будет только один из <tex>k = \log_2 M</tex> переданных битов.)
* Коды Грея используются для кодирования номера дорожек в жёстких дисках.
* Код Грея можно использовать также и для решения задачи о [http://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B8%D0%B5_%D0%B1%D0%B0%D1%88%D0%BD%D0%B8 Ханойских башнях]:
}}
* Коды Грея широко применяются в теории [http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC генетических алгоритмов] для кодирования генетических признаков, представленных целыми числами.
* Коды Грея используются в [http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D1%8B_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE Картах Карно] (при передаче в карту переменные сортируются в Код код Грея).
== Источники ==
* [http://en.wikipedia.org/wiki/Gray_code Gray code, From Wikipedia, the free encyclopedia]
* [http://ru.wikipedia.org/wiki/Код_Грея код_Грея Код Грея, Материал из Википедии — свободной энциклопедии]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
