317
правок
Изменения
Нет описания правки
== Алгоритм построения ==
[[Файл:Gray_Code_Building.png|300px440px|thumb|right|Получение зеркального двоичного кода Грея.]]
{| border="0"
|align="left" colspan="4"|
<code>
buildCode(n):
GrayCode[1, n] = '''false'''0 GrayCode[2, n] = '''true''' 1 <font color=green> // Построение кода длины 1 </font> p = 2 <font color=green> // Где p {{---}} количество уже имеющихся кодов </font>
'''for''' i = 2 '''to''' n
t = p
p = p * 2
'''for''' k = (p / 2 + 1) '''to''' p
GrayCode[k] = GrayCode[t] <font color=green> // Отражение имеющихся кодов </font> GrayCode[t, n + 1 - i] = '''false'''0 GrayCode[k, n + 1 - i] = '''true''' 1 <font color=green> // Добавление 0 и 1 в начало </font>
t--
</code>
|}
Для любого <tex>x < 2^n</tex> выполняется <tex>\enskip L_x = 0M_x</tex> и, по условию, равно
<tex>L_x = 0(x_{n-1}x_{n-2} \dots ...x_{0} \oplus 0x_{n-1}x_{n-2}\dots ...x_{1})</tex> раскрыв скобки, получим новое выражение <tex>L_x</tex>:
<tex>= 0x_{n-1}x_{n-2}\dots ...x_{0} \oplus 00x_{n-1}x_{n-2}\dots ...x_{1}</tex> что равно (второе слагаемое равно первому, побитово сдвинутого вправо.)
<tex>= x \oplus (\lfloor x / 2 \rfloor)</tex>
Для любого <tex>x \geq 2^n</tex> выполняется <tex>\enskip 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 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_{1})</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>
Таким образом, шаг индукции доказан, следовательно, теорема верна.
}}
[[Файл:single_track.png|50px|thumb|right|Пример однодорожечного кода грея.]]
=== Сбалансированный код Грея ===
Несмотря на то, что зеркальный двоичный код Грея полезен во многих случаях, он не является оптимальным в некоторых ситуациях из-за отсутствия "однородности". В сбалансированном коде Грея, количество изменений в различных координатных позициях сделаны максимально приближенными настолько, насколько это возможно.
Чтобы показать это точнее, пусть <tex>G</tex> {{---}} это <tex>R</tex>-ичный полный цикл Грея, имеющий последовательность перехода <tex>(\delta_k)</tex>, которая определяет различие последующего бита в коде Грея с предыдущим(и различие последнего с первым); отсчёты переходов (спектры) <tex>G</tex> являются наборами целых чисел, определенных как <tex>\lambda_k = |\{ j \in \mathbb{Z}_{R^n} : \delta_j = k \}| \,</tex> для <tex> k \in \mathbb{Z}_R</tex>.
Код Грея является однородным или равномерно сбалансированным, если все его отсчёты переходов равны, и в этом случае у нас есть <tex>\lambda_k = R^n / n</tex> для всех <tex>k</tex>. Ясно, что при <tex>R = 2</tex>, такие коды существуют только при <tex>n = 2</tex>. В противном случае, если <tex>R^n</tex> не делится на <tex>n</tex> равномерно, то можно построить сбалансированные коды Грея, где каждый отсчёт перехода либо <tex>\lfloor R^n / n \rfloor </tex> либо <tex> \lceil R^n / n \rceil</tex>.
Чтобы снизить уровнень шума различных контактов не переключаясь в тот же момент времени, один датчик предпочтительно устанавливает дорожки так, что выход данных от контактов находится в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; для достижения точности хотя бы в <tex>1</tex> градус нужно, по крайней мере, <tex>360</tex> различных позиций на оборот, который требует минимум <tex>9</tex> бит данных, и тем самым такое же количество контактов.
'''Не путать''' с [[:Цепные_коды|цепными кодами.]], получаемых циклическим сдвигом
== Применение ==
Фрэнк Грей изобрел метод для преобразования аналоговых сигналов в отраженные двоичные кодовые группы с использованием аппарата на основе вакуумной трубки. Способ и устройство были запатентованы в 1953 году, а код получил название код Грея. "PCM трубка" {{---}} аппарат, запатентованный Греем, был сделан Раймондом У. Сирсом из (англ.) Bell Labs, работая с Греем и Уильямом М. Гудоллом.
