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

Как видно, коды лексикографически (в данном случае, по значению) упорядоченных цифр 1 и 2 в случае кода Грея различаются одним двоичным разрядом, а прямые коды этих же цифр – двумя разрядами. Аналогичную картину можно наблюдать в случае пар цифр 3 и 4; 5 и 6; 7 и 8.

Для формирования кода Грея можно использовать следующую последовательность действий:

Шаг 1) код Грея для 0 и 1 равен 02 и 12, соответственно;

Шаг 2) для построения кодов Грея для десятичных чисел 2 и 3 построим таблицу, в которой для нумерации строк и столбцов использованы коды Грея для чисел 0 и 1 (обозначение строк и столбцов выделены серым фоном):

В ячейках таблицы размещены кодируемые десятичные числа, включая и уже закодированные 0 и 1. Стрелки показывают направление перемещения по ячейкам для формирования кода одного из чисел (само число указано в ячейке). Тогда код Грея для произвольного числа, размещенного в некоторой ячейке, формируется как номер строки и номер столбца для этой ячейки. Так, код Грея для числа 3 – это 102, а для числа 2 – 112. Поскольку код Грея имеет постоянную длину, сформированные ранее коды для чисел 0 и 1 пополняются незначащими нулями, т.е. код Грея для 0 – это 002, а для 1 – это 012;

Шаг 3) получив коды Грея для четырех десятичных чисел, используем их в качестве номеров строк и столбцов, чтобы сформировать кодовые комбинации для первых шестнадцати десятичных цифр:

Так, например, для получения кода числа 9 выписывают обозначения строки и столбца: соответственно, 11 и 01. Тогда получаем код: для числа 15 кодом будет комбинация 1000, для числа 11 – 1110 и т.д.

Поскольку переход от числа 15 к 0 также является одношаговым (эти числа имеют коды, соответственно, 1000 и 0000), построенный код называют также циклически одношаговым;

Шаг 4) для формирования кода Грея для множества последовательных натуральных чисел, начинающихся с нуля, в количестве 2m строят таблицу размером mxm и нумеруют строки и столбцы в соответствии с кодами Грея, построенными на предыдущих этапах для m чисел. Получают коды Грея в соответствии с рассмотренными схемами.

Следует отметить, что таблицы для кода Грея не обязательно квадратные: число строк и столбцов могут не совпадать.

Пример 1. Построить код Грея для алфавита, который используется при записи фамилии "Шеннон". При этом не различать строчные и прописные буквы.

Сформирует исходный алфавит, для которого будем строить код. Это множество символов {е, н, о, ш}. Отметим, что символы в множестве упорядочены по алфавиту. Тогда построим таблицу размером 2х2, введем обозначения строк и столбцов и разместим в ячейках символы алфавита. Получим:

Тогда коды Грея: е - 00, н - 01, о - 11, ш - 10.

Пример 2. Закодировать фамилию "Шеннон" построенным в примере 1 кодом Грея (строчные и прописные буквы не различаются).