Код Грея

Отражённый двоичный код ( RBC ), также известный как отражённый двоичный код ( RB ) или код Грея в честь Фрэнка Грея , представляет собой упорядочение двоичной системы счисления , при котором два последовательных значения отличаются только одним битом (двоичной цифрой).

Например, представление десятичного значения "1" в двоичном коде обычно будет " 001 ", а "2" будет " 010 ". В коде Грея эти значения представлены как " 001 " и " 011 ". Таким образом, для увеличения значения с 1 до 2 требуется изменить только один бит вместо двух.

Коды Грея широко используются для предотвращения ложного выхода электромеханических переключателей и для облегчения исправления ошибок в цифровых коммуникациях, таких как цифровое наземное телевидение и некоторые системы кабельного телевидения . Использование кода Грея в этих устройствах помогает упростить логические операции и уменьшить количество ошибок на практике. ^[3]

Многие устройства указывают положение путем замыкания и размыкания переключателей. Если это устройство использует естественные двоичные коды , позиции 3 и 4 находятся рядом друг с другом, но все три бита двоичного представления различаются:

Десятичная дробь	Двоичный
...	...
3	011
4	100
...	...

Проблема с естественными двоичными кодами заключается в том, что физические переключатели не идеальны: очень маловероятно, что физические переключатели будут менять состояния точно синхронно. При переходе между двумя состояниями, показанными выше, все три переключателя меняют состояние. В короткий период, пока все меняются, переключатели будут считывать некоторую ложную позицию. Даже без дребезга клавиш переход может выглядеть как 011 — 001 — 101 — 100. Когда переключатели кажутся находящимися в позиции 001 , наблюдатель не может сказать, является ли это «реальной» позицией 1 или переходным состоянием между двумя другими позициями. Если выход подается в последовательную систему, возможно, через комбинационную логику , то последовательная система может хранить ложное значение.

Эту проблему можно решить, изменяя только один переключатель за раз, так что никогда не возникает никакой двусмысленности положения, что приводит к кодам, назначающим каждому из смежного набора целых чисел или каждому члену кольцевого списка слово символов таким образом, что никакие два кодовых слова не идентичны, а каждые два соседних кодовых слова отличаются ровно одним символом. Эти коды также известны как коды с единичным расстоянием , ^{[4] [5] [6] [7] [8]} с одним расстоянием , с одним шагом , монострофические ^{[9] [10] [7] [8]} или синкопические коды , ^[9] в отношении расстояния Хэмминга 1 между соседними кодами.

В принципе, может быть более одного такого кода для заданной длины слова, но термин «код Грея» был впервые применен к конкретному двоичному коду для неотрицательных целых чисел, двоично-отражённому коду Грея , или BRGC . Исследователь Bell Labs Джордж Р. Стибиц описал такой код в патентной заявке 1941 года, выданной в 1943 году. ^{[11] [12] [13]} Фрэнк Грей ввёл термин « отражённый двоичный код» в своей патентной заявке 1947 года, отметив, что у кода «ещё не было признанного названия». ^[14] Он вывел это название из того факта, что он «может быть построен из обычного двоичного кода с помощью своего рода процесса отражения».

В стандартной кодировке кода Грея младший бит следует повторяющемуся шаблону 2 включено, 2 выключено ( … 11001100 … ); следующая цифра — шаблону 4 включено, 4 выключено; i -й младший бит — шаблону 2 ⁱ включено 2 ⁱ выключено. Старшая цифра является исключением из этого правила: для n- битного кода Грея старшая цифра следует шаблону 2 ^{n -1} включено, 2 ^{n -1} выключено, что является той же (циклической) последовательностью значений, что и для второй по значимости цифры, но сдвинутой вперед на 2 ^{n -2} позиции. Четырехбитовая версия этого показана ниже:

Десятичная дробь	Двоичный	Серый
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

Для десятичного 15 код переходит в десятичный 0 всего с одним изменением переключателя. Это называется циклическим или смежным свойством кода. ^[15]

В современных цифровых коммуникациях коды Грея играют важную роль в исправлении ошибок . Например, в схеме цифровой модуляции , такой как QAM , где данные обычно передаются в символах из 4 бит или более, диаграмма созвездия сигнала организована таким образом, что битовые шаблоны, передаваемые соседними точками созвездия, отличаются только на один бит. Объединяя это с прямой коррекцией ошибок , способной исправлять однобитовые ошибки, приемник может исправить любые ошибки передачи, которые заставляют точку созвездия отклоняться в область соседней точки. Это делает систему передачи менее восприимчивой к шуму .

Несмотря на то, что Штибиц описал этот код ^{[11] [12] [13]} до Грея, отраженный двоичный код позже был назван в честь Грея другими, кто его использовал. Две разные патентные заявки 1953 года используют «код Грея» как альтернативное название для «отраженного двоичного кода»; ^{[16] [17]} одна из них также перечисляет среди названий «минимальный код ошибки» и «циклический перестановочный код». ^[17] Патентная заявка 1954 года ссылается на «код Грея телефонной компании Bell». ^[18] Другие названия включают «циклический двоичный код», ^[12] «циклический прогрессирующий код», ^{[19] [12]} «циклический перестановочный двоичный код» ^[20] или «циклический перестановочный двоичный код» (CPB). ^{[21] [22]}

Код Грея иногда ошибочно приписывают изобретателю электрического устройства 19 века Элише Грею . ^{[13] [23] [24] [25]}

Отражённые двоичные коды применялись для решения математических головоломок ещё до того, как они стали известны инженерам.

Двоично-отражённый код Грея представляет собой базовую схему классической китайской головоломки с кольцами , последовательного механического механизма головоломки, описанного французом Луи Гро в 1872 году. ^{[26] [13]}

Он может служить руководством по решению задачи «Ханойские башни» , основанной на игре француза Эдуарда Люка 1883 года. ^{[27] [28] [29] [30]} Аналогично, так называемые конфигурации игр «Башни Бухареста» и «Башни Клагенфурта» дают троичные и пятеричные коды Грея. ^[31]

Мартин Гарднер написал популярный отчет о коде Грея в своей колонке «Математические игры» в журнале Scientific American в августе 1972 года . ^[32]

Код также образует гамильтонов цикл на гиперкубе , где каждый бит рассматривается как одно измерение.

Когда французский инженер Эмиль Бодо перешел с использования 6-элементного (6-битного) кода на 5-элементный код для своей печатной телеграфной системы в 1875 ^[33] или 1876 году, ^{[34] [35]} он упорядочил алфавитные символы на своем печатном колесе, используя отраженный двоичный код, и назначил коды, используя только три бита для гласных. С гласными и согласными, отсортированными в их алфавитном порядке, ^{[36] [37] [38]} и другими символами, размещенными соответствующим образом, 5-битный код символа был признан отраженным двоичным кодом. ^[13] Этот код стал известен как код Бодо ^[39] и, с небольшими изменениями, был в конечном итоге принят как Международный телеграфный алфавит № 1 (ITA1, CCITT-1) в 1932 году. ^{[40] [41] [38]}

Примерно в то же время, в 1874 году, немецко-австрийский учёный Отто Шеффлер  [de] ^[42] продемонстрировал в Вене ещё один печатный телеграф, использовавший 5-битный отражённый двоичный код для той же цели. ^{[43] [13]}

