Изменения

Для получения кода длины <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 + 1</tex>: первая половина кода будет корректна, так как она совпадает с кодом с шага <tex>i</tex> за исключением добавленного последнего бита <tex>0</tex>. Вторая половина тоже соответствует условиям, так как она является зеркальным отражением первой половины, только добавлен везде бит <tex>1</tex>. На стыке: первые <tex>i</tex> бит совпадают в силу зеркальности, последние различны по построению.

Для кода длиной <tex>1 </tex> бит утверждение проверяется непосредственно.

Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия "однородности". В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно. Чтобы показать это точнее, пусть <tex>G </tex> - это <tex>R<//tex>-ичный полный цикл Грея, имеющий последовательность перехода <mathtex> (\delta_k)</mathtex>; отсчёты переходов(спектры) <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>. В противном случае, если <mathtex>R^n</mathtex> не делится на <tex>n </tex> равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо <math>\lfloor R^n / n \rfloor </math> либо <math> \lceil R^n / n \rceil</math>. Коды Грея также могут быть экспоненциально сбалансироваными, если все их отсчеты переходов являются смежными степеням двойки, и такие коды существуют для каждой степени двойки.

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

* В технике коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в [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>-арном символе наиболее вероятными являются ближайшие соседние символы, отличающиеся от переданного лишь одним битом, если используется кодировка Грея. Таким образом, высока вероятность того, что при кодировании с помощью кода Грея в случае возникновения ошибки ошибочным будет только один из <mathtex>k = log_2 M</mathtex> переданных битов.)

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