Код Грея

Упорядочивание двоичных значений, используемых для позиционирования и исправления ошибок

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

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

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

Функция

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

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

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

Код Грея вдоль числовой оси

Для десятичного 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]

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

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

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

Вращающийся энкодер для приборов измерения угла, маркированный в 3-битном двоично-отраженном коде Грея (BRGC)

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

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

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

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

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

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

Благодаря свойствам расстояния Хэмминга кодов Грея, их иногда используют в генетических алгоритмах . ^[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]}

Построениен-битный код Грея

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

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

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

Однобитовый код Грея — это 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 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)

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

Коды Грея снбиты и длиной менее 2н

Можно построить двоичные коды Грея с 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{ for }}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{if }}0\leq i<n\\L,&{\text{ otherwise }}\end{cases}}}$

Деликатная часть этой конструкции заключается в том, чтобы найти адекватное разбиение сбалансированного n -разрядного кода Грея таким образом, чтобы код, индуцированный им, оставался сбалансированным, но для этого важны только кратности переходов; объединение двух последовательных блоков по цифровому переходу и разделение другого блока по другому цифровому переходу дает другой код Грея с точно таким же спектром переходов , так что можно, например, ^[65] обозначить первые переходы по цифре как те, которые попадают между двумя блоками. Однородные коды могут быть найдены, когда и , и эта конструкция может быть расширена также на R -арный случай. ^[66] ${\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}}}$

Коды Грея с длительным сроком действия

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

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

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

Формализовать концепцию монотонных кодов Грея можно следующим образом: рассмотрим разбиение гиперкуба на уровни вершин, имеющих одинаковый вес, т.е. ${\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)|=\textstyle {\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 основана на идее рекурсивного построения подпутей длины, имеющих ребра в . ^[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 \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}\left(\pi _{n-1}^{2}\right)}$ ${\displaystyle P_{n,j}}$

Эти монотонные коды Грея могут быть эффективно реализованы таким образом, что каждый последующий элемент может быть сгенерирован за время 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]

Коды «Змея в коробке»

Максимальные длины змей ( L _s ) и катушек ( L _c ) в задаче о змеях в коробке для размерностей n от 1 до 4

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

Однопутный код Грея

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

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

Название происходит от их использования с вращающимися энкодерами , где несколько дорожек считываются контактами, в результате чего для каждой из них выводится значение 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 воспроизведен здесь:

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

9-битный однодорожечный код Грея, отображающий угловое разрешение в один градус.

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

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

Двумерный код Грея

Диаграмма созвездия в коде Грея для прямоугольной 16- QAM

Двумерные коды Грея используются в коммуникации для минимизации количества ошибок битов в квадратурной амплитудной модуляции (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}}$

Связанные коды

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

• Коды 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]}

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

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

Примечания

1. Применив простое правило инверсии , код Грея и код О'Брайена I можно перевести в чистый двоичный код 8421 и код Эйкена 2421 соответственно, чтобы упростить арифметические операции. ^[C]
2. Последовательность 0, 1, 0, 2, 0, 1, 0, 3, … (последовательность A007814 в OEIS ).
3. Существует несколько вариантов кода Грея, которые называются «модифицированными» в некотором роде: Код Гликсона иногда называют модифицированным кодом Грея. ^[D] Код Люкаля также называют модифицированным отраженным двоичным кодом (MRB). ^[E] Код О'Брайена I или код Уоттса иногда называют отраженным двоичным модифицированным кодом Грея. ^[F]
4. Перестановкой и инвертированием трех битовых строк можно преобразовать код О'Брайена II и код Петерика друг в друга.
5. Поменяв местами две пары битовых строк, по отдельности сдвигая четыре битовые строки и инвертируя одну из них, можно преобразовать код Гликсона и код О'Брайена I друг в друга.
6. Другие коды BCD с единичным расстоянием включают в себя не связанный с кодом Грея 5-битный код Либо-Крейга и код 1-2-1 .
7. В зависимости от целевого применения кода, веса Хэмминга кода могут быть важными свойствами, выходящими за рамки теоретических соображений кодирования, а также по физическим причинам. В некоторых обстоятельствах состояния all-cleared и/или all-set должны быть опущены (например, чтобы избежать непроводящих или короткозамкнутых условий), может быть желательно поддерживать максимально низкий используемый вес (например, чтобы снизить энергопотребление схемы считывателя) или поддерживать небольшую дисперсию используемых весов (например, чтобы снизить акустический шум или колебания тока).
8. Для кодов Грея BCD, Пола и Клара количество необходимых дорожек чтения может быть уменьшено с 4 до 3, если допустима инверсия одной из средних дорожек.
9. Для кодов О'Брайена I и II, а также кодов Петерика, Сасскинда, Клара, а также кодов Грея Excess-3 дополнение до 9 может быть получено путем инвертирования старшей (четвертой) двоичной цифры.
10. Для кода Томпкинса II дополнение до 9 можно получить путем инвертирования первых трех цифр и перестановки двух средних двоичных цифр.

Ссылки