Фрэнк Грей , который прославился изобретением метода передачи сигналов, который стал использоваться для совместимого цветного телевидения, изобрел метод преобразования аналоговых сигналов в отраженные двоичные кодовые группы с использованием аппарата на основе вакуумной трубки . Поданная в 1947 году, запатентованная методика и аппарат были получены в 1953 году, ^[14] и имя Грея закрепилось за кодами. Аппарат « ИКМ-трубка », который запатентовал Грей, был изготовлен Рэймондом У. Сирсом из Bell Labs, работавшим с Греем и Уильямом М. Гудоллом, который приписал Грею идею отраженного двоичного кода. ^[44]

Грей был больше всего заинтересован в использовании кодов для минимизации ошибок при преобразовании аналоговых сигналов в цифровые; его коды до сих пор используются для этой цели.

Коды Грея используются в линейных и вращательных позиционных кодерах ( абсолютных энкодерах и квадратурных энкодерах ) вместо взвешенного двоичного кодирования. Это позволяет избежать возможности того, что при изменении нескольких битов в двоичном представлении позиции произойдет неправильное считывание из-за того, что некоторые биты изменятся раньше других.

Например, некоторые вращающиеся энкодеры имеют диск, который имеет электропроводящий рисунок кода Грея на концентрических кольцах (дорожках). Каждая дорожка имеет неподвижный металлический пружинный контакт, который обеспечивает электрический контакт с токопроводящим рисунком кода. Вместе эти контакты производят выходные сигналы в форме кода Грея. Другие энкодеры используют бесконтактные механизмы на основе оптических или магнитных датчиков для производства выходных сигналов кода Грея.

Независимо от механизма или точности движущегося энкодера, ошибка измерения положения может возникнуть в определенных положениях (на границах кода), поскольку код может меняться в тот самый момент, когда он считывается (выбирается). Двоичный выходной код может вызвать значительные ошибки измерения положения, поскольку невозможно заставить все биты измениться в одно и то же время. Если в момент выборки положения некоторые биты изменились, а другие нет, выбранное положение будет неверным. В случае абсолютных энкодеров указанное положение может быть далеко от фактического положения, а в случае инкрементальных энкодеров это может испортить отслеживание положения.

Напротив, код Грея, используемый позиционными кодерами, гарантирует, что коды для любых двух последовательных позиций будут отличаться только на один бит и, следовательно, только один бит может измениться за раз. В этом случае максимальная ошибка позиции будет небольшой, указывая на позицию, смежную с фактической позицией.

Благодаря свойствам расстояния Хэмминга кодов Грея, их иногда используют в генетических алгоритмах . ^[15] Они очень полезны в этой области, поскольку мутации в коде допускают в основном постепенные изменения, но иногда изменение одного бита может вызвать большой скачок и привести к появлению новых свойств.

Коды Грея также используются для маркировки осей карт Карно с 1953 года ^{[45] [46] [47]} , а также в круговых диаграммах Хендлера с 1958 года ^{[48] [49] [50] [51] —} оба графических метода минимизации логических схем .

В современных цифровых коммуникациях 1D- и 2D-коды Грея играют важную роль в предотвращении ошибок перед применением исправления ошибок . Например, в схеме цифровой модуляции , такой как QAM , где данные обычно передаются в символах из 4 бит или более, диаграмма созвездия сигнала организована таким образом, что битовые шаблоны, передаваемые соседними точками созвездия, отличаются только на один бит. Объединяя это с прямой коррекцией ошибок , способной исправлять однобитовые ошибки, приемник может исправить любые ошибки передачи, которые заставляют точку созвездия отклоняться в область соседней точки. Это делает систему передачи менее восприимчивой к шуму .

• 
  Коды 4-PSK
• 
  Коды 8-PSK
• 
  Коды 16-QAM

Разработчики цифровой логики широко используют коды Грея для передачи многобитной информации о счете между синхронной логикой, работающей на разных тактовых частотах. Логика считается работающей в разных «тактовых доменах». Она имеет основополагающее значение для проектирования больших чипов, работающих на многих разных тактовых частотах.

Если система должна последовательно проходить все возможные комбинации состояний включения-выключения некоторого набора элементов управления, а изменения элементов управления требуют нетривиальных затрат (например, времени, износа, работы человека), код Грея минимизирует количество изменений настроек до всего одного изменения для каждой комбинации состояний. Примером может служить тестирование трубопроводной системы для всех комбинаций настроек ее управляемых вручную клапанов.

Можно построить сбалансированный код Грея, [ 52 ^] , который переворачивает каждый бит одинаково часто. Поскольку перевороты бит распределены равномерно, это оптимально следующим образом: сбалансированные коды Грея минимизируют максимальное количество переворотов бит для каждой цифры.

Джордж Р. Штибиц уже в 1941 году использовал отраженный двоичный код в двоичном устройстве подсчета импульсов. ^{[11] [12] [13]}

Типичное использование счетчиков кода Грея — построение буфера данных FIFO (первым пришел, первым вышел), который имеет порты чтения и записи, которые существуют в разных доменах синхронизации. Входные и выходные счетчики внутри такого двухпортового FIFO часто хранятся с использованием кода Грея, чтобы предотвратить захват недопустимых переходных состояний, когда счет пересекает домены синхронизации. ^[53] Обновленные указатели чтения и записи должны передаваться между доменами синхронизации, когда они изменяются, чтобы иметь возможность отслеживать пустое и полное состояние FIFO в каждом домене. Каждый бит указателей выбирается недетерминированно для этой передачи домена синхронизации. Таким образом, для каждого бита распространяется либо старое значение, либо новое значение. Следовательно, если в точке выборки изменяется более одного бита в многобитовом указателе, может быть распространено «неправильное» двоичное значение (ни новое, ни старое). Гарантируя, что может изменяться только один бит, коды Грея гарантируют, что единственными возможными выбранными значениями являются новое или старое многобитовое значение. Обычно используются коды Грея длиной, равной степени двойки.

Иногда цифровые шины в электронных системах используются для передачи величин, которые могут увеличиваться или уменьшаться только на единицу за раз, например, выход счетчика событий, который передается между доменами часов или в цифро-аналоговый преобразователь. Преимущество кодов Грея в этих приложениях заключается в том, что различия в задержках распространения множества проводов, которые представляют биты кода, не могут привести к тому, что полученное значение пройдет через состояния, которые находятся вне последовательности кода Грея. Это похоже на преимущество кодов Грея в конструкции механических энкодеров, однако источником кода Грея в этом случае является электронный счетчик. Сам счетчик должен считать в коде Грея, или, если счетчик работает в двоичном коде, то выходное значение счетчика должно быть повторно синхронизировано после того, как оно было преобразовано в код Грея, потому что когда значение преобразуется из двоичного кода в код Грея, ^{[nb 1]} возможно, что различия во времени прибытия двоичных битов данных в схему преобразования двоичного кода в код Грея будут означать, что код может кратковременно проходить через состояния, которые находятся вне последовательности. Добавление тактового регистра после схемы, преобразующей значение счетчика в код Грея, может привести к задержке в один такт, поэтому прямой подсчет в коде Грея может быть выгодным. ^[54]

