Изменения
→Явная формула для получения зеркального двоичного кода Грея
{{Определение
|definition =
'''Код Грея ''' (англ. ''Gray code)''') {{---}} такое упорядочение <tex>k</tex>-ичных (обычно двоичных) векторов, что соседние вектора отличаются только в одном разряде.
}}
== Алгоритм построения ==
[[Файл:Gray_CodeGray_Code_Building.png|360px300px|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>n</tex> равно <tex>2^n.</tex>
{| border="0"
|align="left" colspan="4"|
*<tex>\mathtt{GrayCode }</tex> {{---}} двумерный массивтипа '''boolean''', в котором <tex>\mathtt{GrayCode[a, b] }</tex> {{---}} <tex>b</tex>-ый бит в <tex>a</tex>-ом коде Грея,*<tex>\mathtt{p}</tex> {{---}} Счетчик количества уже имеющихся кодов,*<tex>\mathtt{t}</tex> {{---}} Показывает количество кодов в <tex>(a-1)</tex>-м коде Грея.<font size=3code>
buildCode(n):
|}
* на первом шаге код отвечает условиям
* предположим, что код, получившийся на <tex>i</tex>-ом шаге, является Кодом кодом Грея
* тогда на шаге <tex>i + 1</tex>: первая половина кода будет корректна, так как она совпадает с кодом с шага <tex>i</tex> за исключением добавленного последнего бита <tex>0</tex>. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит <tex>1</tex>. На стыке: первые <tex>i</tex> бит совпадают в силу зеркальности, последние различны по построению.
Таким образом, этот код {{---}} Код код Грея. Индукционное предположение доказано, алгоритм работает верно.
Этот алгоритм можно обобщить и для <tex>k</tex>-ичных векторов. Также известен алгоритм преобразования двоичного кода в Код код Грея.
Существует ещё несколько видов Кода кода Грея {{---}} сбалансированный Код код Грея, код БеккетаБаркера-Грея, одноколейный Код код Грея.<ref>[http://en.wikipedia.org/wiki/Gray_code#Special_types_of_Gray_codes Wikipedia {{---}} Special types of Gray codes]</ref> Кроме того, коды Греяиспользуются для [[:Коды_Грея_для_перестановок|упорядочения перестановок.]]
== Явная формула для получения зеркального двоичного кода Грея ==
Для кода длиной <tex>1</tex> бит утверждение проверяется непосредственно.
Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено, что для любого <tex>i </tex> выполняется <tex>\enskip enspace M_i = i \oplus (\lfloor i / 2 \rfloor)</tex>
Обозначим за <tex>L</tex> код длины <tex>n + 1</tex>, полученный из <tex>M</tex> описанным выше алгоритмом. Тогда:
Для любого <tex>x < 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}) =</tex>выполняется <tex> 0x_{n-1}x_{n-2}...x_{0} \oplus 00x_{n-1}x_{n-2}...x_{1} enspace L_x = x \oplus (\lfloor x / 2 \rfloor)0M_x</tex>и, по условию, равно
<tex>L_x = 1(\overline {x_0x_{n-1} x_{n-2}... \dots x_{0}} \oplus 0 \overline {x_00x_{n-1} x_{n-2}... \dots x_{1}}) =</tex><tex> 1что равно (\overline {x_{n-1}}x_{n-2}...x_{0} \oplus 0x_{n-1}x_{n-2}..второе слагаемое равно первому, побитово сдвинутого вправо.x_{1}) =</tex>
<tex>= x \oplus (\lfloor x / 2 \rfloor)</tex> Для любого <tex>x \geqslant 2^n</tex> выполняется <tex>\enspace L_x = 1</tex><tex>M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть <tex>L_x = 1(\overline {x_{n-1}x_{n-2}... \dots x_{0}} \oplus 1x_0 \overline {x_{n-1} x_{n-2} \dots x_{1}})</tex> что по свойству '''xor''' (<tex>\neg x \oplus \neg y = x \oplus y</tex>) равно <tex>= 1(\overline {x_{n-1}}x_{n-2} \dots x_{0} \oplus 0x_{n-1}x_{n-2}... \dots x_{1}) </tex> или (все по тому же свойству) <tex>= 1(x_{n-1}x_{n-2} \dots x_{0} \oplus 1x_{n-1}x_{n-2}... \dots x_{01})</tex>раскрыв скобки, получим <tex> = 1x_{n-1}x_{n-2} \dots x_{0} \oplus 01x_{n-1}x_{n-2}... \dots x_{1} </tex> откуда получаем, зная из условия, что старший разряд <tex>L_x</tex> равен <tex>1</tex> <tex>= x_{n}x_{n-1}x_{n-2}... \dots x_{0} \oplus 0x_{n}x_{n-1}x_{n-2}... \dots x_{1} =</tex>что, аналогично первому пункту, равно <tex> = x \oplus (\lfloor x / 2 \rfloor)</tex>
Таким образом, шаг индукции доказан, следовательно, теорема верна.
}}
=== Сбалансированный код Грея ===
Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия "однородности". В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно. Чтобы показать это точнее, пусть <tex>G</tex> {{- --}} это <tex>R<//tex>-ичный полный цикл Грея, имеющий последовательность перехода <tex> (\delta_k)</tex>, <tex>\delta_k = i</tex>, для <tex>k = 0 \dots n</tex> если в коде Грея <tex>i</tex>-й и <tex>(i+1)</tex> биты различны и <tex>n</tex> {{---}} кол-во таких различий; отсчёты переходов(спектры) <tex>G</tex> являются наборами целых чисел, определенных как <mathtex>\lambda_k = |\{ j \in \mathbb{Z}_{R^n} : \delta_j = k \}| \, , \text { for } </tex> для <tex> k \in \mathbb{Z}_R</mathtex>. Код Грея является однородным или равномерно сбалансированным, если все его отсчёты переходов равны, и в этом случае у нас есть <mathtex>\lambda_k = R^n / n</mathtex> для всех <mathtex>k</mathtex>. Ясно, что при <tex>R = 2</tex>, такие коды существуют только при <tex>n = 2</tex>. В противном случае, если <tex>R^n</tex> не делится на <tex>n</tex> равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо <mathtex>\lfloor R^n / n \rfloor </mathtex> либо <mathtex> \lceil R^n / n \rceil</mathtex>. Коды Грея также могут быть экспоненциально сбалансироваными, если все их отсчеты переходов являются смежными степеням двойки, и такие коды существуют для каждой степени двойки.
=== Однодорожечный код Грея ===
Еще один вид кода Грея {{- --}} это однодорожечный код Грея. Разработан , разработанный Спеддингом и уточнен Хильтгеном, Патерсоном и Брандестини. Однодорожечный код Грея является циклическим списком уникальных двоичных кодировок длины <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 трубку с отраженным двоичным кодом в тарелке.]]* В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках-энкодерах <ref>[http://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D0%BA%D0%BE%D0%B4%D0%B5%D1%80 датчикахВикипедия {{---энкодерах}} Датчик угла поворота]</ref>). В частности, коды Грея и были открыты в связи с этим применением. (Код Грея — это код преобразования бинарных символов в <tex>M</tex>-арные, такие, что двоичные последовательности, соответствующие соседним символам (сдвигам фаз), отличаются только одним битом. Обычная бинарная кодировка сравнивается с кодировкой Грея. При появлении ошибки в <tex>M</tex>-арном символе наиболее вероятными являются ближайшие соседние символы, отличающиеся от переданного лишь одним битом, если используется кодировка Грея. Таким образом, высока вероятность того, что при кодировании с помощью кода Грея в случае возникновения ошибки ошибочным будет только один из <tex>k = \log_2 M</tex> переданных битов.)
* Коды Грея используются для кодирования номера дорожек в жёстких дисках.
* Коды Грея широко применяются в теории генетических алгоритмов <ref>[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 Википедия {{---}} Генетический алгоритм]</ref> для кодирования генетических признаков, представленных целыми числами. * Коды Грея используются в Картах Карно<ref>[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 Википедия {{---}} Карта Карно]</ref> (при передаче в карту переменные сортируются в код Грея). * Алгоритм модуляции 2B1Q (англ. ''2 Binary 1 Quandary'') <ref>[http://en.wikipedia.org/wiki/2B1Q Wikipedia {{---}} 2B1Q]</ref> * Код Грея можно использовать также и для решения следующей задачи о <ref>[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 Википедия {{---}} Ханойская Башня]</ref>: === Задача о Ханойских башнях]: ===
{{задача
|definition =
}}
== Источники информации ==
* [http://en.wikipedia.org/wiki/Gray_code Wikipedia {{---}} Gray code, From Wikipedia, the free encyclopedia]
* [http://ru.wikipedia.org/wiki/Код_Грея код_Грея Википедия {{---}} Код Грея, Материал из Википедии — свободной энциклопедии]
* [http://www.jucs.org/jucs_13_11/the_gray_code/jucs_13_11_1573_1597_doran.pdf Robert W. Doran The Gray Code, Journal of Universal Computer Science, vol. 13, no. 11 (2007).]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]