Код Грея - Gray code

В отраженный двоичный код (РБК), также известный как отраженный двоичный (РБ) или же Код Грея после Фрэнк Грей, это порядок двоичная система счисления такие, что два последовательных значения отличаются только одним кусочек (двоичный символ).

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

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

Имя

Патент Грея вводит термин «отраженный двоичный код».

Bell Labs Исследователь Фрэнк Грей ввел термин отраженный двоичный код в своей патентной заявке 1947 года, отмечая, что у кода «пока нет признанного названия».^[3] Он получил свое название от того факта, что он «может быть построен из обычного двоичного кода посредством своего рода процесса отражения».

Код был позже назван в честь Грея другими, кто его использовал. Две разные патентные заявки 1953 года используют «код Грея» в качестве альтернативного названия «отраженного двоичного кода»;^[4][5] в одном из них также указаны «минимальный код ошибки» и «код циклической перестановки» среди имен.^[5] В заявке на патент 1954 года упоминается «код Грея по телефону Bell».^[6] Другие названия включают «циклический двоичный код», «код циклической прогрессии»,^[7][8] "циклическая перестановка двоичного кода"^[9] или «циклический переставленный двоичный код» (CPB).^[10][11]

Мотивация

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

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

Отраженный двоичный код решает эту проблему, изменяя только один переключатель за раз, поэтому нет двусмысленности положения:

Визуализируется как обход вершины из тессеракт

Код Грея для десятичного числа 15 переключается на десятичный 0 с одним переключением переключателя. Это называется «циклическим» свойством кода Грея. В стандартном кодировании Грея младший значащий бит следует повторяющейся схеме: 2 вкл., 2 выкл. ( … 11001100 … ); следующая цифра - образец 4 вкл., 4 выкл .; n-й младший бит шаблон ${ Displaystyle 2 ^ {п}}$ на ${ Displaystyle 2 ^ {п}}$ выключенный.

Более формально Код Грея это код, присваивающий каждому из непрерывного набора целые числа или для каждого члена кругового списка - слово символов, такое, что никакие два кодовых слова не являются идентичными, а каждые два соседних кодовых слова отличаются ровно на один символ. Эти коды также известны как единичное расстояние,^{[12][13][14][8][15][16]} на одно расстояние, один шаг, монострофический^{[17][18][15][16]} или же синкопические коды,^[17] в отношении Расстояние Хэмминга 1 между соседними кодами. В принципе, для данной длины слова может быть более одного такого кода, но термин «код Грея» впервые был применен к конкретному двоичный код для неотрицательных целых чисел, двоично-отраженный код Грея, или же BRGC, четырехбитная версия которого показана выше.

История и практическое применение

Отраженные двоичные коды применялись к математическим головоломкам еще до того, как они стали известны инженерам. Мартин Гарднер написал популярный отчет о коде Грея в августе 1972 г. Колонка "Математические игры" в журнале Scientific American. Французский инженер Эмиль Бодо использовали коды Грея в телеграфия в 1878 г.^[19] Он получил французский Почетный легион медаль за свою работу. Код Грея иногда неправильно приписывают^[20] к Элиша Грей.^[21][22][23]

Фрэнк Грей, который прославился изобретением метода передачи сигналов, который стал использоваться для совместимого цветного телевидения, изобрел метод преобразования аналоговых сигналов в группы отраженного двоичного кода с использованием вакуумная труба на базе аппарата. Метод и устройство были запатентованы в 1953 году, и имя Грея закрепилось за кодами. "Трубка PCM «Аппарат, который запатентовал Грей, был создан Рэймондом У. Сирсом из Bell Labs в сотрудничестве с Греем и Уильямом М. Гудоллом, которые приписывали Грею идею отраженного двоичного кода.^[24]

Часть первой страницы патента Грея, показывающая трубку PCM (10) с отраженным двоичным кодом на пластине (15)

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

Датчики положения

Энкодер для угловых приборов, маркированных 3-битным двоичным кодом Грея (BRGC)

Абсолютный поворотный энкодер с кодом Грея с 13 дорожками. Корпус, диск прерывателя и источник света находятся сверху; чувствительный элемент и компоненты поддержки находятся внизу.

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

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

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

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

Математические головоломки

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

Генетические алгоритмы

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

Минимизация логической схемы

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

Исправление ошибки

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

Связь между доменами часов

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

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

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

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

Счетчики кода Грея и арифметика

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

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

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

Адресация кода Грея

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

Строительство п-битовый код Грея

Первые несколько шагов метода отражения и префикса.

4-битная перестановка кода Грея

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

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

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

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

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