Чтобы получить следующее значение счета в счетчике кода Грея, необходимо иметь некоторую комбинационную логику, которая увеличит текущее значение счета, которое хранится. Один из способов увеличить число в коде Грея — преобразовать его в обычный двоичный код, ^[55] добавить к нему единицу с помощью стандартного двоичного сумматора, а затем преобразовать результат обратно в код Грея. ^[56] Другие методы подсчета в коде Грея обсуждаются в отчете Роберта В. Дорана , включая получение выходных данных с первых защелок триггеров master-slave в двоичном счетчике пульсаций. ^[57]

Поскольку выполнение программного кода обычно вызывает шаблон доступа к памяти инструкций с локально последовательными адресами, кодирование шины с использованием адресации кода Грея вместо двоичной адресации может значительно сократить количество изменений состояния адресных битов, тем самым снижая энергопотребление ЦП в некоторых маломощных конструкциях. ^{[58] [59]}

Двоично-отражённый список кода Грея для n бит может быть сгенерирован рекурсивно из списка для n  − 1 бит путём отражения списка (т. е. перечисления записей в обратном порядке), добавления префикса к записям в исходном списке с двоичным 0 , добавления префикса к записям в отражённом списке с двоичной  1 , а затем конкатенации исходного списка с обратным списком. ^[13] Например, генерация списка n  = 3 из списка n  = 2:

2-битный список:	00 , 01 , 11 , 10
Отражено:		10 , 11 , 01 , 00
Добавляйте к старым записям префикс 0 :	000 , 001 , 011 , 010 ,
Добавляйте к новым записям префикс 1 :		110 , 111 , 101 , 100
Связанные:	000 , 001 , 011 , 010 ,	110 , 111 , 101 , 100

Однобитовый код Грея — это G ₁  = ( 0,1 ). Его можно рассматривать как рекурсивно построенный, как указано выше, из нуль-битового кода Грея G ₀  = (  Λ  ), состоящего из одной записи нулевой длины. Этот итеративный процесс генерации G _{n +1} из G _n делает очевидными следующие свойства стандартного отражающего кода:

• G _n — это перестановка чисел 0, ..., 2 ⁿ  − 1. (Каждое число встречается в списке ровно один раз.)
• G _n вкладывается как первая половина G _{n +1} .
• Следовательно, кодирование является стабильным в том смысле, что как только двоичное число появляется в G _, оно появляется в той же позиции во всех более длинных списках; поэтому имеет смысл говорить о значении отражающего кода Грея числа: G ( m ) = m -й отражающий код Грея, отсчитываемый от 0.
• Каждая запись в G _n отличается от предыдущей записи только одним битом. (Расстояние Хэмминга равно 1.)
• Последняя запись в G _n отличается от первой записи всего одним битом. (Код циклический.)

Эти характеристики предполагают простой и быстрый метод перевода двоичного значения в соответствующий код Грея. Каждый бит инвертируется, если следующий старший бит входного значения установлен в единицу. Это может быть выполнено параллельно с помощью операции сдвига битов и исключающего ИЛИ, если они доступны: n -й код Грея получается путем вычисления . Добавление бита 0 оставляет порядок кодовых слов неизменным, добавление бита 1 меняет порядок кодовых слов на противоположный. Если биты в позиции кодовых слов инвертированы, порядок соседних блоков кодовых слов меняется на противоположный. Например, если бит 0 инвертируется в последовательности кодовых слов из 3 бит, порядок двух соседних кодовых слов меняется на противоположный${\displaystyle n\oplus \left\lfloor {\tfrac {n}{2}}\right\rfloor }$${\displaystyle я}$${\displaystyle 2^{я}}$

000,001,010,011,100,101,110,111 → 001,000,011,010,101,100,111,110  (инвертировать бит 0)

Если бит 1 инвертирован, блоки из 2 кодовых слов меняют порядок:

000,001,010,011,100,101,110,111 → 010,011,000,001,110,111,100,101  (инвертировать бит 1)

Если бит 2 инвертирован, блоки из 4 кодовых слов меняют порядок:

000,001,010,011,100,101,110,111 → 100,101,110,111,000,001,010,011  (инвертировать бит 2)

Таким образом, выполнение исключающего или над битом в позиции с битом в позиции оставляет порядок кодовых слов нетронутым, если , и меняет порядок блоков кодовых слов на обратный, если . Теперь, это точно такая же операция, как метод отражения и префикса для генерации кода Грея.${\displaystyle b_{i}}$${\displaystyle я}$${\displaystyle b_{i+1}}$${\displaystyle я+1}$${\displaystyle b_{i+1}={\mathtt {0}}}$${\displaystyle 2^{i+1}}$${\displaystyle b_{i+1}={\mathtt {1}}}$

Аналогичный метод может быть использован для выполнения обратного перевода, но вычисление каждого бита зависит от вычисленного значения следующего более высокого бита, поэтому его нельзя выполнять параллельно. Предполагая, что - это th Gray-кодированный бит ( будучи самым значимым битом), а - th binary-coded bit ( будучи самым значимым битом), обратный перевод может быть задан рекурсивно: , и . Альтернативно, декодирование кода Грея в двоичное число можно описать как префиксную сумму битов в коде Грея, где каждая отдельная операция суммирования в префиксной сумме выполняется по модулю два.${\displaystyle g_{i}}$${\displaystyle я}$${\displaystyle g_{0}}$${\displaystyle b_{i}}$${\displaystyle я}$${\displaystyle b_{0}}$${\displaystyle b_{0}=g_{0}}$${\displaystyle b_{i}=g_{i}\oplus b_{i-1}}$

Чтобы построить двоично-отраженный код Грея итеративно, на шаге 0 начните с , а на шаге найдите позицию бита наименее значимой 1 в двоичном представлении и переверните бит в этой позиции в предыдущем коде, чтобы получить следующий код . Позиции битов начинаются с 0, 1, 0, 2, 0, 1, 0, 3, .... ^{[nb 2]} См. find first set для эффективных алгоритмов вычисления этих значений.${\displaystyle \mathrm {code} _{0}={\mathtt {0}}}$${\displaystyle я>0}$${\displaystyle я}$${\displaystyle \mathrm {код} _{i-1}}$${\displaystyle \mathrm {code} _{i}}$

Следующие функции в C преобразуют двоичные числа в соответствующие им коды Грея. Хотя может показаться, что преобразование Грея в двоичный код требует обработки каждого бита по одному за раз, существуют более быстрые алгоритмы. ^{[60] [55] [nb 1]}

typedef беззнаковое целое uint ;   // Эта функция преобразует беззнаковое двоичное число в отраженный двоичный код Грея. uint BinaryToGray ( uint num ) { return num ^ ( num >> 1 ); // Оператор >> — сдвиг вправо. Оператор ^ — исключающее или. }         // Эта функция преобразует отраженное двоичное число кода Грея в двоичное число. uint GrayToBinary ( uint num ) { uint mask = num ; while ( mask ) { // Каждый бит кода Грея подвергается операции «исключающее ИЛИ» со всеми более значимыми битами. mask >>= 1 ; num ^= mask ; } return num ; }                   // Более эффективная версия для кодов Грея длиной 32 бита или меньше за счет использования методов SWAR (SIMD в регистре). // Реализует параллельную префиксную функцию XOR. Операторы присваивания могут располагаться в любом порядке. // // Эту функцию можно адаптировать для более длинных кодов Грея, добавив шаги.uint GrayToBinary32 ( uint num ) { num ^= num >> 16 ; num ^= num >> 8 ; num ^= num >> 4 ; num ^= num >> 2 ; num ^= num >> 1 ; return num ; } // Вариант «четыре бита за раз» изменяет двоичное число (abcd)2 на (abcd)2 ^ (00ab)2, затем на (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2.                             

