Код Грея

Отражение двоичного кода ( RBC ), также известный как отраженный двоичный ( RB ) или код Грея после Frank Gray , является упорядочение двоичной системе счисления таким образом, что две последовательные значения различаются только в одной битовой (двоичный разряд).

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

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

Мотивация и имя [ править ]

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

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

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

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

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

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

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

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

Код Грея иногда приписывают, неправильно, ^[12] , чтобы Элиша Грей . ^{[22] [23] [24]}

История и практическое применение [ править ]

Математические головоломки [ править ]

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

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

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

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

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

Коды телеграфии [ править ]

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

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

Преобразование аналого-цифрового сигнала [ править ]

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

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

Датчики положения [ править ]

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

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

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

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

Генетические алгоритмы [ править ]

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

Минимизация логической схемы [ править ]

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

Исправление ошибок [ править ]

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

Связь между доменами часов [ править ]

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

Циклическое переключение состояний с минимальными усилиями [ править ]

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

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

Счетчики кода Грея и арифметика [ править ]

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

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

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

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

Адресация кода Грея [ править ]

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

Построение n- битного кода Грея [ править ]

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

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

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

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

{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)

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

Аналогичный метод можно использовать для выполнения обратного преобразования, но вычисление каждого бита зависит от вычисленного значения следующего более высокого бита, поэтому его нельзя выполнять параллельно. Предполагая, что это -й бит, закодированный по Грею ( являющийся наиболее значимым битом), и является -м битом с двоичным кодированием ( являющимся наиболее значимым битом), обратное преобразование может быть выполнено рекурсивно:, и . В качестве альтернативы декодирование кода Грея в двоичное число можно описать как префиксную сумму битов в коде Грея, где каждая отдельная операция суммирования в префиксной сумме выполняется по модулю два.${\displaystyle g_{i}}$${\displaystyle i}$${\displaystyle g_{0}}$${\displaystyle b_{i}}$${\displaystyle i}$${\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]} См. " Найти первый набор" для получения информации об эффективных алгоритмах вычисления этих значений.${\displaystyle \mathrm {code} _{0}=0}$${\displaystyle i>0}$${\displaystyle i}$${\displaystyle \mathrm {code} _{i-1}}$${\displaystyle \mathrm {code} _{i}}$

Преобразование в код Грея и обратно [ править ]

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

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

Специальные типы кодов Грея [ править ]

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

n -аричный код Грея [ править ]

 0 → 000 1 → 001 2 → 002 10 → 012 11 → 011 12 → 010 20 → 020 21 → 021 22 → 022100 → 122101 → 121102 → 120110 → 110111 → 111112 → 112120 → 102121 → 101122 → 100200 → 200201 → 201202 → 202210 → 212211 → 211212 → 210220 → 220221 → 221222 → 222

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

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

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

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

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

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

Сбалансированный код Грея [ править ]

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

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

Код Грея является однородным или равномерно сбалансированным, если все его счетчики переходов равны, и в этом случае мы имеем для всех k . Ясно, что когда такие коды существуют, только если n является степенью 2. В противном случае, если n не делится равномерно, можно построить хорошо сбалансированные коды, в которых каждый счетчик переходов равен или . ^[51] Коды Грея также могут быть экспоненциально сбалансированы, если все их счетчики переходов являются смежными степенями двойки, и такие коды существуют для каждой степени двойки. ^[61]${\displaystyle \lambda _{k}=R^{n}/n}$${\displaystyle R=2}$${\displaystyle R^{n}}$${\displaystyle \lfloor R^{n}/n\rfloor }$${\displaystyle \lceil R^{n}/n\rceil }$

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

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 00 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 перехода, которые не могут быть равномерно распределены по позициям. В этом примере четыре позиции имеют шесть переходов каждая, а одна - восемь: ^[51]

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 00 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 01 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 11 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

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

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

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

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

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

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

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

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