Аналогичный метод можно использовать для выполнения обратного преобразования, но вычисление каждого бита зависит от вычисленного значения следующего более высокого бита, поэтому его нельзя выполнять параллельно. Предполагая ${ displaystyle g_ {i}}$ это ${ displaystyle i}$th Бит с кодировкой Грея (${ 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 начните с ${ displaystyle mathrm {code} _ {0} = 0}$, а на шаге ${ displaystyle i> 0}$ найти битовую позицию наименее значащей 1 в двоичном представлении ${ displaystyle i}$ и переверните бит в этой позиции в предыдущем коде ${ displaystyle mathrm {code} _ {i-1}}$ чтобы получить следующий код ${ Displaystyle mathrm {код} _ {я}}$. Позиции битов начинаются с 0, 1, 0, 2, 0, 1, 0, 3,….^{[nb 2]} Видеть найти первый набор для эффективных алгоритмов вычисления этих значений.

Преобразование в код Грея и обратно

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

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

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

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

п-арный код Грея

  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

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

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

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

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

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

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

Сбалансированный код Грея

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

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

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

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

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

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

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

${ 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 (п + 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}}$

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

${ displaystyle lambda '_ {i} = { begin {cases} 4 lambda _ {i} -2m_ {i}, & { text {if}} 0 leq i$

Тонкая часть этой конструкции - найти адекватное разделение сбалансированного п-цифровой код Грея, такой, что индуцированный им код остается сбалансированным, но для этого имеет значение только кратность переходов; соединение двух последовательных блоков по цифре ${ displaystyle i}$ переход и разделение другого блока на другую цифру ${ displaystyle i}$ переход производит другой код Грея с точно таким же спектром перехода ${ displaystyle lambda '_ {я}}$, поэтому можно, например,^[40] обозначить первый ${ displaystyle m_ {i}}$ переходы на цифру ${ displaystyle i}$ как те, что попадают между двумя блоками. Единые коды можно найти, когда ${ Displaystyle R Equiv 0 { pmod {4}}}$ и ${ Displaystyle R ^ {п} эквив 0 { pmod {п}}}$, и эту конструкцию можно распространить на р-часть тоже.^[41]

Монотонные коды Грея

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

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

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

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

Элегантная конструкция монотонной п-цифровые коды Грея для любых п основан на идее рекурсивного построения подпути ${ displaystyle P_ {n, j}}$ длины ${ displaystyle 2 { binom {n} {j}}}$ имея края в ${ displaystyle E_ {n} (j)}$.^[43] Мы определяем ${ 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}}$

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

${ Displaystyle G_ {n} ^ {(1)} = P_ {n, 0} P_ {n, 1} ^ {R} P_ {n, 2} P_ {n, 3} ^ {R} cdots { текст {и}} 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

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

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

Код Беккета – Грея

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

Коды змейки в коробке

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

Однодорожечный код Грея

Еще один вид кода Грея - это однопутный код Грея (STGC) разработан Норманом Б. Спеддингом.^[48][49] и усовершенствован Хильтгеном, Патерсоном и Брандестини в «Одноколейных кодах Грея» (1996).^[50][51] STGC - это циклический список п уникальное двоичное кодирование длины n, такое, что два последовательных слова отличаются ровно в одной позиции, и когда список рассматривается как п × п матрица, каждый столбец представляет собой циклический сдвиг первого столбца.^[52]

Однопутный код Грея с 5 датчиками.

Анимированная и цветная версия ротора STGC.

Название происходит от их использования с поворотные энкодеры, где несколько дорожек распознаются контактами, в результате чего для каждого на выходе получается 0 или 1. Чтобы уменьшить шум из-за того, что разные контакты не переключаются в один и тот же момент времени, предпочтительно настраивать дорожки так, чтобы данные вывод контактов в коде Грея. To get high angular accuracy, one needs lots of contacts; in order to achieve at least 1 degree accuracy, one needs at least 360 distinct positions per revolution, which requires a minimum of 9 bits of data, and thus the same number of contacts.

If all contacts are placed at the same angular position, then 9 tracks are needed to get a standard BRGC with at least 1 degree accuracy. However, if the manufacturer moves a contact to a different angular position (but at the same distance from the center shaft), then the corresponding "ring pattern" needs to be rotated the same angle to give the same output. If the most significant bit (the inner ring in Figure 1) is rotated enough, it exactly matches the next ring out. Since both rings are then identical, the inner ring can be cut out, and the sensor for that ring moved to the remaining, identical ring (but offset at that angle from the other sensor on that ring). Those two sensors on a single ring make a quadrature encoder. That reduces the number of tracks for a "1 degree resolution" angular encoder to 8 tracks. Reducing the number of tracks still further can't be done with BRGC.

For many years, Torsten Sillke^[53] and other mathematicians believed that it was impossible to encode position on a single track such that consecutive positions differed at only a single sensor, except for the 2-sensor, 1-track quadrature encoder. So for applications where 8 tracks were too bulky, people used single-track incremental encoders (quadrature encoders) or 2-track "quadrature encoder + reference notch" encoders.

Norman B. Spedding, however, registered a patent in 1994 with several examples showing that it was possible.^[48] Although it is not possible to distinguish 2^п positions with п sensors on a single track, it является possible to distinguish close to that many. Etzion and Paterson conjecture that when п is itself a power of 2, п sensors can distinguish at most 2^п − 2п positions and that for prime п the limit is 2^п − 2 positions.^[54] The authors went on to generate a 504 position single track code of length 9 which they believe is optimal. Since this number is larger than 2⁸ = 256, more than 8 sensors are required by any code, although a BRGC could distinguish 512 positions with 9 sensors.

An STGC for п = 30 and п = 5 is reproduced here:

Each column is a cyclic shift of the first column, and from any row to the next row only one bit changes.^[55]The single-track nature (like a code chain) is useful in the fabrication of these wheels (compared to BRGC), as only one track is needed, thus reducing their cost and size.The Gray code nature is useful (compared to chain codes, также называемый De Bruijn sequences ), as only one sensor will change at any one time, so the uncertainty during a transition between two discrete states will only be plus or minus one unit of angular measurement the device is capable of resolving.^[56]

Two-dimensional Gray code

A Gray-coded constellation diagram for rectangular 16-QAM

Two-dimensional Gray codes are used in communication to minimize the number of bit errors in quadrature amplitude modulation adjacent points in the созвездие. In a typical encoding the horizontal and vertical adjacent constellation points differ by a single bit, and diagonal adjacent points differ by 2 bits.^[57]

Gray isometry

The bijective mapping { 0 ↔ 00, 1 ↔ 01, 2 ↔ 11, 3 ↔ 10 } establishes an isometry между metric space над finite field ${displaystyle mathbb {Z} _{2}^{2}}$ with the metric given by the Hamming distance and the metric space over the finite ring ${displaystyle mathbb {Z} _{4}}$ (the usual modular arithmetic ) with the metric given by the Lee distance. The mapping is suitably extended to an isometry of the Hamming spaces ${displaystyle mathbb {Z} _{2}^{2m}}$ и ${displaystyle mathbb {Z} _{4}^{m}}$. Its importance lies in establishing a correspondence between various "good" but not necessarily linear codes as Gray-map images in ${displaystyle mathbb {Z} _{2}^{2}}$ из ring-linear codes из ${displaystyle mathbb {Z} _{4}}$.^[58][59]

Related codes

There are a number of binary codes similar to Gray codes, including:

• Datex codes aka Giannini codes (1954), as described by Carl P. Spaulding,^{[17][60][61][62][63][16]} use a variant of O'Brien code II.
• Codes used by Varec (ca. 1954),^{[64][65][66][67]} use a variant of O'Brien code I as well as base-12 and base-16 Gray code variants.
• Lucal code (1959)^[1][2][35] aka modified reflected binary code (MRB)^[1][2]
• Gillham code (1961/1962),^{[61][68][16][69][70]} uses a variant of Datex code and O'Brien code II.
• Leslie and Russell code (1964)^{[71][18][72][68]}
• Royal Radar Establishment code^[68]
• Hoklas code (1988)^[73][74][75]

Следующее binary-coded decimal (BCD) codes are Gray code variants as well:

• Petherick code (1953),^{[7][76][77][78][74][nb 3]} также известный как Royal Aircraft Establishment (RAE) code.^[79]
• O'Brien codes I and II (1955)^{[80][81][82][62][63][74]} (An O'Brien type-I code^{[nb 4]} was already described by Frederic A. Foss of IBM^[83][84] and used by Varec in 1954. Later, it was also known as Watts code or Watts reflected decimal (WRD) code.^{[85][9][10][86][87][88][89][90][nb 1]} An O'Brien type-II code was already used by Datex in 1954.^{[nb 3]})
• Excess-3 Gray code (1956)^[91] (aka Gray excess-3 code,^[62][63][16] Gray 3-excess code, reflex excess-3 code, excess Gray code,^[74] Gray excess code, 10-excess-3 Gray code or Gray–Stibitz code), described by Frank P. Turvey Jr. of ITT.^[91]
• Tompkins codes I and II (1956)^{[12][81][82][62][63][74]}
• Glixon code (1957)^{[92][93][94][81][82][62][63][74][nb 4]}

Смотрите также

• Linear feedback shift register
• De Bruijn sequence - a Gray code on a larger alphabet than {0,1}.
• Steinhaus–Johnson–Trotter algorithm, an algorithm that generates Gray codes for the factorial number system
• Minimum distance code

Примечания

Рекомендации

дальнейшее чтение

• Ричардс, Ричард Колер (1955). Арифметические операции в цифровых компьютерах (5-е изд.). Нью-Йорк, США: D. Van Nostrand Co., Inc.
• Ричардс, Ричард Колер (1967). Электронные цифровые компоненты и схемы. D. Van Nostrand Co., Inc. С. 490, 500–504, 510–511.
• Блэк, Пол Э. (25 февраля 2004 г.). «Код Грея». NIST.
• Press, William H .; Teukolsky, Saul A .; Веттерлинг, Уильям Т .; Фланнери, Брайан П. (2007). «Раздел 22.3. Коды Грея». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк, США: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.
• Дикарь, Карла Дайан (1997). "Обзор комбинаторных кодов Грея". SIAM Обзор. Общество промышленной и прикладной математики (СИАМ). 39 (4): 605–629. CiteSeerX  10.1.1.39.1924. Дои:10.1137 / S0036144595295272. JSTOR  2132693.
• Уилф, Герберт Сол (1989). «Главы 1–3». Комбинаторные алгоритмы: обновление. Общество промышленной и прикладной математики (СИАМ). ISBN  0-89871-231-9. ISBN  978-0-89871-231-5.
• Дьюар, Меган; Стивенс, Бретт (29 августа 2012 г.). Заказ блочных конструкций - коды Грея, универсальные циклы и конфигурация. CMS Книги по математике (1-е изд.). Нью-Йорк, США: Springer Science + Business Media. Дои:10.1007/978-1-4614-4325-4. ISBN  978-1-46144324-7. ISSN  1613-5237. ISBN  1-46144324-5.
• Максфилд, Клайв «Макс» (01.10.2012) [28.05.2011]. "Основы кода Грея". Как сделать дизайн. EETimes. Часть 1. В архиве с оригинала на 30.10.2017. Получено 2017-10-30. Часть 2 Часть 3
• Уоррен-младший, Генри С. (2013). «Глава 13: Код Грея». Хакерское наслаждение (2-е изд.). Эддисон Уэсли – Pearson Education, Inc. С. 311–317. ISBN  978-0-321-84268-8. (7 страниц)
• Зиновик, Игорь; Кронинг, Даниэль; Чебиряк, Юрий (21.03.2008). «Вычисление двоичных комбинаторных кодов Грея с помощью исчерпывающего поиска с помощью SAT-решателей». IEEE Transactions по теории информации. IEEE. 54 (4): 1819–1823. Дои:10.1109 / TIT.2008.917695. HDL:20.500.11850/11304. (5 страниц)
• О'Брайен, Джозеф А. (июнь 1957 г.). "Преобразователи двоично-десятичного кода единиц измерения расстояния". Операции IRE на электронных компьютерах. ИС-6 (2): 122–123. Дои:10.1109 / TEC.1957.5221585. ISSN  0367-9950. Получено 2020-05-25. (2 страницы)
• Барр, К. Г. (март 1981). «Десятичный код Грея - легко конвертируется для кодирования положения вала» (PDF). Беспроводной мир. Vol. 87 нет. 1542. Факультет естественных наук, Университет Вест-Индии. С. 86–87. В архиве (PDF) из оригинала на 2020-07-28. Получено 2020-07-28.

внешняя ссылка

• Демонстрация "кода серого" Майкл Шрайбер, Вольфрам Демонстрационный проект (с реализацией Mathematica). 2007 г.
• Словарь алгоритмов и структур данных NIST: код Грея.
• Hitch Hiker's Guide по эволюционным вычислениям, Q21: Что такое коды Грея и почему они используются?, включая C код для преобразования между двоичным и BRGC.
• Драгос А. Харабор использует Коды Грея в 3D-дигитайзере.
• Однодорожечные коды Грея, двоичные цепные коды (Ланкастер 1994 ), и регистры сдвига с линейной обратной связью все они полезны для определения абсолютного положения на одноколейном поворотном энкодере (или другом датчике положения).
• Столбец AMS: коды Грея
• Генератор колеса оптического кодировщика
• ProtoTalk.net - Понимание квадратурного кодирования - Более подробно описывает квадратурное кодирование с акцентом на роботизированные приложения