На более новых процессорах количество инструкций ALU на этапе декодирования можно сократить, воспользовавшись набором инструкций CLMUL . Если MASK — это постоянная двоичная строка единиц, заканчивающаяся одной нулевой цифрой, то умножение MASK без переноса с серым кодированием x всегда даст либо x, либо его побитовое отрицание.

На практике «код Грея» почти всегда относится к двоично-отражённому коду Грея (BRGC). Однако математики открыли и другие виды кодов Грея. Подобно BRGC, каждый из них состоит из списка слов, где каждое слово отличается от следующего только одной цифрой (каждое слово имеет расстояние Хэмминга 1 от следующего слова).

Можно построить двоичные коды Грея с n битами длиной менее 2 ⁿ , если длина четная. Одна из возможностей — начать со сбалансированного кода Грея и удалить пары значений либо в начале и в конце, либо в середине. ^[61] Последовательность OEIS A290772 ^[62] дает число возможных последовательностей Грея длиной 2 n , которые включают ноль и используют минимальное количество бит.

Существует много специализированных типов кодов Грея, отличных от двоично-отраженного кода Грея. Одним из таких типов кода Грея является n -арный код Грея , также известный как небулев код Грея . Как следует из названия, этот тип кода Грея использует небулевы значения в своих кодировках.

Например, 3-арный ( троичный ) код Грея будет использовать значения 0,1,2. ^[31] ( n ,  k ) -код Грея является n -арным кодом Грея с k цифрами. ^[63] Последовательность элементов в (3, 2)-коде Грея: 00,01,02,12,11,10,20,21,22. ( n ,  k )-код Грея может быть построен рекурсивно, как BRGC, или может быть построен итеративно . Алгоритм для итеративной генерации ( N ,  k )-кода Грея представлен (на языке C ):

// входы: основание, цифры, значение // выход: Грей // Преобразует значение в код Грея с заданным основанием и цифрами. // Итерация по последовательности значений приведет к последовательности // кодов Грея, в которой за раз изменяется только одна цифра. void toGray ( unsigned base , unsigned digits , unsigned value , unsigned gray [ digits ]) { unsigned baseN [ digits ]; // Сохраняет обычное число с основанием N, по одной цифре на запись unsigned i ; // Переменная цикла // Помещает обычное число с основанием N в массив baseN. Для основания 10 109 // будет храниться как [9,0,1] for ( i = 0 ; i < digits ; i ++ ) { baseN [ i ] = value % base ; value = value / base ; } // Преобразует обычное число с основанием N в эквивалент кода Грея. Обратите внимание, что // цикл начинается со старшей значащей цифры и идет вниз. unsigned shift = 0 ; while ( i -- ) { // Цифра Грея сдвигается вниз на сумму старших цифр. gray [ i ] = ( baseN [ i ] + shift ) % base ; shift = shift + base - gray [ i ]; // Вычитаем из base, чтобы сдвиг был положительным } } // ПРИМЕРЫ // вход: значение = 1899, основание = 10, цифры = 4 // выход: baseN[] = [9,9,8,1], gray[] = [0,1,7,1] // вход: значение = 1900, основание = 10, цифры = 4 // выход: baseN[] = [0,0,9,1], gray[] = [0,1,8,1]                                              

Существуют и другие алгоритмы кода Грея для ( n , k )-кодов Грея. Код ( n , k )-Грея, полученный с помощью вышеприведенного алгоритма, всегда цикличен; некоторые алгоритмы, такие как алгоритм Гуана ^[63], не обладают этим свойством, когда k нечетно. С другой стороны, хотя при этом методе изменяется только одна цифра за раз, она может изменяться путем переноса (циклирования от n  − 1 до 0). В алгоритме Гуана счет попеременно увеличивается и уменьшается, так что числовая разность между двумя цифрами кода Грея всегда равна единице.

Коды Грея не определены однозначно, поскольку перестановка столбцов такого кода также является кодом Грея. Вышеуказанная процедура создает код, в котором чем ниже значимость цифры, тем чаще она меняется, что делает его похожим на обычные методы подсчета.

См. также Перекошенная двоичная система счисления — вариант троичной системы счисления, в которой при каждом приращении изменяются не более двух цифр, поскольку каждое приращение может быть выполнено с помощью не более чем одной операции переноса цифры .

Хотя двоичный отраженный код Грея полезен во многих сценариях, в некоторых случаях он не является оптимальным из-за отсутствия «единообразия». ^[52] В сбалансированных кодах Грея число изменений в различных координатных позициях максимально близко. Чтобы сделать это более точным, пусть G будет R -ичным полным циклом Грея, имеющим последовательность переходов ; количество переходов ( спектр ) G представляет собой набор целых чисел, определяемых как${\displaystyle (\delta _{k})}$

${\displaystyle \lambda _{k}=|\{j\in \mathbb {Z} _{R^{n}}:\delta _{j}=k\}|\,,{\text{ для }}k\in \mathbb {Z} _{n}}$

Код Грея является однородным или равномерно сбалансированным , если все его счетчики переходов равны, в этом случае мы имеем для всех k . Очевидно, что когда , такие коды существуют только если n является степенью 2. ^[64] Если n не является степенью 2, можно построить хорошо сбалансированные двоичные коды, в которых разность между двумя счетчиками переходов не превышает 2; так что (объединяя оба случая) каждый счетчик переходов равен либо , либо . ^[52] Коды Грея также могут быть экспоненциально сбалансированными , если все их счетчики переходов являются смежными степенями двойки, и такие коды существуют для каждой степени двойки. ^[65]${\displaystyle \lambda _{k}={\tfrac {R^{n}}{n}}}$${\displaystyle R=2}$${\displaystyle 2\left\lfloor {\tfrac {2^{n}}{2n}}\right\rfloor }$${\displaystyle 2\left\lceil {\tfrac {2^{n}}{2n}}\right\rceil }$

Например, сбалансированный 4-битный код Грея имеет 16 переходов, которые можно равномерно распределить по всем четырем позициям (по четыре перехода на позицию), что делает его равномерно сбалансированным: ^[52]

0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0

0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0

0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0

0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1

тогда как сбалансированный 5-битный код Грея имеет всего 32 перехода, которые не могут быть равномерно распределены между позициями. В этом примере четыре позиции имеют по шесть переходов каждая, а одна — восемь: ^[52]

1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0

1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1

1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1

1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1