${\displaystyle \lambda '_{i}={\begin{cases}4\lambda _{i}-2m_{i},&{\text{if }}0\leq i<n\\L,&{\text{ otherwise }}\end{cases}}}$

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

Монотонные коды Грея [ править ]

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

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

${\displaystyle V_{n}(i)=\{v\in V_{n}:v{\text{ has weight }}i\}}$

для . Эти уровни удовлетворяют . Позвольте быть подграфом индуцированного , и пусть быть ребрами в . Монотонный код Грея тогда является гамильтоновым путем в таком, что всякий раз, когда он идет раньше , тогда .${\displaystyle 0\leq i\leq n}$${\displaystyle |V_{n}(i)|={\binom {n}{i}}}$${\displaystyle Q_{n}(i)}$${\displaystyle Q_{n}}$${\displaystyle V_{n}(i)\cup 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 основана на идее рекурсивного построения подпутей длины, имеющих ребра . ^[64] Мы определяем , когда или , и${\displaystyle P_{n,j}}$${\displaystyle 2{\binom {n}{j}}}$${\displaystyle E_{n}(j)}$${\displaystyle P_{1,0}=(0,1)}$${\displaystyle P_{n,j}=\emptyset }$${\displaystyle j<0}$${\displaystyle j\geq n}$

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

иначе. Здесь - подходящим образом определенная перестановка, относящаяся к пути P с его координатами, переставленными на . Эти пути приводят к двум монотонным n -значных кодов Грея и задаются${\displaystyle \pi _{n}}$${\displaystyle P^{\pi }}$${\displaystyle \pi }$${\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{ and }}G_{n}^{(2)}=P_{n,0}^{R}P_{n,1}P_{n,2}^{R}P_{n,3}\cdots }$

Выбор того, который гарантирует, что эти коды действительно являются кодами Грея, оказывается правильным . Первые несколько значений показаны в таблице ниже.${\displaystyle \pi _{n}}$${\displaystyle \pi _{n}=E^{-1}(\pi _{n-1}^{2})}$${\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 ). Алгоритм проще всего описать с помощью сопрограмм .

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

Код Беккета – Грея [ править ]

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

Коды змейки в коробке [ править ]

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

Однодорожечный код Грея [ править ]

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

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

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

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

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

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

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

Двумерный код Грея [ править ]

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

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

Изометрия серого [ править ]

Биективное отображение {0 ↔ 00, 1 ↔ 01, 2 ↔ 11, 3 ↔ 10} устанавливает изометрию между метрическим пространством над конечным полем с метрикой, заданной расстоянием Хэмминга, и метрическим пространством над конечным кольцом (обычное модульная арифметика ) с метрикой, заданной расстоянием Ли . Отображение подходящим образом продолжается до изометрии пространств Хэмминга и . Его важность заключается в установлении соответствия между различными «хорошо» , но не обязательно линейные коды как Серо-карты изображений в из кольцевых линейных кодов с . ^[80]${\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}}$^[81]

Связанные коды [ править ]

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

• Коды Datex, также известные как коды Джаннини (1954), как описано Карлом П. Сполдингом, ^{[8] [82] [83] [84] [85] [7],} используют вариант кода О'Брайена II .
• Коды, используемые Вареком (около 1954 г.), ^{[86] [87] [88] [89],} используют вариант кода О'Брайена I, а также варианты кода Грея с основанием 12 и 16.
• Lucal code (1959) ^{[1] [2] [56]} или модифицированный отраженный двоичный код (MRB) ^{[1] [2] [nb 3]}
• В коде Гиллхема (1961/1962), ^{[83] [90] [7] [91] [92]} используется вариант кода Datex и кода О'Брайена II .
• Код Лесли и Рассела (1964) ^{[93] [9] [94] [90]}
• Код компании Royal Radar ^[90]
• Кодекс Хокласа (1988) ^{[95] [96] [97]}

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

• Код Петерика (1953), ^{[18] [98] [99] [100] [54] [96] [nb 4],} также известный как код Royal Aircraft Establishment (RAE). ^[101]
• Коды О'Брайена I и II (1955) ^{[102] [103] [104] [84] [85] [96]} (Код О'Брайена типа I ^{[nb 5]} уже был описан Фредериком А. Фоссом из IBM ^{[105] [106]} и использовался Вареком в 1954 году. Позже он был также известен как код Уоттса или отраженный десятичный код Уоттса (WRD) и иногда неоднозначно упоминается как отраженный двоичный модифицированный код Грея ^{[107] [19]. [20] [108] [109] [110] [111] [112] [113] [nb 1] [nb 3]} Код О'Брайена типа II уже использовался Datex в 1954 году. ^{[Nb 4]})
• Код Грея с избытком-3 (1956) ^[114] (он же код с избытком Грея -3 , ^{[84] [85] [7]} Код с избытком Грея с 3, рефлексный код с избытком-3, код с избытком Грея, ^[96] Код с избытком Грея , Код Грея-10-избыток-3 или код Грея – Стибица), описанный Фрэнком П. Терви-младшим из ITT . ^[114]
• Коды Томпкинса I и II (1956) ^{[3] [103] [104] [84] [85] [96]}
• Код Гликсона (1957), иногда неоднозначно также называемый модифицированным кодом Грея ^{[115] [54] [116] [117] [103] [104] [84] [85] [96] [nb 3] [nb 5]]}

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]