1. Lucal, Harold M. (декабрь 1959 г.). «Арифметические операции для цифровых компьютеров с использованием модифицированного отраженного двоичного кода». Труды IRE по электронным компьютерам . EC-8 (4): 449–458. doi :10.1109/TEC.1959.5222057. ISSN  0367-9950. S2CID  206673385.(10 страниц)
2. Sellers, Jr., Frederick F.; Hsiao, Mu-Yue; Bearnson, Leroy W. (ноябрь 1968 г.). Error Detecting Logic for Digital Computers (1-е изд.). Нью-Йорк, США: McGraw-Hill Book Company . стр. 152–164. LCCN  68-16491. OCLC  439460.
3. Грей, Джоэл (март 2020 г.). «Понимание кода Грея: надежная система кодирования». graycode.ie . Раздел: Заключение . Получено 2023-06-30 .
4. Tompkins, Howard E. (сентябрь 1956 г.) [1956-07-16]. "Unit-Distance Binary-Decimal Codes for Two-Track Commutation". IRE Transactions on Electronic Computers . Переписка. EC-5 (3). Школа электротехники Мура , Пенсильванский университет , Филадельфия, Пенсильвания, США: 139. doi :10.1109/TEC.1956.5219934. ISSN  0367-9950. Архивировано из оригинала 2020-05-18 . Получено 2020-05-18 .(1 страница)
5. Kautz, William H. (июнь 1958 г.). «Коды проверки ошибок на единичном расстоянии». IRE Transactions on Electronic Computers . EC-7 (2): 179–180. doi :10.1109/TEC.1958.5222529. ISSN  0367-9950. S2CID  26649532.(2 страницы)
6. Susskind, Alfred Kriss; Ward, John Erwin (1958-03-28) [1957, 1956]. "III.F. Коды единичного расстояния / VI.E.2. Отраженные двоичные коды". Написано в Кембридже, Массачусетс, США. В Susskind, Alfred Kriss (ред.). Notes on Analog-Digital Conversion Techniques . Technology Books in Science and Engineering. Vol. 1 (3-е изд.). Нью-Йорк, США: Technology Press of the Massachusetts Institute of Technology / John Wiley & Sons, Inc. / Chapman & Hall, Ltd. стр. 3-10–3-16 [3-13–3-16], 6-65–6-60 [6-60].(x+416+2 страницы) (Примечание. Содержание книги изначально было подготовлено сотрудниками лаборатории сервомеханизмов кафедры электротехники Массачусетского технологического института для специальных летних программ, проводившихся в 1956 и 1957 годах. «Код считывающего типа» Сасскинда на самом деле является второстепенным вариантом кода, показанного здесь, в котором две самые значимые строки битов поменяны местами для лучшей иллюстрации симметрии. Кроме того, поменяв местами две строки битов и инвертировав одну из них, код можно преобразовать в код Петерика, тогда как поменяв местами и инвертировав две строки битов, код можно преобразовать в код О'Брайена II.)
7. Chinal, Jean P. (январь 1973 г.). "3.3. Коды единичных расстояний". Написано в Париже, Франция. Методы проектирования цифровых систем. Перевод Престона, Алана; Саммера, Артура (1-е англ. изд.). Берлин, Германия: Akademie-Verlag / Springer-Verlag . стр. 50. doi :10.1007/978-3-642-86187-1. ISBN 978-0-387-05871-9. S2CID  60362404. Лицензия № 202-100/542/73. Заказ № 7617470(6047) ES 19 B 1 / 20 K 3 . Получено 21.06.2020 .(xviii+506 страниц) (Примечание. Оригинальная книга на французском языке 1967 года называлась «Techniques Booléennes et Calculateurs Arithmétiques», опубликованная издательством Éditions Dunod  [fr] .)
8. Военный справочник: энкодеры – угол вала в цифровом формате (PDF) . Министерство обороны США . 1991-09-30. MIL-HDBK-231A. Архивировано (PDF) из оригинала 2020-07-25 . Получено 2020-07-25 .(Примечание. Заменяет MIL-HDBK-231(AS) (1970-07-01).)
9. Spaulding, Carl P. (1965-01-12) [1954-03-09]. "Цифровая система кодирования и трансляции" (PDF) . Монровия, Калифорния, США: Datex Corporation. Патент США 3165731A . Серийный номер 415058. Архивировано (PDF) из оригинала 2020-08-05 . Получено 2018-01-21 .(28 страниц)
10. Russell, A. (август 1964 г.). «Некоторые двоичные коды и новый пятиканальный код». Управление (системы, приборы, обработка данных, автоматизация, управление, включающее Automation Progress) . Специальные характеристики. 8 (74). Лондон, Великобритания: Morgan-Grampain (Publishers) Limited: 399–404 . Получено 22.06.2020 .(6 страниц)
11. Stibitz, George Robert (1943-01-12) [1941-11-26]. «Двоичный счетчик». Нью-Йорк, США: Bell Telephone Laboratories, Incorporated . Патент США 2,307,868 . Серийный номер 420537. Получено 24.05.2020 . стр. 2, правый столбец, строки 43–73: […] Более четкое представление о положении шариков после каждого импульса будет получено, если набор шариков будет представлен числом, имеющим аналогичное количество цифр, каждое из которых может иметь одно из двух произвольных значений, например 0 и 1. Если верхняя позиция обозначена как 0, а нижняя позиция […] как 1, то настройка счетчика […] может быть прочитана слева направо как 0,100,000. […] Ниже приведен перевод числа полученных импульсов в эту форму двоичной записи для первых шестнадцати импульсов, полученных от первых пяти шаров […] Номер импульса […] Двоичная запись […][1] (4 страницы)
12. Winder, C. Farrell (октябрь 1959 г.). "Shaft Angle Encoders Afford High Accuracy" (PDF) . Electronic Industries . 18 (10). Chilton Company : 76–80. Архивировано из оригинала (PDF) 2020-09-28 . Получено 2018-01-14 . стр. 78: […] Тип кодового колеса, наиболее популярный в оптических энкодерах, содержит циклический двоичный кодовый шаблон, предназначенный для получения циклической последовательности выходов "вкл-выкл". Циклический двоичный код также известен как код циклической прогрессии, отраженный двоичный код и код Грея. Этот код был создан GR Stibitz из Bell Telephone Laboratories и впервые предложен для систем импульсно-кодовой модуляции Фрэнком Греем , также из BTL. Отсюда и название код Грея. Код Грея или циклический код используется в основном для устранения возможности возникновения ошибок при переходе между кодами, которые могут привести к грубым неоднозначностям. […]
13. Кнут, Дональд Эрвин (2014-09-12). «Перечисление и возврат к предыдущему элементу / Генерация всех n-кортежей». Искусство программирования, том 4A: Комбинаторные алгоритмы, часть 1. Том 4A (1-е изд.). Addison-Wesley Professional . стр. 442–443. ISBN 978-0-13348885-2.(912 страниц)
14. Gray, Frank (1953-03-17) [1947-11-13]. Импульсно-кодовая связь (PDF) . Нью-Йорк, США: Bell Telephone Laboratories, Incorporated . Патент США 2,632,058 . Серийный номер 785697. Архивировано (PDF) из оригинала 2020-08-05 . Получено 2020-08-05 .(13 страниц)
15. Goldberg, David Edward (1989). Генетические алгоритмы в поиске, оптимизации и машинном обучении (1-е изд.). Reading, Массачусетс, США: Addison-Wesley . Bibcode :1989gaso.book.....G.
16. Брекман, Джек (1956-01-31) [1953-12-31]. Схема кодирования (PDF) . Лонг-Бранч, Нью-Джерси, США: Министр армии США . Патент США 2,733,432 . Серийный номер 401738. Архивировано (PDF) из оригинала 2020-08-05 . Получено 2020-08-05 .(8 страниц)
17. Ragland, Earl Albert; Schultheis, Jr., Harry B. (1958-02-11) [1953-10-16]. Система управления положением двоичного кода, чувствительная к направлению (PDF) . Северный Голливуд, Калифорния, США: Bendix Aviation Corporation. Патент США 2,823,345 . Серийный номер 386524. Архивировано (PDF) из оригинала 2020-08-05 . Получено 2020-08-05 .(10 страниц)
18. Домешек, Сол; Райнер, Стюарт (1958-06-24) [1954-01-08]. Автоматическая система ректификации (PDF) . Министр ВМС США . Патент США 2,839,974 . Серийный номер 403085. Архивировано (PDF) из оригинала 2020-08-05 . Получено 2020-08-05 .(8 страниц)
19. Petherick, Edward John (октябрь 1953 г.). Циклическая прогрессивная двоично-десятичная система представления чисел (Техническое примечание MS15). Фарнборо, Великобритания: Королевское авиационное учреждение (RAE).(4 страницы) (Примечание. Иногда ее называют циклически-кодированной двоично-десятичной системой представления чисел .)
20. Evans, David Silvester (1960). Fundamentals of Digital Instrumentation (1-е изд.). Лондон, Великобритания: Hilger & Watts Ltd. Получено 24.05.2020 .(39 страниц)
21. Evans, David Silvester (март 1961 г.). «Глава третья: прямое считывание с кодированных шкал». Цифровые данные: их вывод и сокращение для анализа и управления процессами (1-е изд.). Лондон, Великобритания: Hilger & Watts Ltd / Interscience Publishers . стр. 18–23 . Получено 2020-05-24 . стр. 20–23: […] Декодирование. […] Для декодирования кодов CPB или WRD можно применить простое правило инверсии. Показания более высоких дорожек определяют способ, которым переводятся более низкие дорожки. Правило инверсии применяется строка за строкой для CPB, а для WRD — десятилетие за десятилетием или строка за строкой. Начиная, таким образом, с верхней или самой медленно изменяющейся дорожки CPB, если результат нечетный (1), значение следующей дорожки должно быть инвертировано, т. е. 0 для 1 и 1 для 0. Если, однако, первая дорожка четная (0), вторая дорожка остается прочитанной, т. е. 0 для 0 и 1 для 1. Опять же, если результирующее показание второй дорожки нечетное, показание третьей дорожки инвертируется и т. д. Когда нечетное меняется на четное, строка ниже не инвертируется, а когда четное меняется на нечетное, строка ниже инвертируется. Результатом применения этого правила к шаблону […] является чистый двоичный (PB) шаблон […], где каждой дорожке или цифре может быть присвоено определенное числовое значение (в данном случае 1, 2, 4, 8 и т. д.). […] Использование правила инверсии строка за строкой в ​​коде WRD создает [шаблон] [ кода 1, 2, 4, 2 ], где снова цифрам можно присвоить числовые значения и суммировать десятилетие за десятилетием. Суммирование цифр может быть очень полезным, например, в высокоскоростной системе сканирования; но в параллельной системе декодирования […], обычно каждый двоичный квартет или декаду рассматривают как единое целое. Другими словами, если первый или более значимый десяток нечетный, второй десяток исправляется или дополняется путем инвертирования дорожки D и так далее, результатом чего является повторяющийся шаблон [исправленного кода WRD]. Этого чрезвычайно легко добиться, поскольку единственным требуемым изменением является инверсия значения дорожки D или дополнительной цифры. […](8+82 страницы) (Примечание. Автор вообще не упоминает Грея и называет стандартный код Грея «циклическим переставленным двоичным кодом» (CPB), в индексе книги он ошибочно указан как «циклический чистый двоичный код».)
22. Ньюсон, PA (1965). Таблицы для двоичного кодирования углов (1-е изд.). Управление по атомной энергии Соединенного Королевства , Исследовательская группа, Исследовательский центр по атомной энергии , Харвелл, Великобритания: Канцелярия Ее Величества . Получено 24.05.2020 .(12 страниц)
23. Heath, FG (сентябрь 1961 г.). «Пионеры двоичного кодирования». Журнал Института инженеров-электриков . 7 (81). Манчестерский колледж науки и технологий , Технологический факультет Манчестерского университета , Манчестер, Великобритания: Институт инженерии и технологий (IET): 539–541. doi :10.1049/jiee-3.1961.0300. Архивировано из оригинала 28.03.2020 . Получено 22.06.2020 .(3 страницы)
24. Cattermole, Kenneth W. (1969). Написано в Harlow, Essex, UK. Principles of pulse code modulation (1 ed.). London, UK / New York, USA: Iliffe Books Ltd. / American Elsevier Publishing Company, Inc. стр. 245, 434. ISBN 978-0-444-19747-4. LCCN  78-80432. SBN 444-19747-8. стр. 245: […] Кажется, есть некоторая путаница в атрибуции этого кода, потому что два изобретателя по имени Грей были связаны с ним. Когда я впервые услышал это имя, я принял его за Элишу Грея , и Хит свидетельствует об использовании им этого имени. Многие люди принимают его за ссылку на Фрэнка Грея из Bell Telephone Laboratories , который в 1947 году первым предложил использовать его в кодирующих трубках: его патент указан в библиографии. […](2+448+2 страницы)
25. Эдвардс, Энтони Уильям Фэрбэнк (2004). Шестеренки разума: История диаграмм Венна. Балтимор, Мэриленд, США: Johns Hopkins University Press . стр. 48, 50. ISBN 0-8018-7434-3.
26. Грос, Люк-Агатон-Луи (1872). Théorie du Baguenodier par un clerc de notaire lyonnais (на французском языке) (1-е изд.). Лион, Франция: Эме Вентринье . Архивировано из оригинала 3 апреля 2017 г. Проверено 17 декабря 2020 г.[2](2+16+4 страницы и 4 страницы в развороте) (Примечание. Эта брошюра была опубликована анонимно, но известно, что ее автором является Луи Гро.)
27. Лукас, Эдуард (ноябрь 1883 г.). La Tour d'Hanoï: Véritable casse tête annamite - Jeu rapporté du Tonkin par le Professeur N. Claus (de Siam) Mandarin du Collège Li Sou Stian! (на французском языке). Imprimerie Поль Бусрез, Тур.(Примечание. N. Claus de Siam — анаграмма имени Lucas d'Amiens, псевдонима автора Эдуарда Люка .)
28. де Парвиль, Анри [на французском языке] , изд. (27 декабря 1883 г.). «La Tour d'Hanoï, настоящий кассетный аннамит, игра в Тонкине с профессором Н. Клаусом (из Сиама), мандарином колледжа Ли-Су-Стиан. Un vrai casse-tête, en effet, mais intéressant. Nous ne saurions mieux remercier le mandarin de son, направленное на намерение à l'égard d'un profane qu'en signalant la Tour d'Hanoï aux personnes Patientes possédées par le démon du jeu". Journal des Débats Politiques et Litéraires (обзор). Revue des science (на французском языке) (Matin ed.). Париж, Франция: 1–2 [2]. ark:/12148/bpt6k462461g. Архивировано из оригинала 2020-12-18 . Получено 2020-12-18 .(1 страница)
29. Allardice, RE; Fraser, AY (февраль 1883 г.). Allardice, Robert Edgar ; Fraser, Alexander Yule (ред.). "La Tour d'Hanoï". Труды Эдинбургского математического общества (на английском и французском языках). 2 (5). Эдинбургское математическое общество : 50–53. doi : 10.1017/S0013091500037147 (неактивен 2024-11-01). eISSN  1464-3839. ISSN  0013-0915. S2CID  122159381.{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)[3] (4 страницы)
30. Лукас, Эдуард (1979) [1892]. Récréations mathématiques (на французском языке). Том. 3 (переиздание Библиотеки Альберта Бланшара). п. 58.(Первое издание этой книги было опубликовано посмертно.)
31. Herter, Felix; Rote, Günter (2018-11-14) [2018-08-09, 2017-12, 2017-08-09, 2016-04-22]. "Loopless Gray Code Enumeration and the Tower of Bucharest" (PDF) . Theoretical Computer Science . 748 . Berlin, Germany: 40–54. arXiv : 1604.06707 . doi :10.1016/j.tcs.2017.11.017. ISSN  0304-3975. S2CID  4014870. Архивировано (PDF) из оригинала 2020-12-16 . Получено 2020-12-16 .[4] (15/18/19/24 страницы)
32. Гарднер, Мартин (август 1972 г.). «Любопытные свойства кода Грея и как его можно использовать для решения головоломок». Scientific American . Математические игры . Т. 227, № 2. С. 106.(1 страница)
33. Земан, Иоганн; Фишер, Фердинанд, ред. (1877). «Einige neuere Vorschläge zur mehrfachen Telegraphie: A. Absatzweise vielfache Telegraphie». Политехнический журнал Динглера (на немецком языке). 226 . Аугсбург, Германия: JG Cotta'sche Buchhandlung: 499–507. Архивировано из оригинала 21 декабря 2020 г. Проверено 21 декабря 2020 г. п. 499: […] Der um die Mitte des J[ahres] 1874 года, патент [e]rte, ebenfalls dem Highton 'schen verwandte Typendrucker des französischen Telegraphen-Verwaltungsbeamten Baudot wurde bei seiner 1875 года, патентi[e]rten Weiterentwicklung in einen fünffachen умгевандельт […]
34. Бутрика, Эндрю Дж. (1991-06-21). "Бодо, Жан Морис Эмиль". В Froehlich, Фриц Э.; Кент, Аллен ; Холл, Кэролин М. (ред.). Энциклопедия телекоммуникаций Фрёлиха/Кента: Том 2 - Батареи для кодов-Телекоммуникации . Том 2. Marcel Dekker Inc. / CRC Press . стр. 31–34. ISBN 0-8247-2901-3. LCCN  90-3966 . Получено 20.12.2020 . стр. 31: […] Прототип Бодо (4 года в разработке) был построен в 1876 году. Передатчик имел 5 клавиш, похожих на клавиши фортепиано. Сообщения отправлялись в специальном 5-элементном коде, разработанном Бодо […]
35. Фишер, Эрик Н. (2000-06-20). «Эволюция кодов символов, 1874–1968». ark:/13960/t07x23w8s . Получено 2020-12-20 . […] В 1872 году [Бодо] начал исследования в направлении телеграфной системы, которая позволила бы нескольким операторам одновременно передавать данные по одному проводу и, по мере получения передач, печатать их обычными буквенными символами на полоске бумаги. Он получил патент на такую ​​систему 17 июня 1874 года. […] Вместо переменной задержки, за которой следовал одноединичный импульс, система Бодо использовала единообразные шесть единиц времени для передачи каждого символа. […] его ранний телеграф, вероятно, использовал шестиединичный код […], который он приписывает Дэви в статье 1877 года. […] в 1876 году Бодо перепроектировал свое оборудование для использования пятиединичного кода. Однако знаки препинания и цифры все еще иногда были нужны, поэтому он перенял у Хьюза использование двух специальных символов пробела между буквами и цифрами, которые заставляли принтер переключаться между регистрами одновременно с тем, как он продвигал бумагу без печати. ​​Пятиэлементный код, который он начал использовать в это время […], был структурирован для соответствия его клавиатуре […], которая управляла двумя единицами каждого символа с помощью переключателей, управляемых левой рукой, и тремя другими единицами — правой рукой. […][5][6]
36. Ротен, Тимофей (25 декабря 1884 г.). «Le télégraphe imprimeur Бодо». Журнал Télégraphique (на французском языке). VIII/№16 (12). Берн, Швейцария: Международное бюро телеграфной администрации: 241–253 [249]. eISSN  2725-738X. ISSN  2223-1420. ковчег:/12148/bpt6k5725454q. Архивировано из оригинала 21 декабря 2020 г. Проверено 20 декабря 2020 г.
37. Пендри, Генри Уолтер (1920) [октябрь 1919]. Написано в Лондоне, Великобритания. The Baudôt Printing Telegraph System (2-е изд.). Лондон, Бат, Мельбурн, Нью-Йорк: Sir Isaac Pitman and Sons, Ltd. стр. 43–44. LCCN  21005277. OCLC  778309351. OL  6633244M . Получено 20.12.2020 .(vii+184 страницы) (Примечание. Первое издание было опубликовано в 1913 году.)
38. MacMillan, David M. (2010-04-27) [2010-04-25, 2010-04-23]. "Коды, которые не учитываются - некоторые коды печатного телеграфа как продукты их технологий (с особым вниманием к телеграфному наборному устройству)". lemur.com . Редакция 3. Mineral Point, Wisconsin, USA. Архивировано из оригинала 2020-12-18 . Получено 2020-12-20 .
39. Написано в Лиссабоне, Португалия. Международная телеграфная конвенция Сен-Петерсбурга и правила и тарифы и приложения, Лиссабонская редакция, 1908 г./Документы публикации: Documents de la Conférence télégraphique Internationale de Lisbonne (на французском языке). Берн, Швейцария: Международное бюро L'Union Télégraphique . 1909 [1908].
40. «Глава IX. Знаки передачи, Статья 35. Знаки передачи международных телеграфных алфавитов №№ 1 и 2, знаки кода Морзе, устройства Хьюза и устройства Siemens» . Написано в Мадриде, Испания. Приложение к телеграфному регламенту к Международной конвенции электросвязи - протокол финального аудита правил - Мадрид, 1932 г. (PDF) (на французском языке). Берн, Швейцария: Международное бюро L'Union Télégraphique . 1933 [1932]. С. 31–40 [33]. Архивировано (PDF) из оригинала 21 декабря 2020 г. Проверено 21 декабря 2020 г.(1+188 страниц) [7]
41. "Глава IX. Сигналы передачи. Статья 35. Сигналы передачи международных телеграфных алфавитов № 1 и 2, сигналы кода Морзе и сигналы приборов Хьюза и Сименса". Телеграфные правила, приложенные к Международной конвенции электросвязи - Заключительный протокол к телеграфным правилам - Мадрид 1932 г. (PDF) (на английском и французском языках). Лондон, Великобритания: Главное почтовое отделение / Канцелярия Его Величества . 1933 [1932]. стр. 32–40 [34]. 43-152-2 / 18693. Архивировано (PDF) из оригинала 21.12.2020 . Получено 21.12.2020 .(1+2*120+26 страниц) [8]
42. Земанек, Генрих «Хайнц» Йозеф (1 декабря 1983). Отто Шеффлер (1838-1928). Pionier des Telephons, der Telegraphie und der Lochkarte sowie Erbauer der ersten Wiener Telephonzentrale . Blätter für Technikgeschichte (на немецком и английском языках). Том. 41–43 (1979–1981) (1-е изд.). Вена, Австрия: Технический музей промышленности и производства , Forschungsinstitut für Technikgeschichte / Springer-Verlag . стр. 81–118. ISBN 3-21181779-4. ISSN  0067-9127. OCLC  952698275.
43. Zemanek, Heinrich "Heinz" Josef (1976-06-07). "Computer prehistory and history in central Europe". Написано в Вене, Австрия. International Workshop on Managing Requirements Knowledge . AFIPS '76: Proceedings of the June 7–10, 1976, national computer conference and exposition June 1976. Vol. 1. New York, USA: American Federation of Information Processing Societies , Association for Computing Machinery . pp. 15–20. doi :10.1145/1499799.1499803. ISBN 978-1-4503-7917-5. S2CID  14114959. Архивировано из оригинала 2020-12-17 . Получено 2020-12-17 . стр. 17: […] В 1874 году Шеффлер  [de] изобрел еще один печатающий телеграф , четверную систему, похожую на Бодо , но механически более сложную. Телеграф Хьюза имел два синхронно вращающихся пальца, один в отправителе и один в приемнике. С помощью похожей на пианино клавиатуры оператор выбирал букву и тем самым вступал в контакт с вращающимся пальцем в соответствующем направлении. Поскольку принимающий палец в этот момент находился в том же направлении, приемник мог напечатать правильную букву. Печатающие телеграфы Бодо и Шеффлера используют пятибитный двоичный код. ... Код Шеффлера является отраженным двоичным кодом! То, что Ф. Грей запатентовал в 1953 году для PCM , Шеффлер применил в своем телеграфе в 1874 году, и по схожей причине: надежность. У него были контактные пальцы, считывающие на пяти кулачках последовательно все комбинации; правый запускает печать. Если пальцы должны были сделать минимальное количество движений, решением будет отраженный двоичный код. Для Шеффлера эта идея была второстепенной. Точнее, код описан в письме сотрудника австрийской почты, И[оганна] Н[епомука] Тойфельхарта, вставленном туда в качестве сноски и сообщающем, что Шеффлер нашел код, комбинируя деревянные бруски с различными комбинациями, пока не получил наилучшее решение. Другой сотрудник почты, Александр Вильгельм Ламберт из Линца, утверждает, что показал этот код Шеффлеру еще в 1872 году, но это утверждение неясно и не может быть проверено. […](6 страниц)
44. Гудолл, Уильям М. (январь 1951 г.). «Телевидение с помощью импульсно-кодовой модуляции». Bell System Technical Journal . 30 (1): 33–49. doi :10.1002/j.1538-7305.1951.tb01365.x.(Примечание. Представлено устно на Национальном съезде ИРЭ, Нью-Йорк, март 1949 г.)
45. Карно, Морис (ноябрь 1953 г.) [1953-04-23, 1953-03-17]. "Метод карты для синтеза комбинационных логических схем" (PDF) . Труды Американского института инженеров-электриков, часть I: Связь и электроника . 72 (5): 593–599. doi :10.1109/TCE.1953.6371932. S2CID  51636736. Статья 53-217. Архивировано из оригинала (PDF) 2017-04-16 . Получено 2017-04-16 .(Примечание. Также содержит краткий обзор Сэмюэля Х. Колдуэлла .)
46. Уэйкерли, Джон Ф. (1994). Цифровой дизайн: принципы и практики . Нью-Джерси, США: Prentice Hall . стр. 48–49, 222. ISBN 0-13-211459-3.(Примечание. В двух разделах страницы, взятых вместе, говорится, что карты К помечены кодом Грея. В первом разделе говорится, что они помечены кодом, который изменяет только один бит между записями, а во втором разделе говорится, что такой код называется кодом Грея.)
47. Браун, Фрэнк Маркхэм (2012) [2003, 1990]. "3.9.2 Карты". Булевое рассуждение – Логика булевых уравнений (переиздание 2-го изд.). Минеола, Нью-Йорк, США: Dover Publications, Inc. стр. 49. ISBN 978-0-486-42785-0. стр. 49: […] Карта Карно упорядочивает аргументы дискриминантов в соответствии с отраженным двоичным кодом, также называемым кодом Грея. […](xii+291+3 страницы) 1-е издание
48. Хендлер, Вольфганг (1958). Ein Minimisierungsverfahren zur Synthese von Schaltkreisen (Minimisierungsgraphen) (Диссертация) (на немецком языке). Потсдам, Германия: Technische Hochschule Darmstadt . Д 17.(73 страницы+прибл.) [9]
49. Бергер, Эрих Р.; Хендлер, Вольфганг (1967) [1962]. Штайнбух, Карл В .; Вагнер, Зигфрид В. (ред.). Taschenbuch der Nachrichtenverarbeitung (на немецком языке) (2-е изд.). Берлин, Германия: Springer-Verlag OHG . стр. 64, 1034–1035, 1036, 1038. LCCN  67-21079. Титул № 1036. с. 64: […] Übersichtlich ist die Darstellung nach Händler , die sämtliche Punkte, numeriert nach dem Gray-Code […], auf dem Umfeld eines Kreises anordnet. Sie erfordert allerdings sehr viel Platz. […] [ Диаграмма Хендлера , где все точки, пронумерованные в соответствии с кодом Грея , расположены на окружности, легко понятна. Однако она требует много места.]
50. "Informatik Sammlung Erlangen (ISER)" (на немецком языке). Эрланген, Германия: Университет Фридриха-Александра . 13 марта 2012 г. Архивировано из оригинала 16 мая 2017 г. Проверено 12 апреля 2017 г.
51. "Informatik Sammlung Erlangen (ISER) - Impressum" (на немецком языке). Эрланген, Германия: Университет Фридриха-Александра . 13 марта 2012 г. Архивировано из оригинала 26 февраля 2012 г. Проверено 15 апреля 2017 г.
52. Bhat, Girish S.; Savage, Carla Diane (1996). "Сбалансированные коды Грея". Электронный журнал комбинаторики . 3 (1). doi : 10.37236/1249 .
53. Донохью, Райан (2003). "Синхронизация в цифровых логических схемах" (PDF) . Архивировано (PDF) из оригинала 2018-01-15 . Получено 2018-01-15 .
54. Халст, Джордж Д. (1962-02-06) [1957-11-15]. Счетчик отраженного двоичного кода (PDF) . Натли, Нью-Джерси, США: Международная телефонная и телеграфная корпорация (ITT). Патент США 3,020,481 . Серийный номер 696793. Архивировано (PDF) из оригинала 2020-08-06 . Получено 2020-08-06 .(5 страниц)
55. Powell, E. Alexander (июнь 1968 г.). «Коды, особенно полезные для аналого-цифровых преобразований». Краткая заметка о полезных кодах для схем управления потоками (PDF) . Крэнфилд, Великобритания: Колледж аэронавтики , кафедра производственного инжиниринга. стр. 7, 9. S2CID  215864694. Памятка CoA 156. Архивировано (PDF) из оригинала 15.12.2020 . Получено 15.12.2020 .(18 страниц) (Примечание. В статье код Гликсона назван модифицированным кодом Грея , а имя Ричарда У. Хэмминга указано с ошибкой.)
56. Мехта, Хузефа; Оуэнс, Роберт Майкл; Ирвин, Мэри Джейн "Джани" (1996-03-22). "Некоторые проблемы адресации в коде Грея". Труды Шестого симпозиума Великих озер по СБИС . IEEE Computer Society . стр. 178–181. doi :10.1109/GLSV.1996.497616. ISBN 978-0-8186-7502-7. ISSN  1066-1395. S2CID  52837310.
57. Doran, Robert "Bob" William (март 2007 г.). The Gray Code (PDF) . Серия исследовательских отчетов CDMTCS. Центр дискретной математики и теоретической информатики, Оклендский университет , Новая Зеландия. CDMTCS-304. Архивировано (PDF) из оригинала 22-05-2020 . Получено 23-05-2020 .(25 страниц)
58. Су, Чинг-Лонг; Цуй, Чи-Ин; Деспейн, Элвин М. (1994). Проектирование архитектуры с низким энергопотреблением и методы компиляции для высокопроизводительных процессоров (PDF) (Отчет). Advanced Computer Architecture Laboratory. ACAL-TR-94-01. Архивировано (PDF) из оригинала 2020-07-26 . Получено 2020-12-17 .
59. Го, Хуэй; Парамесваран, Шри (апрель–июнь 2010 г.). «Смещенное кодирование Грея для уменьшения переключения шины адреса памяти инструкций для маломощных встраиваемых систем». Журнал системной архитектуры . 56 (4–6): 180–190. doi :10.1016/j.sysarc.2010.03.003.
60. Dietz, Henry Gordon "Hank" (2002). "The Aggregate Magic Algorithms: Gray Code Conversion". The Aggregate . Кафедра электротехники и вычислительной техники, Инженерный колледж, Университет Кентукки . Архивировано из оригинала 2020-12-16 . Получено 2020-12-16 .
61. Максфилд, Макс (29.06.2007). "Как генерировать коды Грея для последовательностей, не являющихся степенью 2". Архивировано из оригинала 29.01.2022 . Получено 29.01.2022 .
62. (последовательность A290772 в OEIS )
63. Guan, Dah-Jyh (1998). «Обобщенные коды Грея с приложениями». Труды Национального научного совета Китайской Республики, Часть A. 22 : 841–848. CiteSeerX 10.1.1.119.1344 . 
64. DG Wagner, J. West (1991). «Построение однородных кодов Грея». Congressus Numerantium . 80 : 217–223.
65. ^Suparta, I. Nengah (2005). "Простое доказательство существования экспоненциально сбалансированных кодов Грея". Electronic Journal of Combinatorics . 12. doi : 10.37236/1986 .
66. Flahive, Mary Elizabeth ; Bose, Bella (2007). "Балансировка циклических R-арных кодов Грея". Electronic Journal of Combinatorics . 14 . doi : 10.37236/949 .
67. Штракс, Рауль; Писсенс, Франк (2016). «Ариадна: минимальный подход к непрерывности состояния». Usenix Security . 25 .
68. Savage, Carla Diane (1997). «Обзор комбинаторных кодов Грея». Обзор SIAM . 39 (4). Общество промышленной и прикладной математики (SIAM): 605–629. Bibcode : 1997SIAMR..39..605S. CiteSeerX 10.1.1.39.1924 . doi : 10.1137/S0036144595295272. JSTOR  2132693. S2CID  6375360. 
69. Savage, Carla Diane ; Winkler, Peter (1995). "Монотонные коды Грея и проблема средних уровней". Журнал комбинаторной теории . Серия A. 70 (2): 230–248. doi : 10.1016/0097-3165(95)90091-8 . ISSN  0097-3165.
70. Savage, Carla Diane (1997-01-16). «Длинные циклы в средних двух уровнях булевой решетки». Ars Combinatoria . 35 (A). North Carolina State University, Raleigh, North Carolina, USA: 97–108. CiteSeerX 10.1.1.39.2249 . ISSN  0381-7032. S2CID  15975960. Архивировано из оригинала 2020-05-13 . Получено 2020-05-13 . (15 страниц)
71. Goddyn, Luis (1999). "MATH 343 Applied Discrete Math Supplementary Materials" (PDF) . Кафедра математики, Университет Саймона Фрейзера . Архивировано из оригинала (PDF) 2015-02-17.
72. Савада, Джозеф «Джо»; Вонг, Деннис Чи-Хим (2007). «Быстрый алгоритм генерации кодов Беккета–Грея». Электронные заметки по дискретной математике . 29 : 571–577. doi :10.1016/j.endm.2007.07.091.
73. Ричардс, Ричард Колер (январь 1971). «Snake-in-the-Box Codes». Написано в Эймсе, Айова, США. Digital Design . Нью-Йорк, США: Wiley-Interscience , John Wiley & Sons, Inc. стр. 206–207. ISBN 0-471-71945-5. LCCN  73-147235.(12+577+1 страниц)
74. NZ 264738, Спеддинг, Норман Брюс, "A position encoder", опубликовано 1994-10-28 ^{[ неудачная проверка ]} 
75. Спеддинг, Норман Брюс (1994-10-28). "Нижеследующее является копией предварительного патента, поданного от имени Industrial Research Limited 1994-10-28 – Патент Новой Зеландии 264738" (PDF) . Industrial Research Limited. Патент Новой Зеландии 264738. Архивировано (PDF) из оригинала 2017-10-29 . Получено 2018-01-14 .
76. Хильтген, Ален П.; Патерсон, Кеннет Г.; Брандестини, Марко (сентябрь 1996 г.). «Однодорожечные коды Грея». Труды IEEE по теории информации . 42 (5): 1555–1561. doi :10.1109/18.532900. Zbl  857.94007.
77. Hiltgen, Alain P.; Paterson, Kenneth G. (сентябрь 2001 г.). «Single-Track Circuit Codes» (PDF) . IEEE Transactions on Information Theory . 47 (6): 2587–2595. CiteSeerX 10.1.1.10.8218 . doi :10.1109/18.945274. Архивировано (PDF) из оригинала 2018-01-15 . Получено 2018-01-15 . 
78. Эцион, Туви; Шварц, Моше (ноябрь 1999 г.) [17.05.1998]. «Структура однодорожечных кодов Грея» (PDF) . Труды IEEE по теории информации . IT-45 (7): 2383–2396. CiteSeerX 10.1.1.14.8333 . doi :10.1109/18.796379. Архивировано (PDF) из оригинала 15.01.2018 . Получено 15.01.2018 . Технический отчет CS0937 Архивировано 15.12.2018 на Wayback Machine
79. Sillke, Torsten (1997) [1993-03-01]. "Gray-Codes with few tracks (a question of Marco Brandestini)". Архивировано из оригинала 29-10-2017 . Получено 29-10-2017 .
80. Etzion, Tuvi; Paterson, Kenneth G. (май 1996 г.). "Near Optimal Single-Track Gray Codes" (PDF) . IEEE Transactions on Information Theory . IT-42 (3): 779–789. CiteSeerX 10.1.1.14.1527 . doi :10.1109/18.490544. Архивировано (PDF) из оригинала 2016-10-30 . Получено 2018-04-08 . 
81. Раски, Фрэнк ; Уэстон, Марк (2005-06-18). "Обзор диаграмм Венна: симметричные диаграммы". Динамические обзоры. Электронный журнал комбинаторики . doi : 10.37236/26 .
82. Альсиаторе, Дэвид Г.; Хистанд, Майкл Б. (1999). Мехатроника. McGraw–Hill Education – Европа. ISBN 978-0-07-131444-2.
83. Уильямс, Гэри (2008-07-25). «'однодорожечный серый код' искали для кодирования 360 градусов с помощью 9 датчиков». Обмен экспертами .
84. Бауэр, Флориан. "9-битный абсолютный однодорожечный вращающийся энкодер с кодом Грея". Thingiverse .
85. Кришна (2008-05-11). "Код Грея для QAM". Архивировано из оригинала 2017-10-29 . Получено 2017-10-29 .
86. Стрэнг, Томас; Дамманн, Армин; Рёкль, Матиас; Пласс, Саймон (октябрь 2009 г.). Использование кодов Грея в качестве идентификаторов местоположения (PDF) . 6. GI/ITG KuVS Fachgespräch Ortsbezogene Anwendungen und Dienste (на английском и немецком языках). Оберпфаффенхофен, Германия: Институт связи и навигации Немецкого аэрокосмического центра (DLR). CiteSeerX 10.1.1.398.9164 . Архивировано (PDF) из оригинала 1 мая 2015 г. Проверено 16 декабря 2020 г. (5/8 страниц) [10]
    • Томас Стрэнг и др. (октябрь 2009 г.). «Использование кодов Грея в качестве идентификаторов местоположения» (PDF) . ResearchGate (Аннотация) (на немецком и английском языках). Архивировано из оригинала 2020-09-03.