Теперь мы покажем конструкцию ^[66] и реализацию ^[67] для хорошо сбалансированных двоичных кодов Грея, которые позволяют нам генерировать n -разрядный сбалансированный код Грея для каждого n . Основной принцип заключается в индуктивном построении ( n  + 2)-разрядного кода Грея, заданного n -разрядным кодом Грея G таким образом, чтобы сохранялось сбалансированное свойство. Для этого мы рассмотрим разбиения на четное число L непустых блоков вида${\displaystyle G'}$${\displaystyle G=g_{0},\ldots ,g_{2^{n}-1}}$

${\displaystyle \left\{g_{0}\right\},\left\{g_{1},\ldots ,g_{k_{2}}\right\},\left\{g_{k_{2}+1},\ldots ,g_{k_{3}}\right\},\ldots ,\left\{g_{k_{L-2}+1},\ldots ,g_{-2}\right\},\left\{g_{-1}\right\}}$

где , , и ). Это разбиение индуцирует -значный код Грея, заданный как${\displaystyle k_{1}=0}$${\displaystyle k_{L-1}=-2}$${\displaystyle k_{L}\equiv -1{\pmod {2^{n}}}}$${\displaystyle (n+2)}$

${\displaystyle {\mathtt {00}}g_{0},}$

${\displaystyle {\mathtt {00}}g_{1},\ldots ,{\mathtt {00}}g_{k_{2}},{\mathtt {01}}g_{k_{2}},\ldots ,{\mathtt {01}}g_{1},{\mathtt {11}}g_{1},\ldots ,{\mathtt {11}}g_{k_{2}},}$

${\displaystyle {\mathtt {11}}g_{k_{2}+1},\ldots ,{\mathtt {11}}g_{k_{3}},{\mathtt {01}}g_{k_{3}},\ldots ,{\mathtt {01}}g_{k_{2}+1},{\mathtt {00}}g_{k_{2}+1},\ldots ,{\mathtt {00}}g_{k_{3}},\ldots ,}$

${\displaystyle {\mathtt {00}}g_{-2},{\mathtt {00}}g_{-1},{\mathtt {10}}g_{-1},{\mathtt {10}}g_ {-2},\ldots ,{\mathtt {10}}g_{0},{\mathtt {11}}g_{0},{\mathtt {11}}g_{-1},{\mathtt {01 }}g_{-1},{\mathtt {01}}g_{0}}$

Если мы определим кратности перехода

${\displaystyle m_{i}=\left|\left\{j:\delta _{k_{j}}=i,1\leq j\leq L\right\}\right|}$

