Код Грея

Код Гре́я (англ. Gray code) — двоичный код, использующий символы 0 и 1, в котором две соседние кодовые комбинации различаются между собой значением символа только в одном разряде (одношаговый код). Иными словами, расстояние Хэмминга (мера различия между соседними кодовыми комбинациями) равно единице.

Строго говоря, существует множество кодов Грея для систем счисления с любым основанием и в общем виде можно записать представление этого множества как {Gray (n, k)}, где

n — основание системы счисления,

k — число цифр в коде.

Однако в большинстве случаев под термином «код Грея» понимают именно бинарный код, в котором $n=2$. В этом случае, поскольку основание системы является чётным числом, код имеет «зеркальную» циклическую структуру, то есть является рефлексивным (от лат. reflexio — обращение назад, отражение).

История создания и применение кода Грея

Фрэнк Грей

Код назван в честь исследователя Фрэнка Грея, работавшего в лаборатории Bell labs. В 1947 году была подана заявка на патент под названием «импульсный код связи», которая была удовлетворена в 1953 году (патент США № 2632058). Код назван «рефлексивным» (отражённым) из-за того, что первая половина значений при изменении порядка эквивалентна второй половине, за исключением старшего бита. Старший бит просто инвертируется. При делении каждой новой половины пополам это свойство сохраняется.

Отраженный двоичный код применялся для решения математических задач, а затем получил использование в технике, в частности, для защиты от ложного прочтения состояния электромеханических и электронных переключателей, когда необходимо исключить логические гонки. Французский инженер Эмиль Бодо применил код Грея в 1878 году в телеграфии, за эту работу он был награжден орденом Почётного легиона.

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

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

Преимущества кода Грея

Круговой энкодер с трёхбитовым кодом Грея

Характерной особенностью кода Грея является изменение только одной позиции при переходе от одной кодовой комбинации к другой. Это свойство широко используют как для построения некоторых типов аналого-цифровых преобразователей (АЦП), где он позволяет свести к «единице» младшего разряда погрешность неоднозначности при считывании, так и для решения других задач, требующих минимизировать погрешность перехода.

Если при преобразовании линейных и угловых перемещений использовать обычный двоичный код без дополнительного синхроимпульса, то расположенные рядом кодовые комбинации могут различаться одновременно в нескольких разрядах, поскольку двоичный код является многошаговым. Например, если на границе перехода возникла совокупность комбинаций 0111 и 1000, различающихся во всех разрядах, то за счёт неточности изготовления или установки считывателя, или неодновременности срабатывания ключей может быть прочитана ложная комбинация «нулей» и «единиц». Допустим, что третий справа считыватель сработал с отставанием, тогда в какой-то момент вместо комбинации 1000 будет прочитана комбинация 1100. Применение кода Грея для решения подобных задач позволяет свести ошибки к минимуму.

Представление информации в коде Грея

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

Ниже представлены основные алгоритмы преобразование двоичного числа в код Грея и обратного преобразования — кода Грея в двоичное число.

Алгоритм построения кода Грея

Преобразование двоичного числа в код Грея можно реализовать поразрядной реализацией логической функции «исключающее ИЛИ» с тем же числом, сдвинутым вправо на один бит, в котором старший разряд заполняется нулём: $g_{i}=b_{i}\oplus b_{i+1}$, где $\oplus$ — операция «исключающее ИЛИ». Биты нумеруются справа налево, начиная с младшего.

Например, необходимо преобразовать соседние двоичные числа 1011₂ = (11₁₀) и 1100₂ = (12₁₀) в код Грея:

• сдвинем первое исходное число 1011 вправо на один бит, получим двоичную комбинацию 0101;
• далее применим поразрядную реализацию функции «исключающее ИЛИ» над исходным числом 1011 и комбинацией сдвига 0101:

  1011
$\oplus$
  0101
  ----
  1110G -> результат перевода двоичного числа 10112 в код Грея.

Аналогичная процедура преобразования второго двоичного числа 1100₂ даст в коде Грея результат 1010_G.
В итоге полученные из соседних двоичных чисел комбинации кода Грея 1110_G и 1010_G отличаются друг от друга в одном двоичном разряде (третьем справа).

Ниже приведена схема поразрядного преобразования двоичного числа в код Грея на логических элементах XOR («исключающее ИЛИ») и таблица представления чисел в двоичном коде и в коде Грея.

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

