Код Грея
Код Грея (англ. Gray code) — двоичный код, использующий символы 0 и 1, в котором две соседние кодовые комбинации различаются между собой значением символа только в одном разряде (одношаговый код).
Иными словами, расстояние Хэмминга (мера различия между соседними кодовыми комбинациями) равно единице.
Строго говоря, существует множество кодов Грея для систем счисления с любым основанием и в общем виде можно записать представление этого множества как {Gray (n, k)}, где
n — основание системы счисления,
k — число цифр в коде.
Однако в большинстве случаев под термином «код Грея» понимают именно бинарный код, в котором . В этом случае, поскольку основание системы является чётным числом, код имеет «зеркальную» циклическую структуру, то есть является рефлексивным (от лат. reflexio — обращение назад, отражение)[1].
История создания кода Грея[править]
Код назван в честь исследователя Фрэнка Грея, работавшего в лаборатории Bell labs. В 1947 году была подана заявка на патент под названием «импульсный код связи», которая была удовлетворена в 1953 году (патент США № 2632058)[2]. Код назван «рефлексивным» (отражённым) из-за того, что первая половина значений при изменении порядка эквивалентна второй половине, за исключением старшего бита. Старший бит просто инвертируется. При делении каждой новой половины пополам это свойство сохраняется.
Отраженный двоичный код применялся для решения математических задач, а затем получил использование в технике, в частности, для защиты от ложного прочтения состояния электромеханических и электронных переключателей, когда необходимо исключить логические гонки.
В настоящее время код Грея используется при составлении алгоритмов для создания карт Карно, которые, в свою очередь, используются в качестве инженерного инструмента при проектировании комбинационных и последовательностных логических схем. Кроме того, код Грея применяется для упрощения выявления и исправления ошибок в системах связи, а также для формирования последовательности импульсов в линейных и круговых датчиках отсчёта — энкодерах[3].
Помимо того, Код Грея используется для адресации цилиндров дискового массива. В них код Грея является составной частью меток, размещенных на треках, определяющих номер цилиндра[4].
Преимущества кода Грея[править]
.svg)
Характерной особенностью кода Грея является изменение только одной позиции при переходе от одной кодовой комбинации к другой. Это свойство широко используют как для построения некоторых типов АЦП, где он позволяет свести к «единице» младшего разряда погрешность неоднозначности при считывании, так и для решения других задач, требующих минимизировать погрешность перехода.
Если при преобразовании линейных и угловых перемещений использовать обычный двоичный код без дополнительного синхроимпульса, то расположенные рядом кодовые комбинации могут различаться одновременно в нескольких разрядах, поскольку двоичный код является многошаговым. Например, если на границе перехода возникла совокупность комбинаций 0111 и 1000, различающихся во всех разрядах, то за счёт неточности изготовления или установки считывателя, или неодновременности срабатывания ключей может быть прочитана ложная комбинация «нулей» и «единиц». Допустим, что третий справа считыватель сработал с отставанием, тогда в какой-то момент вместо комбинации 1000 будет прочитана комбинация 1100. Применение кода Грея для решения подобных задач позволяет свести ошибки к минимуму[5].
Представление информации в коде Грея[править]
Ниже на иллюстрации приведены несколько вариантов генерации кода Грея путём изменения соседних 4-битовых последовательностей таким образом, что при переходе позиции меняется только один бит.
Ниже представлены основные алгоритмы преобразование двоичного числа в код Грея и обратного преобразования — кода Грея в двоичное число[6][7].
Алгоритм построения кода Грея[править]
Преобразование двоичного числа в код Грея можно реализовать поразрядной реализацией логической функции «исключающее ИЛИ» с тем же числом, сдвинутым вправо на один бит, в котором старший разряд заполняется нулём: , где — операция «исключающее ИЛИ». Биты нумеруются справа налево, начиная с младшего.
Например, необходимо преобразовать соседние двоичные числа 10112 = (1110) и 11002 = (1210) в код Грея:
- сдвинем первое исходное число 1011 вправо на один бит, получим двоичную комбинацию 0101;
- далее применим поразрядную реализацию функции «исключающее ИЛИ» над исходным числом 1011 и комбинацией сдвига 0101:
1011
0101
----
1110G -> результат перевода двоичного числа 10112 в код Грея.
Аналогичная процедура преобразования второго двоичного числа 11002 даст в коде Грея результат 1010G.
В итоге полученные из соседних двоичных чисел комбинации кода Грея 1110G и 1010G отличаются друг от друга в одном двоичном разряде (третьем справа).
Ниже приведена схема поразрядного преобразования двоичного числа в код Грея на логических элементах XOR («исключающее ИЛИ») и таблица представления чисел в двоичном коде и в коде Грея.
| Двоичное число | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Код Грея | 0000 | 0001 | 0011 | 0010 | 0110 | 0111 | 0101 | 0100 | 1100 | 1101 | 1111 | 1110 | 1010 | 1011 | 1001 | 1000 |
Алгоритм преобразования двоичного числа в код Грея, записанный на языке C++, выглядит следующим образом: <source lang="c++"> unsigned int grayencode(unsigned int g) {
return g ^ (g >> 1);
} </source>
Преобразование кода Грея в двоичное число[править]
Поскольку информация, выраженная в виде кода Грея, не несёт реальной числовой информации, перед дальнейшей обработкой её необходимо преобразовать в стандартный бинарный код — двоичное число.
Для перевода кода Грея в двоичное число необходимо выполнение следующих правил:
- осуществляют сдвиг исходного числа в коде Грея на один разряд вправо и производят поразрядное сложение по модулю 2 (логическая операция «Исключающее ИЛИ») с исходным числом;
- полученное результирующее число сдвигают на 2 разряда вправо и складывают по модулю 2 с результатом предыдущего сложения;
- результат предыдущей операции сдвигают на 4 разряда вправо и складывают по модулю 2 с результатом предыдущего сложения;
- очередное сложение результата предыдущей операции осуществляют с этим же числом, сдвинутым на количество разрядов, определяемое геометрической прогрессией , где n — номер шага сложения.
Операции прекращают, когда очередной сдвиг приводит к обнулению числа. Результат последнего сложения представляет собой искомое число в двоичном коде.
Пример перевода восьмиразрядного кода Грея в двоичное число:
10110011G -> исходный код 1011001 -> сдвиг на 20 (на 1 разряд) -------- 11101010 111010 -> сдвиг на 21 (на 2 разряда) -------- 11010000 1101 -> сдвиг на 22 (на 4 разряда). Следующий сдвиг не производится, так как приведёт к обнулению числа -------- 110111012 -> двоичное число
Ниже приведена схема поразрядного преобразователя из кода Грея в двоичное число, реализованная на логических элементах XOR:
Ниже приведена функция на языке С++, реализующая данный алгоритм. Она осуществляет последовательный сдвиг вправо и суммирование исходного двоичного кода до тех пор, пока очередной сдвиг не обнулит слагаемое. <source lang="cpp"> unsigned int graydecode(unsigned int gray) {
unsigned int bin;
for (bin = 0; gray; gray >>= 1) {
bin ^= gray;
}
return bin;
} </source>
Построение многомерного кода Грея[править]
Существуют алгоритмы, позволяющие по -битовому коду Грея построить n-битовый код. К алгоритму такого типа относится рекурсивная генерация путём отражения исходных комбинаций битов и добавления к ним префиксов 0 или 1 (фр. prefix от лат. praefixus — «прикреплённый впереди»). Порядок действий выглядит следующим образом:
- Отражение исходной комбинации битов;
- Добавление к исходной комбинации префикса 0;
- Добавление к отражённой комбинации префикса 1;
- Объединение кодовых комбинаций, полученных в пунктах 2 и 3.
Например, создание списка комбинаций при из списка комбинаций при выглядит следующим образом:
| Исходная комбинация, | 00 | 01 | 11 | 10 | ||||
| Зеркальное отражение исходной комбинации | 10 | 11 | 01 | 00 | ||||
| Добавление к исходной комбинации префикса 0 | 00 | 001 | 011 | 010 | ||||
| Добавление к отражённой комбинации префикса 1 | 110 | 111 | 101 | 100 | ||||
| Объединение кодовых комбинаций, | 000 | 001 | 011 | 010 | 110 | 111 | 101 | 100 |
Варианты кода Грея[править]
К вариантам кода Грея можно отнести следующие его разновидности:
- сбалансированный код Грея;
- двумерный код Грея.
Сбалансированный код Грея[править]
Любые датчики имеют ограниченный ресурс по количеству переключений, поэтому в ряде случаев применяют так называемый сбалансированный код Грея c равномерным распределением количества переходов по разрядам.
Ниже представлен сбалансированный 4-битовый код Грея с 16 переходами, в течение которых каждый разряд переключается четырежды:
- 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 переходами, переключение разрядов не может быть равномерно распределено по переходам. В этом случае четыре позиции будут иметь по шесть переходов, а одна — восемь, поэтому для построения многоразрядного сбалансированного кода Грея применяют специальные алгоритмы, заключающиеся в индуктивном построении -значного кода Грея[8].
Двумерный код Грея[править]
Двумерные коды Грея используются в свя́зи для минимизации количества битовых ошибок в соседних точках квадратурной амплитудной модуляции (QAM, от англ. Quadrature amplitude modulation) в созвездии. При типичном кодировании соседние точки совокупности по горизонтали и вертикали отличаются на один бит, а соседние точки по диагонали отличаются на 2 бита.
Самые простые и наиболее часто используемые комбинации QAM состоят из точек, расположенных в квадрате, то есть 16-QAM, 64-QAM и 256-QAM (чётные степени двойки).
Двумерные коды Грея также используются в схемах идентификации местоположения. Например, код применяется к географическим картам в проекции Меркатора для расчета расстояния, объединяя характеристики расстояния Хэмминга с циклическим продолжением проекции Меркатора[9].
Одношаговые двоично-десятичные коды[править]
Существуют двоично-десятичные коды (BCD), которые также являются одношаговыми, то есть функциональными вариантами кода Грея[10].
Всякий четырехбитовый одношаговый код для изображения десятичных цифр можно вписать в карту Вейча-Карно следующим образом:
- разметить столбцы и строки карты комбинациями двухбитового кода Грея и поставить в соответствие каждой клетке четырехбитовую комбинацию из битов столбца, за которыми следуют биты строки;
- вписать десятичные цифры от 0 до 9 в карту так, чтобы соседние цифры оказались в смежных клетках, а цифра 9 была в клетке, смежной с цифрой 0, в результате получим один из возможных одношаговых кодов.
Например, симметричное расположение десятичных цифр, показанное в карте ниже, и построенный по ней четырёхбитовый одношаговый код выглядят следующим образом:
| 00 | 01 | 11 | 10 | |
| 00 | 0 | - | - | 9 |
| 01 | 1 | - | - | 8 |
| 11 | 2 | - | - | 7 |
| 10 | 3 | 4 | 5 | 6 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0000 | 0001 | 0011 | 0010 | 0110 | 1110 | 1010 | 1011 | 1001 | 1000 |
Ниже приведена таблица вариантов одношаговых двоично-десятичных кодов[11].
| Код Гликсона |
Коды О’Брайена | Смещённый код Грея |
Коды Томпкинса | Код Петерика | ||
|---|---|---|---|---|---|---|
| 0000 | 0000 | 0001 | 0010 | 0000 | 0010 | 0101 |
| 0001 | 0001 | 0011 | 0110 | 0001 | 0011 | 0001 |
| 0011 | 0011 | 0010 | 0111 | 0011 | 0111 | 0011 |
| 0010 | 0010 | 0110 | 0101 | 0010 | 0101 | 0010 |
| 0110 | 0110 | 0100 | 0100 | 0110 | 0100 | 0110 |
| 0111 | 1110 | 1100 | 1100 | 1110 | 1100 | 1110 |
| 0101 | 1010 | 1110 | 1101 | 1111 | 1101 | 1010 |
| 0100 | 1011 | 1010 | 1111 | 1101 | 1001 | 1011 |
| 1100 | 1001 | 1011 | 1110 | 1100 | 1011 | 1001 |
| 1000 | 1000 | 1001 | 1010 | 1000 | 1010 | 1101 |
Смещённый код Грея представляет собой код Грея, в котором исключены первые три и последние три кодовые комбинации из полного 16-позиционного набора четырёхбитового кода. Второй код О’Брайена, второй код Томпкинса и код Петерика не используют комбинации «0000» и «1111», что предоставляет практические преимущества.
Источники[править]
- ↑ КОД ГРЕЯ. Проверено 11 апреля 2024.
- ↑ Pulse code communication (англ.). Unite States Patent and Trademark offise (1953-03-17). Проверено 12 апреля 2024.
- ↑ Н. И. Сорока, Г. А. Кривинченко Коды и кодирование. Конспект лекций. Министерство образования Республики Беларусь. Проверено 11 апреля 2024.
- ↑ Код Грея и его использование в дисковых накопителях. Проверено 27 апреля 2024.
- ↑ Белоусов Аркадий Системы счисления: код Грея. Проверено 19 апреля 2024.
- ↑ Середа С. Н. Алгоритмы построения кода Грея. Муромский институт. Владимирский государственный университет: Владимирский государственный университет. Проверено 19 апреля 2024.
- ↑ Чепкунова Е. Г. ПОСОБИЕ ДЛЯ ПОДГОТОВКИ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ «ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ» РАЗДЕЛ «КОДИРОВАНИЕ ИНФОРМАЦИИ» / канд. техн. наук, доц. КНИТУ Шлеймович М.И.. — Казань: Казанский университет, 2012. — 92 с.
- ↑ Girish S. Bhat Balanced Gray Codes (англ.) // The Electronic Journal of Combinatorics. — Department of Computer ScienceNorth Carolina State University, 1996.
- ↑ Thomas Strang, Armin Dammann, Matthias Röckl, Simon Plass Using Gray codes as Location Identifiers (англ.) (October 2009). Проверено 18 апреля 2024.
- ↑ В. Г. Кнорринг Теоретические основы цифровой измерительной техники. Учебное пособие. — СПб.: Санкт-Петербургский Государственный политехнический университет. — С. 49—52. — 145 с.
- ↑ Gray code. BCD codes (binary coded decimal) (англ.). Проверено 19 апреля 2024.
Литература[править]
- А. Л. Пережогин, И. С. Быков Обзор конструкций и свойств кодов Грея// Математические вопросы кибернетики. Вып. 20. — М.: ФИЗМАТЛИТ, 2022. — 21 с.
- Баранкова И. И., Коновалов М. В. Теория информации. Кодирование. (Электронный ресурс) / Швидченко Д. В. — Магнитогорск: Магнитогорский государственный технический университет, 2017. — 121 с. — ISBN 978-5-9967-1073-7.
|
Одним из источников этой статьи является статья в википроекте «Знание.Вики» («znanierussia.ru») под названием «Код Грея», находящаяся по адресам:
«https://baza.znanierussia.ru/mediawiki/index.php/Код_Грея» «https://znanierussia.ru/articles/Код_Грея». Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий.
|