чтобы быть числом раз, которое цифра в позиции i изменяется между последовательными блоками в разделе, тогда для ( n  + 2)-значного кода Грея, индуцированного этим разделом, спектр перехода равен${\displaystyle \lambda '_{i}}$

${\displaystyle \lambda '_{i}={\begin{cases}4\lambda _{i}-2m_{i},&{\text{если }}0\leq i<n\\L,&{\text{ в противном случае }}\end{cases}}}$

Деликатная часть этой конструкции заключается в том, чтобы найти адекватное разбиение сбалансированного n -разрядного кода Грея таким образом, чтобы код, индуцированный им, оставался сбалансированным, но для этого важны только кратности переходов; объединение двух последовательных блоков по цифровому переходу и разделение другого блока по другому цифровому переходу дает другой код Грея с точно таким же спектром переходов , так что можно, например, ^[65] обозначить первые переходы по цифре как те, которые попадают между двумя блоками. Однородные коды могут быть найдены, когда и , и эта конструкция может быть расширена также на R -арный случай. ^[66]${\displaystyle я}$${\displaystyle я}$${\displaystyle \lambda '_{i}}$${\displaystyle m_{i}}$${\displaystyle я}$${\displaystyle R\equiv 0{\pmod {4}}}$${\displaystyle R^{n}\equiv 0{\pmod {n}}}$

Длинные пробеги (или максимальный зазор ) Грея коды максимизируют расстояние между последовательными изменениями цифр в одной и той же позиции. То есть, минимальная длина пробега любого бита остается неизменной как можно дольше. ^[68]

Монотонные коды полезны в теории сетей взаимосвязей, особенно для минимизации расширения линейных массивов процессоров. ^[69] Если мы определим вес двоичной строки как количество единиц в строке, то, хотя мы, очевидно, не можем иметь код Грея со строго возрастающим весом, мы можем захотеть приблизиться к этому, заставив код пройти через два соседних веса, прежде чем достичь следующего.

Формализовать концепцию монотонных кодов Грея можно следующим образом: рассмотрим разбиение гиперкуба на уровни вершин, имеющих одинаковый вес, т.е.${\displaystyle Q_{n}=(V_{n},E_{n})}$

${\displaystyle V_{n}(i)=\{v\in V_{n}:v{\text{ имеет вес }}i\}}$

для . Эти уровни удовлетворяют . Пусть будет подграфом , индуцированным , и пусть будут ребрами в . Монотонный код Грея тогда является гамильтоновым путем в таким образом, что всякий раз, когда встречается раньше в пути, то .${\displaystyle 0\leq i\leq n}$${\displaystyle |V_{n}(i)|=\textstyle {\binom {n}{i}}}$${\displaystyle Q_{n}(i)}$${\displaystyle Q_{n}}$${\displaystyle V_{n}(i)\чашка V_{n}(i+1)}$${\displaystyle E_{n}(i)}$${\displaystyle Q_{n}(i)}$${\displaystyle Q_{n}}$${\displaystyle \delta _{1}\in E_{n}(i)}$${\displaystyle \delta _{2}\in E_{n}(j)}$${\displaystyle i\leq j}$

Элегантная конструкция монотонных n -значных кодов Грея для любого n основана на идее рекурсивного построения подпутей длины, имеющих ребра в . ^[69] Мы определяем , когда или , и${\displaystyle P_{n,j}}$${\displaystyle 2\textstyle {\binom {n}{j}}}$${\displaystyle E_{n}(j)}$${\displaystyle P_{1,0}=({\mathtt {0}},{\mathtt {1}})}$${\displaystyle P_{n,j}=\emptyset }$${\displaystyle j<0}$${\displaystyle j\geq n}$

${\displaystyle P_{n+1,j}={\mathtt {1}}P_{n,j-1}^{\pi _{n}},{\mathtt {0}}P_{n,j} }$

в противном случае. Здесь, является соответствующим образом определенной перестановкой и относится к пути P с его координатами, переставленными на . Эти пути приводят к двум монотонным n -значным кодам Грея и задаются как${\displaystyle \пи _{n}}$${\displaystyle P^{\пи}}$${\displaystyle \пи}$${\displaystyle G_{n}^{(1)}}$${\displaystyle G_{n}^{(2)}}$

${\displaystyle G_{n}^{(1)}=P_{n,0}P_{n,1}^{R}P_{n,2}P_{n,3}^{R}\cdots {\text{ и }}G_{n}^{(2)}=P_{n,0}^{R}P_{n,1}P_{n,2}^{R}P_{n,3}\cdots }$

Выбор , который гарантирует, что эти коды действительно являются кодами Грея, оказывается . Первые несколько значений показаны в таблице ниже.${\displaystyle \пи _{n}}$${\displaystyle \пи _{n}=E^{-1}\left(\пи _{n-1}^{2}\right)}$${\displaystyle P_{n,j}}$

Подпути в алгоритме Сэвиджа–Винклера

${\displaystyle P_{n,j}}$	j = 0	j = 1	j = 2	j = 3
п = 1	0, 1
п = 2	00, 01	10, 11
п = 3	000, 001	100, 110, 010, 011	101, 111
п = 4	0000, 0001	1000, 1100, 0100, 0110, 0010, 0011	1010, 1011, 1001, 1101, 0101, 0111	1110, 1111

Эти монотонные коды Грея могут быть эффективно реализованы таким образом, что каждый последующий элемент может быть сгенерирован за время O ( n ). Алгоритм проще всего описать с помощью сопрограмм .

Монотонные коды имеют интересную связь с гипотезой Ловаса , которая утверждает, что каждый связный вершинно-транзитивный граф содержит гамильтонов путь. Подграф "среднего уровня" является вершинно-транзитивным (то есть его группа автоморфизмов транзитивна, так что каждая вершина имеет одно и то же "локальное окружение" и не может быть дифференцирована от других, поскольку мы можем переименовать координаты, а также двоичные цифры, чтобы получить автоморфизм ) , и проблема нахождения гамильтонова пути в этом подграфе называется "проблемой средних уровней", которая может дать представление о более общей гипотезе. На вопрос был дан утвердительный ответ для , и предыдущая конструкция для монотонных кодов гарантирует гамильтонов путь длины не менее 0,839 ‍ N , где N - число вершин в подграфе среднего уровня. ^[70]${\displaystyle Q_{2n+1}(n)}$${\displaystyle n\leq 15}$

Другой тип кода Грея, код Беккета–Грея , назван в честь ирландского драматурга Сэмюэля Беккета , который интересовался симметрией . В его пьесе « Квад » четыре актера, и она разделена на шестнадцать временных периодов. Каждый период заканчивается тем, что один из четырех актеров выходит на сцену или покидает ее. Пьеса начинается и заканчивается пустой сценой, и Беккет хотел, чтобы каждое подмножество актеров появлялось на сцене ровно один раз. ^[71] Очевидно, что набор актеров, находящихся в данный момент на сцене, можно представить 4-битным двоичным кодом Грея. Однако Беккет наложил дополнительное ограничение на сценарий: он хотел, чтобы актеры входили и выходили так, чтобы актер, который был на сцене дольше всех, всегда был тем, кто выйдет. Затем актеров можно было бы представить в виде очереди « первым пришел, первым вышел» , так что (из актеров на сцене) актер, которого выводят из очереди, всегда был тем, кто был поставлен в очередь первым. ^[71] Беккет не смог найти код Беккета–Грея для своей пьесы, и действительно, исчерпывающий список всех возможных последовательностей показывает, что такого кода не существует для n = 4. Сегодня известно, что такие коды существуют для n = 2, 5, 6, 7 и 8, и не существуют для n = 3 или 4. Пример 8-битного кода Беккета–Грея можно найти в книге Дональда Кнута «Искусство компьютерного программирования» . ^[13] По словам Савады и Вонга, пространство поиска для n = 6 можно исследовать за 15 часов, и болееДля случая n = 7 найдено 9500 решений. ^[72]

Коды типа «змея в коробке» или «змеи » — это последовательности узлов индуцированных путей в n- мерном графе гиперкуба , а коды типа «катушка в коробке » или «катушки ^{» [73]} — это последовательности узлов индуцированных циклов в гиперкубе. Рассматриваемые как коды Грея, эти последовательности обладают свойством обнаруживать любую однобитовую ошибку кодирования. Коды этого типа были впервые описаны Уильямом Х. Каутцем в конце 1950-х годов ^[5] ; с тех пор было проведено много исследований по поиску кода с максимально возможным числом кодовых слов для заданного измерения гиперкуба.

Еще одним видом кода Грея является однодорожечный код Грея (STGC), разработанный Норманом Б. Спеддингом ^{[74] [75]} и усовершенствованный Хилтгеном, Патерсоном и Брандестини в работе «Однодорожечные коды Грея» (1996). ^{[76] [77]} STGC представляет собой циклический список из P уникальных двоичных кодировок длины n, такой, что два последовательных слова отличаются ровно в одной позиции, и когда список рассматривается как матрица P  ×  n , каждый столбец является циклическим сдвигом первого столбца. ^[78]

Название происходит от их использования с вращающимися энкодерами , где несколько дорожек считываются контактами, в результате чего для каждой из них выводится значение 0 или 1. Чтобы уменьшить шум из-за того, что разные контакты не переключаются в один и тот же момент времени, желательно настроить дорожки так, чтобы выходные данные контактов были в коде Грея. Чтобы получить высокую угловую точность, нужно много контактов; чтобы достичь по крайней мере точности 1°, нужно по крайней мере 360 различных положений на оборот, что требует минимум 9 бит данных и, следовательно, того же количества контактов.

Если все контакты размещены в одном и том же угловом положении, то для получения стандартного BRGC с точностью не менее 1° требуется 9 дорожек. Однако если производитель перемещает контакт в другое угловое положение (но на то же расстояние от центрального вала), то соответствующий «кольцевой рисунок» необходимо повернуть на тот же угол, чтобы получить тот же выходной сигнал. Если старший бит (внутреннее кольцо на рисунке 1) достаточно повернуть, он точно соответствует следующему кольцу. Поскольку оба кольца тогда идентичны, внутреннее кольцо можно вырезать, а датчик для этого кольца переместить на оставшееся идентичное кольцо (но смещенное на этот угол относительно другого датчика на этом кольце). Эти два датчика на одном кольце образуют квадратурный энкодер. Это уменьшает количество дорожек для углового энкодера с «разрешением 1°» до 8 дорожек. Уменьшить количество дорожек еще больше с BRGC невозможно.

В течение многих лет Торстен Силке ^[79] и другие математики считали, что невозможно кодировать положение на одной дорожке так, чтобы последовательные положения отличались только на одном датчике, за исключением 2-сенсорного, 1-дорожечного квадратурного энкодера. Поэтому для приложений, где 8 дорожек были слишком громоздкими, люди использовали однодорожечные инкрементальные энкодеры (квадратурные энкодеры) или 2-дорожечные энкодеры «квадратурный энкодер + опорная метка».

Однако Норман Б. Спеддинг зарегистрировал патент в 1994 году с несколькими примерами, показывающими, что это возможно. ^[74] Хотя невозможно различить 2 ⁿ позиций с помощью n датчиков на одной дорожке, можно различить почти столько же. Этцион и Патерсон предполагают, что когда n само по себе является степенью 2, n датчиков могут различить максимум 2 ⁿ  − 2 n позиций, а для простого n предел составляет 2 ⁿ  − 2 позиций. ^[80] Авторы продолжили генерировать 504-позиционный однодорожечный код длины 9, который, по их мнению, является оптимальным. Поскольку это число больше, чем 2 ⁸ = 256, для любого кода требуется более 8 датчиков, хотя BRGC может различить 512 позиций с помощью 9 датчиков.

STGC для P  = 30 и n  = 5 воспроизведен здесь:

Однопутевой код Грея на 30 позиций

Угол	Код		Угол	Код		Угол	Код		Угол	Код		Угол	Код
0°	10000		72°	01000		144°	00100		216°	00010		288°	00001
12°	10100		84°	01010		156°	00101		228°	10010		300°	01001
24°	11100		96°	01110		168°	00111		240°	10011		312°	11001
36°	11110		108°	01111		180°	10111		252°	11011		324°	11101
48°	11010		120°	01101		192°	10110		264°	01011		336°	10101
60°	11000		132°	01100		204°	00110		276°	00011		348°	10001

Каждый столбец представляет собой циклический сдвиг первого столбца, и от любой строки к следующей строке изменяется только один бит. ^[81] Однодорожечная природа (как кодовая цепочка) полезна при изготовлении этих колес (по сравнению с BRGC), поскольку требуется только одна дорожка, что снижает их стоимость и размер. Код Грея полезен (по сравнению с цепочными кодами , также называемыми последовательностями Де Брейна ), поскольку в любой момент времени будет меняться только один датчик, поэтому неопределенность при переходе между двумя дискретными состояниями будет составлять только плюс или минус одну единицу углового измерения, которую способно разрешить устройство. ^[82]

С тех пор, как был добавлен этот пример с углом 30 градусов, возник большой интерес к примерам с более высоким угловым разрешением. В 2008 году Гэри Уильямс ^[83] на основе предыдущей работы ^[80] открыл 9-битный однодорожечный код Грея, который дает разрешение 1 градус. Этот код Грея использовался для разработки реального устройства, которое было опубликовано на сайте Thingiverse . Это устройство ^[84] было разработано etzenseep (Флориан Бауэр) в сентябре 2022 года.

STGC для P  = 360 и n  = 9 воспроизведен здесь:

Однопутный код Грея на 360 позиций

Угол	Код		Угол	Код		Угол	Код		Угол	Код		Угол	Код		Угол	Код		Угол	Код		Угол	Код		Угол	Код
0°	100000001		40°	000000011		80°	000000110		120°	000001100		160°	000011000		200°	000110000		240°	001100000		280°	011000000		320°	110000000
1°	110000001		41°	100000011		81°	000000111		121°	000001110		161°	000011100		201°	000111000		241°	001110000		281°	011100000		321°	111000000
2°	111000001		42°	110000011		82°	100000111		122°	000001111		162°	000011110		202°	000111100		242°	001111000		282°	011110000		322°	111100000
3°	111000011		43°	110000111		83°	100001111		123°	000011111		163°	000111110		203°	001111100		243°	011111000		283°	111110000		323°	111100001
4°	111000111		44°	110001111		84°	100011111		124°	000111111		164°	001111110		204°	011111100		244°	111111000		284°	111110001		324°	111100011
5°	111001111		45°	110011111		85°	100111111		125°	001111111		165°	011111110		205°	111111100		245°	111111001		285°	111110011		325°	111100111
6°	111011111		46°	110111111		86°	101111111		126°	011111111		166°	111111110		206°	111111101		246°	111111011		286°	111110111		326°	111101111
7°	111011011		47°	110110111		87°	101101111		127°	011011111		167°	110111110		207°	101111101		247°	011111011		287°	111110110		327°	111101101
8°	101011011		48°	010110111		88°	101101110		128°	011011101		168°	110111010		208°	101110101		248°	011101011		288°	111010110		328°	110101101
9°	101011111		49°	010111111		89°	101111110		129°	011111101		169°	111111010		209°	111110101		249°	111101011		289°	111010111		329°	110101111
10°	101011101		50°	010111011		90°	101110110		130°	011101101		170°	111011010		210°	110110101		250°	101101011		290°	011010111		330°	110101110
11°	101010101		51°	010101011		91°	101010110		131°	010101101		171°	101011010		211°	010110101		251°	101101010		291°	011010101		331°	110101010
12°	101010111		52°	010101111		92°	101011110		132°	010111101		172°	101111010		212°	011110101		252°	111101010		292°	111010101		332°	110101011
13°	101110111		53°	011101111		93°	111011110		133°	110111101		173°	101111011		213°	011110111		253°	111101110		293°	111011101		333°	110111011
14°	001110111		54°	011101110		94°	111011100		134°	110111001		174°	101110011		214°	011100111		254°	111001110		294°	110011101		334°	100111011
15°	001010111		55°	010101110		95°	101011100		135°	010111001		175°	101110010		215°	011100101		255°	111001010		295°	110010101		335°	100101011
16°	001011111		56°	010111110		96°	101111100		136°	011111001		176°	111110010		216°	111100101		256°	111001011		296°	110010111		336°	100101111
17°	001011011		57°	010110110		97°	101101100		137°	011011001		177°	110110010		217°	101100101		257°	011001011		297°	110010110		337°	100101101
18°	001011001		58°	010110010		98°	101100100		138°	011001001		178°	110010010		218°	100100101		258°	001001011		298°	010010110		338°	100101100
19°	001111001		59°	011110010		99°	111100100		139°	111001001		179°	110010011		219°	100100111		259°	001001111		299°	010011110		339°	100111100
20°	001111101		60°	011111010		100°	111110100		140°	111101001		180°	111010011		220°	110100111		260°	101001111		300°	010011111		340°	100111110
21°	000111101		61°	001111010		101°	011110100		141°	111101000		181°	111010001		221°	110100011		261°	101000111		301°	010001111		341°	100011110
22°	000110101		62°	001101010		102°	011010100		142°	110101000		182°	101010001		222°	010100011		262°	101000110		302°	010001101		342°	100011010
23°	000100101		63°	001001010		103°	010010100		143°	100101000		183°	001010001		223°	010100010		263°	101000100		303°	010001001		343°	100010010
24°	000101101		64°	001011010		104°	010110100		144°	101101000		184°	011010001		224°	110100010		264°	101000101		304°	010001011		344°	100010110
25°	000101001		65°	001010010		105°	010100100		145°	101001000		185°	010010001		225°	100100010		265°	001000101		305°	010001010		345°	100010100
26°	000111001		66°	001110010		106°	011100100		146°	111001000		186°	110010001		226°	100100011		266°	001000111		306°	010001110		346°	100011100
27°	000110001		67°	001100010		107°	011000100		147°	110001000		187°	100010001		227°	000100011		267°	001000110		307°	010001100		347°	100011000
28°	000010001		68°	000100010		108°	001000100		148°	010001000		188°	100010000		228°	000100001		268°	001000010		308°	010000100		348°	100001000
29°	000011001		69°	000110010		109°	001100100		149°	011001000		189°	110010000		229°	100100001		269°	001000011		309°	010000110		349°	100001100
30°	000001001		70°	000010010		110°	000100100		150°	001001000		190°	010010000		230°	100100000		270°	001000001		310°	010000010		350°	100000100
31°	100001001		71°	000010011		111°	000100110		151°	001001100		191°	010011000		231°	100110000		271°	001100001		311°	011000010		351°	110000100
32°	100001101		72°	000011011		112°	000110110		152°	001101100		192°	011011000		232°	110110000		272°	101100001		312°	011000011		352°	110000110
33°	100000101		73°	000001011		113°	000010110		153°	000101100		193°	001011000		233°	010110000		273°	101100000		313°	011000001		353°	110000010
34°	110000101		74°	100001011		114°	000010111		154°	000101110		194°	001011100		234°	010111000		274°	101110000		314°	011100001		354°	111000010
35°	010000101		75°	100001010		115°	000010101		155°	000101010		195°	001010100		235°	010101000		275°	101010000		315°	010100001		355°	101000010
36°	010000111		76°	100001110		116°	000011101		156°	000111010		196°	001110100		236°	011101000		276°	111010000		316°	110100001		356°	101000011
37°	010000011		77°	100000110		117°	000001101		157°	000011010		197°	000110100		237°	001101000		277°	011010000		317°	110100000		357°	101000001
38°	010000001		78°	100000010		118°	000000101		158°	000001010		198°	000010100		238°	000101000		278°	001010000		318°	010100000		358°	101000000
39°	000000001		79°	000000010		119°	000000100		159°	000001000		199°	000010000		239°	000100000		279°	001000000		319°	010000000		359°	100000000

Начальный и конечный углы для 20 дорожек для однодорожечного кода Грея с 9 датчиками, разнесенными на 40°

Начальный угол	Конечный угол	Длина
3	4	2
23	28	6
31	37	7
44	48	5
56	60	5
64	71	8
74	76	3
88	91	4
94	96	3
99	104	6
110	115	6
131	134	4
138	154	17
173	181	9
186	187	2
220	238	19
242	246	5
273	279	7
286	289	4
307	360	54

Двумерные коды Грея используются в коммуникации для минимизации количества ошибок битов в квадратурной амплитудной модуляции (QAM) соседних точек в созвездии . При типичном кодировании горизонтальные и вертикальные соседние точки созвездия отличаются на один бит, а диагональные соседние точки отличаются на 2 бита. ^[85]

Двумерные коды Грея также используются в схемах идентификации местоположения , где код будет применяться к картам местности, таким как проекция Меркатора земной поверхности, и соответствующая циклическая двумерная функция расстояния, такая как метрика Мангейма, будет использоваться для вычисления расстояния между двумя закодированными местоположениями, тем самым объединяя характеристики расстояния Хэмминга с циклическим продолжением проекции Меркатора. ^[86]

Если из этого значения извлекается подчасть определенного кодового значения, например, последние 3 бита 4-битного кода Грея, то полученный код будет «избыточным кодом Грея». Этот код демонстрирует свойство обратного отсчета в этих извлеченных битах, если исходное значение еще больше увеличивается. Причина этого в том, что значения, закодированные Греем, не демонстрируют поведение переполнения, известное из классического двоичного кодирования, при увеличении за пределы «наивысшего» значения.

Пример: наивысший 3-битный код Грея, 7, кодируется как (0)100. Добавление 1 дает число 8, кодируемое Греем как 1100. Последние 3 бита не переполняются и отсчитываются в обратном порядке, если вы еще больше увеличиваете исходный 4-битный код.

При работе с датчиками, которые выводят несколько значений в кодировке Грея последовательно, следует обращать внимание на то, выдает ли датчик эти несколько значений, закодированных в одном коде Грея, или как отдельные значения, поскольку в противном случае может показаться, что значения отсчитываются в обратном порядке, когда ожидается «переполнение».

Биективное отображение { 0 ↔ 00 , 1 ↔ 01 , 2 ↔ 11 , 3 ↔ 10 } устанавливает изометрию между метрическим пространством над конечным полем с метрикой, заданной расстоянием Хэмминга , и метрическим пространством над конечным кольцом (обычная модулярная арифметика ) с метрикой, заданной расстоянием Ли . Отображение соответствующим образом расширяется до изометрии пространств Хэмминга и . Его важность заключается в установлении соответствия между различными «хорошими», но не обязательно линейными кодами , такими как изображения карты Грея в кольцевых линейных кодов из . ^{[87] [88]} ${\displaystyle \mathbb {Z} _{2}^{2}}$ ${\displaystyle \mathbb {Z} _{4}}$ ${\displaystyle \mathbb {Z} _{2}^{2m}}$${\displaystyle \mathbb {Z} _{4}^{m}}$${\displaystyle \mathbb {Z} _{2}^{2}}$${\displaystyle \mathbb {Z} _{4}}$

Этот раздел может содержать чрезмерное количество цитат . Подробности следующие: Слишком много ссылок затрудняют чтение текста. Пожалуйста, помогите удалить некачественные или нерелевантные цитаты . ( Март 2021 ) ( Узнайте, как и когда удалять это сообщение )

Существует ряд двоичных кодов, похожих на коды Грея, в том числе:

• Коды Datex, также известные как коды Джаннини (1954), описанные Карлом П. Сполдингом ^{[9] [89] [90] [91] [92] [8],} используют вариант кода О'Брайена II.
• Коды, используемые Вареком (около 1954 г.), ^{[93] [94] [95] [96]} используют вариант кода О'Брайена I, а также варианты кода Грея с основанием 12 и основанием 16.
• Код Лукала (1959) ^{[1] [2] [57]} также известный как модифицированный отраженный двоичный код (MRB) ^{[1] [2] [nb 3]}
• Код Гиллхэма (1961/1962), ^{[90] [97] [8] [98] [99]} использует вариант кода Datex и кода О'Брайена II.
• Код Лесли и Рассела (1964) ^{[100] [10] [101] [97]}
• Код Королевского радиолокационного учреждения ^[97]
• Код Хокласа (1988) ^{[102] [103] [104]}

Следующие двоично-десятичные коды (BCD) также являются вариантами кода Грея:

• Код Петерика (1953), ^{[19] [105] [106] [107] [55] [103] [nb 4]} также известный как код Королевского авиационного учреждения (RAE). ^[108]
• Коды О'Брайена I и II (1955) ^{[109] [110] [111] [91] [92] [103]} (Код О'Брайена типа I ^{[nb 5]} уже был описан Фредериком А. Фоссом из IBM ^{[112] [113]} и использовался Вареком в 1954 году. Позже он был также известен как код Уоттса или отраженный десятичный код Уоттса (WRD) и иногда неоднозначно упоминается как отраженный двоичный модифицированный код Грея. ^{[114] [20] [21] [115] [116 ] [ 117] [118] [119] [120] [nb 1] [nb 3]} Код О'Брайена типа II уже использовался Datex в 1954 году. ^{[nb 4]} )
• Код Грея с избыточным числом 3 (1956) ^[121] (он же код Грея с избыточным числом 3 , ^{[91] [92] [8]} Код Грея с избыточным числом 3, код рефлексного избыточного числа 3, избыточный код Грея, ^[103] Код Грея с избыточным числом 10, код Грея с избыточным числом 3 или код Грея–Стибитца), описанный Фрэнком П. Терви-младшим из ITT . ^[121]
• Коды Томпкинса I и II (1956) ^{[4] [110] [111] [91] [92] [103]}
• Код Гликсона (1957), иногда неоднозначно называемый также модифицированным кодом Грея ^{[122] [55] [123] [124] [110] [111] [91] [92] [103] [nb 3] [nb 5]}

• Регистр сдвига с линейной обратной связью
• Последовательность Де Брейна
• Алгоритм Штейнхауза–Джонсона–Троттера – алгоритм, который генерирует коды Грея для факториальной системы счисления.
• Код минимального расстояния
• Последовательность Пруэ–Туэ–Морзе – относится к обратному коду Грея
• формула Райзера
• кривая Гильберта