unsigned int grayencode(unsigned int g)
{
    return g ^ (g >> 1);
}

Преобразование кода Грея в двоичное число

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

Для перевода кода Грея в двоичное число необходимо выполнение следующих правил:

• осуществляют сдвиг исходного числа в коде Грея на один разряд вправо и производят поразрядное сложение по модулю 2 (логическая операция «Исключающее ИЛИ») с исходным числом;
• полученное результирующее число сдвигают на 2 разряда вправо и складывают по модулю 2 с результатом предыдущего сложения;
• результат предыдущей операции сдвигают на 4 разряда вправо и складывают по модулю 2 с результатом предыдущего сложения;
• очередное сложение результата предыдущей операции осуществляют с этим же числом, сдвинутым на количество разрядов, определяемое геометрической прогрессией $2^{n-1}$, где n — номер шага сложения.

Операции прекращают, когда очередной сдвиг приводит к обнулению числа. Результат последнего сложения представляет собой искомое число в двоичном коде.

Пример перевода восьмиразрядного кода Грея в двоичное число:

   10110011G -> исходный код
$\oplus$
    1011001  -> сдвиг на 20 (на 1 разряд)
   --------
   11101010
$\oplus$
     111010  -> сдвиг на 21 (на 2 разряда)
   --------
   11010000
$\oplus$
       1101  -> сдвиг на 22 (на 4 разряда). Следующий сдвиг не производится, так как приведёт к обнулению числа
   --------
   110111012 -> двоичное число

Ниже приведена схема поразрядного преобразователя из кода Грея в двоичное число, реализованная на логических элементах XOR:

Поразрядное преобразование кода Грея в двоичное число

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

unsigned int graydecode(unsigned int gray)
{
    unsigned int bin;
    for (bin = 0; gray; gray >>= 1) {
      bin ^= gray;
    }
    return bin;
}

Построение многомерного кода Грея

Существуют алгоритмы, позволяющие по $(n-1)$-битовому коду Грея построить n-битовый код. К алгоритму такого типа относится рекурсивная генерация путём отражения исходных комбинаций битов и добавления к ним префиксов 0 или 1 (фр. prefix от лат. praefixus — «прикреплённый впереди»). Порядок действий выглядит следующим образом:

1. Отражение исходной комбинации битов;
2. Добавление к исходной комбинации префикса 0;
3. Добавление к отражённой комбинации префикса 1;
4. Объединение кодовых комбинаций, полученных в пунктах 2 и 3.

Схематичное изображение построения многомерного кода Грея

Например, создание списка комбинаций при $n=3$ из списка комбинаций при $n=2$ выглядит следующим образом:

Исходная комбинация, $n=2$	00	01	11	10
Зеркальное отражение исходной комбинации					10	11	01	00
Добавление к исходной комбинации префикса 0	00	001	011	010
Добавление к отражённой комбинации префикса 1					110	111	101	100
Объединение кодовых комбинаций, $n=3$	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 переходами, переключение разрядов не может быть равномерно распределено по переходам. В этом случае четыре позиции будут иметь по шесть переходов, а одна — восемь, поэтому для построения многоразрядного сбалансированного кода Грея применяют специальные алгоритмы, заключающиеся в индуктивном построении $(n+2)$-значного кода Грея.

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

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

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

Самые простые и наиболее часто используемые комбинации QAM состоят из точек, расположенных в квадрате, то есть 16-QAM, 64-QAM и 256-QAM (чётные степени двойки).

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

Одношаговые двоично-десятичные коды

Существуют двоично-десятичные коды (BCD), которые также являются одношаговыми, то есть функциональными вариантами кода Грея.

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

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

Ниже приведена таблица вариантов одношаговых двоично-десятичных кодов.

Код Гликсона	Коды О’Брайена		Смещённый код Грея	Коды Томпкинса		Код Петерика
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», что предоставляет практические преимущества.

Литература

• А. Л. Пережогин, И. С. Быков. Обзор конструкций и свойств кодов Грея// Математические вопросы кибернетики. Вып. 20 (рус.). — М.: ФИЗМАТЛИТ, 2022. — 21 с.
• Баранкова И. И., Коновалов М. В. Теория информации. Кодирование. (Электронный ресурс) (рус.) / Швидченко Д. В. — Магнитогорск: Магнитогорский государственный технический университет, 2017. — 121 с. — ISBN 978-5-9967-1073-7.