87. Греферат, Маркус (2009). «Введение в теорию кольцевого линейного кодирования». В Сала, Массимилиано; Мора, Тео; Перре, Людовик; Саката, Сёдзиро; Траверсо, Карло (ред.). Базисы Грёбнера, кодирование и криптография . Springer Science & Business Media . стр. 220. ISBN 978-3-540-93806-4.
88. Соле, Патрик (2016). «Коды Кердока и Препарата». В Хазевинкель, Михиль (ред.). Энциклопедия математики . Springer Science+Business Media . ISBN 978-1-4020-0609-8. Архивировано из оригинала 2017-10-29.
89. Сполдинг, Карл П. (1965-07-12). Как использовать датчики положения вала . Монровия, Калифорния, США: Datex Corporation.(85 страниц)
90. Wheeler, Edwin L. (1969-12-30) [1968-04-05]. Аналого-цифровой кодер (PDF) . Нью-Йорк, США: Conrac Corporation. Патент США 3487460A . Серийный номер 719026 (397812). Архивировано (PDF) из оригинала 2020-08-05 . Получено 2018-01-21 . стр. 5, левый столбец 9, строки 15–22: ​​[…] Код MOA-GILLHAM по сути является комбинацией кода Грея, обсуждавшегося выше, и хорошо известного кода Datex; код Datex раскрыт в патенте США 3,165,731. Схема такова, что код Datex определяет биты для подсчета единиц кодировщика, а код Грея определяет биты для каждой из декад высшего порядка, десятков, сотен и т. д. […](11 страниц)
91. Доктер, Фолкерт; Штайнхауэр, Юрген (1973-06-18). "2.4. Кодирование чисел в двоичной системе". Цифровая электроника. Техническая библиотека Philips (PTL) / Macmillan Education (Переиздание 1-го английского издания). Эйндховен, Нидерланды: The Macmillan Press Ltd. / NV Philips' Gloeilampenfabrieken . стр. 32, 39, 50–53. doi :10.1007/978-1-349-01417-0. ISBN 978-1-349-01419-4. СБН 333-13360-9. Получено 2020-05-11 . стр. 53: […] Код Datex […] использует код О'Брайена II в каждом десятилетии и отраженные десятичные числа для десятичных переходов. Для дальнейшей обработки необходимо преобразование кода в натуральную десятичную запись. Поскольку код О'Брайена II образует дополнение 9s , это не вызывает особых трудностей: всякий раз, когда кодовое слово для десятков представляет нечетное число, кодовые слова для десятичных единиц даются как дополнение 9s путем инверсии четвертой двоичной цифры. […]^{[ постоянная мертвая ссылка ]} (270 страниц)
92. Доктер, Фолкерт; Штайнхауэр, Юрген (1975) [1969]. «2.4.4.6. Коды Einschrittige». Digitale Elektronik in der Meßtechnik und Datenverarbeitung: Theoretische Grundlagen und Schaltungstechnik . Philips Fachbücher (на немецком языке). Том. Я (улучшенное и дополненное 5-е изд.). Гамбург, Германия: Deutsche Philips GmbH . С. 41, 48, 51, 58, 60–61. ISBN 3-87145-272-6.(xii+327+3 страницы)
93. «…точное измерение уровня жидкости – на ЛЮБОМ РАССТОЯНИИ!». Нефтеперерабатывающий завод (реклама). 33 (9). Gulf Publishing Company : 368. Сентябрь 1954 г. ISSN  0096-6517. стр. 368: […] Полная диспетчерская операция, измерение и дистанционное управление интегрируются в одну единую унифицированную систему, когда установлена ​​система телеметрии с импульсным кодом «Varec». […]
94. Бишап, Бернард В.; Репета, Энтони А.; Джиарриццо, Фрэнк К. (1968-08-13) [1963-04-03]. «Система телеизмерения и контроля, имеющая обычно непрерывные сигналы телеизмерения». Leeds and Northrup Co. US3397386A.[11]
95. "Формат импульса кодировщика". Руководство по установке и эксплуатации микропередатчика модели 1900 с четырьмя проводами (PDF) . Cypress, Калифорния, США: Whessoe Varec, Inc. Январь 1993 г. [1991-07-01]. стр. 04-4–04-8. 33-08461. Архивировано (PDF) из оригинала 2020-05-16 . Получено 2020-05-16 .(38 страниц) (Примечание. Позиция 5 для «Дюймов» на странице 04-8 должна быть «0111», а не «1111».)
96. "2.2.3.3 Формат данных уровня MSP". Varec Model 1900 – Micro 4-Wire Transmitter (BSAP to Mark / Space Protocol (MSP)) – Application Notes (PDF) . Emerson Electric . стр. 11–14. Архивировано (PDF) из оригинала 2020-05-16 . Получено 2020-05-16 .(vi+33 страницы)
97. Wightman, Eric Jeffrey (1972). "Глава 6. Измерение смещения". Instrumentation in Process Control (1-е изд.). Лондон, Великобритания: Butterworth & Co (Publishers) Ltd. стр. 122–123. ISBN 0-408-70293-1. стр. 122–123: […] Другие формы кода также хорошо известны. Среди них — код Королевского радиолокационного учреждения ; Избыточный трехдесятичный код ; Код Гиллхэма , рекомендованный ИКАО для автоматической передачи высоты в целях управления воздушным движением ; Код Петерика и Код Лесли и Рассела Национальной инженерной лаборатории . Каждый из них имеет свои особые достоинства, и они предлагаются в качестве опций различными производителями кодеров. […](12+367+5 страниц)
98. Филлипс, Даррил (2012-07-26) [1998]. "Altitude – MODEC ASCII". AirSport Avionics. Архивировано из оригинала 2012-07-26.
99. Стюарт, К. (2010-12-03). "Aviation Gray Code: Gillham Code Explained". Custom Computer Services (CCS). Архивировано из оригинала 2018-01-16 . Получено 2018-01-14 .
100. Лесли, Уильям "Билл" HP; Рассел, А. (1964). Циклический прогрессивный десятичный код для простого перевода в десятичные и аналоговые выходы (Отчет). Ист-Килбрайд, Глазго, Великобритания: Национальная инженерная лаборатория . Отчет NEL 129.(17 страниц)
101. Лесли, Уильям "Билл" HP (1974). "Работа над NC в NEL". В Koenigsberger, Franz; Tobias, Stephen Albert (ред.). Труды Четырнадцатой международной конференции по проектированию и исследованию станков, 12–14 сентября 1973 г. The Macmillan Press Ltd. стр. 215–224 [215, 217]. doi :10.1007/978-1-349-01921-2_30. ISBN 978-1-34901921-2. LCCN  73-16545. SBN 333-14913-0. Архивировано из оригинала 2022-04-07 . Получено 2020-05-21 .
102. Хоклас, Арчибальд (1989-09-06) [1988-04-29]. «Abtastvorrichtung zur digitalen Wegoder Winkelmessung» (PDF) (на немецком языке). VEB Schiffselektronik Йоханнес Варнке  [ де ] . Патент ГДР DD271603A1. WP H 03 M / 315 194 8. Архивировано из оригинала (PDF) 18 января 2018 г. Проверено 18 января 2018 г. - через DEPATIS  [de] .[12] [13]
103. Хоклас, Арчибальд (2005). "Код Грея – Код единичного расстояния". Архивировано из оригинала 2018-01-15 . Получено 2018-01-15 .
104. Хоклас, Арчибальд (2005). «Gray-Kode – Einschrittiger Abtastkode» (на немецком языке). Архивировано из оригинала 15 января 2018 г. Проверено 15 января 2018 г.
105. Петерик, Эдвард Джон; Хопкинс, А. Дж. (1958). Некоторые недавно разработанные цифровые устройства для кодирования вращения валов (Техническая записка MS21). Фарнборо, Великобритания: Королевское авиационное учреждение (RAE).
106. «Дигитайзер как аналогово-цифровой Wandler в der Steuer-, Meß- und Regeltechnik» (PDF) . Технический центр . Relais, elektronische Geräte, Steuerungen (на немецком языке). № 13. Кёльн-Ниль, Германия: Франц Баумгартнер (FraBa). Май 1963 г., стр. 1–2. Архивировано из оригинала (PDF) 21 мая 2020 г. Проверено 21 мая 2020 г. стр. 1–2: […] Die Firma Harrison Reproduction Equipment, Фарнборо/Англия […] шляпа в jahrelanger Entwicklung in Zusammenarbeit mit der Britischen Luftwaffe und britischen Industriebetrieben den mechanischen Digitizer […] zu einer technischen Reife gebracht, die fast allen Anforderungen […] генюгт. […] Um bei der dezimalen Entschlüsselung des verwendeten Binärcodes zu eindeutigen und bei der Übergabe von einer Dezimalstelle zur anderen in der Reihenfolge immer richtigen Ergebnissen zu commen, wurde ein spezieller Code entwickelt, der jede Möglichkeit einer ssage durch sein Prinzip ausschließt und der ausserdem durch seinen Aufbau eine relative einfache Entschlüsselung erlaubt. Кодекс базируется на Кодексе Петерика. […](4 страницы)
107. Charnley, CJ; Bidgood, RE; Boardman, GET (октябрь 1965 г.). «Проект пневматического позиционного энкодера» (PDF) . Тома трудов IFAC . 2 (3). Колледж аэронавтики, Крэнфилд, Бедфорд, Англия: 75–88. doi :10.1016/S1474-6670(17)68955-9. Глава 1.5 . Получено 14.01.2018 .^{[ постоянная мертвая ссылка ]}
108. Холлингдейл, Стюарт Х. (1958-09-19). «Сессия 14. Обработка данных». Applications of Computers (Доклад конференции). Atlas – Application of Computers, Ноттингемский университет, 15–19 сентября 1958 г. Архивировано из оригинала 25.05.2020 . Получено 25.05.2020 .
109. O'Brien, Joseph A. (май 1956) [1955-11-15, 1955-06-23]. "Циклические десятичные коды для аналого-цифровых преобразователей". Труды Американского института инженеров-электриков, часть I: Связь и электроника . 75 (2). Bell Telephone Laboratories, Whippany, New Jersey, USA: 120–122. doi :10.1109/TCE.1956.6372498. ISSN  0097-2452. S2CID  51657314. Статья 56-21. Архивировано из оригинала 2020-05-18 . Получено 2020-05-18 .(3 страницы) (Примечание. Эта статья была подготовлена ​​для презентации на зимнем общем собрании AIEE в Нью-Йорке, США, с 30 января 1956 г. по 3 февраля 1956 г.)
110. Steinbuch, Карл В. , изд. (1962). Написано в Карлсруэ, Германия. Taschenbuch der Nachrichtenverarbeitung (на немецком языке) (1-е изд.). Берлин / Геттинген / Нью-Йорк: Springer-Verlag OHG . стр. 71–74, 97, 761–764, 770, 1080–1081. LCCN  62-14511.
111. Steinbuch, Карл В .; Вебер, Вольфганг; Хайнеманн, Трауте, ред. (1974) [1967]. Taschenbuch der Informatik – Band II – Struktur und Programmierung von EDV-Systemen . Taschenbuch der Nachrichtenverarbeitung (на немецком языке). Том. 2 (3-е изд.). Берлин, Германия: Springer Verlag . стр. 98–100. ISBN 3-540-06241-6. LCCN  73-80607.
112. Фосс, Фредерик А. (1960-12-27) [1954-12-17]. "Системы управления" (PDF) . International Business Machines Corp . Рис. 7, Рис. 8, Рис. 11. Патент США 2966670A . Серийный номер 475945. Архивировано (PDF) из оригинала 2020-06-21 . Получено 2020-08-05 .(14 страниц) (Примечание. Автор назвал свой код 2*-4-2-1 (+9-±7-±3-±1) отраженным десятичным кодом.)
113. Фосс, Фредерик А. (декабрь 1954 г.). «Использование отраженного кода в цифровых системах управления». Труды IRE по электронным компьютерам . EC-3 (4): 1–6. doi :10.1109/IREPGELC.1954.6499244. ISSN  2168-1740.(6 страниц)
114. Эванс, Дэвид Сильвестр (1958). "[название неизвестно]". Труды . 10–12. Институт измерений и контроля: 87.(Примечание. Код Уоттса назывался WRD-кодом или Watts Reflected Decimal, чтобы отличать его от других кодов, используемых в Hilger & Watts Ltd. )
115. Benjamin, PW; Nicholls, GS (1963). "3.2.2 Электромеханические цифровые преобразователи". Измерение нейтронных спектров путем полуавтоматического сканирования протонов отдачи в фотографических эмульсиях . Управление по атомной энергии Соединенного Королевства , Исследовательский центр атомного оружия , Великобритания: Министерство энергетики США . стр. 8–10, 19. Отчет AWRE № NR 5/63.[14] (23 страницы)
116. Klinkowski, James J. (1967-03-14) [1964-03-23]. "Electronic Diode Matrix Decoder Circuits" (PDF) . Детройт, Мичиган, США: Burroughs Corporation . Патент США 3309695A . Серийный номер 353845. Архивировано (PDF) из оригинала 2020-05-23 . Получено 2020-05-23 .(5 страниц) [15]
117. Klinkowski, James J. (1970-03-31) [1966-12-22]. "Binary-coded decimal signal converter" (PDF) . Детройт, Мичиган, США: Burroughs Corporation . Патент США 3504363A . Серийный номер 603926. Архивировано (PDF) из оригинала 2020-05-23 . Получено 2020-05-23 .(7 страниц)
118. "[название неизвестно]". Новости электротехнического проектирования . 12. Rogers Publishing Company . 1967. ISSN  0012-7515 .[16][17]
119. Tóth-Zentai, Györgyi (1979-10-05). "Некоторые проблемы угловых вращательных цифровых преобразователей". Periodica Polytechnica Electrical Engineering . 23 (3–4). Кафедра электронных технологий, Технический университет, Будапешт, Венгрия: 265–270 [266] . Получено 2020-05-23 .[18] (6 страниц) (Примечание. Показывает 6-значный код Уоттса.)
120. Savard, John JG (2018) [2006]. "Decimal Representations". quadibloc . Архивировано из оригинала 2018-07-16 . Получено 2018-07-16 .
121. Turvey, Jr., Frank P. (1958-07-29) [1956-05-17]. "Pulse-Count Coder" (PDF) . Nutley, New Jersey, USA: International Telephone and Telegraph Corporation . Патент США 2845617A . Серийный номер 585494. Архивировано (PDF) из оригинала 2020-05-23 . Получено 2020-05-23 .(5 страниц)
122. Glixon, Harry Robert (март 1957 г.). «Can You Take Advantage of the Cyclic Binary-Decimal Code?». Control Engineering . 4 (3). Technical Publishing Company , подразделение Dun-Donnelley Publishing Corporation, Dun & Bradstreet Corp .: 87–91. ISSN  0010-8049.(5 страниц)
123. Боруки, Лоренц; Диттманн, Иоахим (1971) [июль 1970, 1966, осень 1965]. «2.3 Общие коды в цифровой технике». Написано в Крефельде/Карлсруэ, Германия. Digitale Meßtechnik: Eine Einführung (на немецком языке) (2-е изд.). Берлин / Гейдельберг, Германия: Springer-Verlag . С. 10–23 [12–14]. дои : 10.1007/978-3-642-80560-8. ISBN 3-540-05058-2. LCCN  75-131547. ISBN 978-3-642-80561-5 . (viii+252 страницы) 1-е издание (Примечание. Как и Кеммерер, авторы описывают 6-битный 20-циклический код Гликсона.)
124. Каммерер, Вильгельм [на немецком языке] (май 1969 г.). «II.15. Структура: Informationsdarstellung im Automaten». Написано в Йене, Германия. Во Фрюхауфе, Ганс [на немецком языке] ; Каммерер, Вильгельм; Шредер, Курц; Винклер, Хельмут (ред.). Digitale Automaten – Theorie, Struktur, Technik, Programmieren . Elektronisches Rechnen und Regeln (на немецком языке). Том. 5 (1-е изд.). Берлин, Германия: Akademie-Verlag GmbH . п. 173. Лицензия №. 202-100/416/69. Номер заказа. 4666 ES 20 К 3.(Примечание. Существует также второе издание 1973 года. Подобно Боруцки и Диттманну, но не называя его кодом Гликсона, автор создает 20-циклический тетрадический код из кода Гликсона и вариант кода Гликсона с инвертированным старшим битом.)
125. Пол, Матиас Р. (10 августа 1995 г.) [1994]. «Unterbrechungsfreier Schleifencode» [Код непрерывного цикла]. 1.02 (на немецком языке) . Проверено 11 февраля 2008 г.(Примечание. Автор назвал этот код Schleifencode (по-английски: «циклический код»). Он отличается от кода Грея BCD только кодировкой состояния 0, что делает его циклическим кодом единичного расстояния для приложений с полным вращением. Избежание шаблона кода «все нули» позволяет проводить самотестирование цикла и использовать линии данных для бесперебойного распределения питания.)
126. Клар, Райнер (1 февраля 1970 г.). Digitale Rechenautomaten – Eine Einführung [ Цифровые компьютеры – Введение ]. Sammlung Göschen (на немецком языке). Том. 1241/1241а (1-е изд.). Берлин, Германия: Вальтер де Грюйтер и компания / GJ Göschen'sche Verlagsbuchhandlung  [de] . п. 17. ISBN 3-11-083160-0. . Архивный номер 7990709. Архивировано из оригинала 2020-06-01 . Получено 2020-04-13 .(205 страниц) (Примечание. Переиздание первого издания 2019 года доступно под ISBN 3-11002793-3 , 978-3-11002793-8 . Существует также переработанное и расширенное 4-е издание.) 
127. Клар, Райнер (1989) [1988-10-01]. Digitale Rechenautomaten – Eine Einführung in die Struktur von Computerhardware [ Цифровые компьютеры – Введение в структуру компьютерного оборудования ]. Sammlung Göschen (на немецком языке). Том. 2050 г. (4-е переработанное изд.). Берлин, Германия: Walter de Gruyter & Co. 28. ISBN 3-11011700-2.(320 страниц) (Примечание. Автор назвал этот код Einheitsabstandscode (англ. «код единичного расстояния»). Поменяв местами две строки битов и инвертировав одну из них, его можно преобразовать в код О'Брайена II, тогда как поменяв местами и инвертировав две строки битов, его можно преобразовать в код Петерика.)

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

• Ричардс, Ричард Колер (1955). Арифметические операции в цифровых компьютерах (5-е изд.). Нью-Йорк, США: D. Van Nostrand Co., Inc.
• Ричардс, Ричард Колер (1967). Электронные цифровые компоненты и схемы . D. Van Nostrand Co., Inc. стр. 490, 500–504, 510–511.
• Блэк, Пол Э. (25.02.2004). "Код Грея". NIST .
• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). "Раздел 22.3. Коды Грея". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк, США: Cambridge University Press . ISBN 978-0-521-88068-8. Архивировано из оригинала 2011-08-11 . Получено 2011-08-18 .
• Savage, Carla Diane (1997). «Обзор комбинаторных кодов Грея». Обзор SIAM . 39 (4). Общество промышленной и прикладной математики (SIAM): 605–629. Bibcode : 1997SIAMR..39..605S. CiteSeerX  10.1.1.39.1924 . doi : 10.1137/S0036144595295272. JSTOR  2132693. S2CID  6375360.
• Wilf, Herbert Saul (1989). "Главы 1–3". Комбинаторные алгоритмы: обновление . Общество промышленной и прикладной математики (SIAM). ISBN 0-89871-231-9.
• Dewar, Megan; Stevens, Brett (2012-08-29). Ordering Block Designs – Gray Codes, Universal Cycles and Configuration . CMS Books in Mathematics (1-е изд.). Нью-Йорк, США: Springer Science+Business Media . doi :10.1007/978-1-4614-4325-4. ISBN 978-1-46144324-7. ISSN  1613-5237.
• Максфилд, Клайв "Макс" (01.10.2012) [28.05.2011]. "Основы кода Грея". Design How-To . EETimes . Часть 1. Архивировано из оригинала 30.10.2017 . Получено 30.10.2017 .Часть 2 Часть 3
• Уоррен, младший, Генри С. (2013). «Глава 13: Gray Code». Hacker's Delight (2-е изд.). Addison Wesley – Pearson Education, Inc. стр. 311–317. ISBN 978-0-321-84268-8.(7 страниц)
• Зиновик, Игорь; Кренинг, Даниэль; Чебиряк, Юрий (2008-03-21). «Вычисление двоичных комбинаторных кодов Грея с помощью исчерпывающего поиска с помощью SAT Solvers». Труды IEEE по теории информации . 54 (4). IEEE : 1819–1823. doi :10.1109/TIT.2008.917695. hdl : 20.500.11850/11304 . S2CID  2854180.(5 страниц)
• O'Brien, Joseph A. (июнь 1957 г.). «Трансляторы двоично-десятичного кода с единицы расстояния». IRE Transactions on Electronic Computers . EC-6 (2): 122–123. doi :10.1109/TEC.1957.5221585. ISSN  0367-9950 . Получено 25.05.2020 .(2 страницы)
• Barr, KG (март 1981 г.). «Десятичный код Грея – легко преобразуется для кодирования положения вала» (PDF) . Wireless World . Том 87, № 1542. Факультет естественных наук, Университет Вест-Индии . стр. 86–87. Архивировано (PDF) из оригинала 28.07.2020 . Получено 28.07.2020 .

Внешние ссылки

• Демонстрация «Кода Грея» Михаэля Шрайбера, Wolfram Demonstrations Project (с реализацией Mathematica). 2007.
• Словарь алгоритмов и структур данных NIST: Код Грея.
• Руководство по эволюционным вычислениям для автостопщиков, вопрос 21: Что такое коды Грея и почему они используются?, включая код на языке C для преобразования между двоичным кодом и BRGC.
• Драгос А. Харабор использует коды Грея в 3D-дигитайзере.
• Однодорожечные коды Грея, двоичные цепные коды (Ланкастер, 1994) и регистры сдвига с линейной обратной связью полезны для определения абсолютного положения на однодорожечном вращающемся энкодере (или другом датчике положения).
• Колонка AMS: коды Грея
• Генератор колес оптического энкодера
• ProtoTalk.net – Понимание квадратурного кодирования – более подробно описывает квадратурное кодирование с упором на робототехнические приложения.