Коды Грея

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

Цифра	Прямой код	Код Грея
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101

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

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

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

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

		номера столбцов
		0	1
номера строк	0	0	1
	1	3	2

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

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

	00	01	11	10
00	0	1	2	3
01	7	6	5	4
11	8	9	10	11
10	15	14	13	12

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

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

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

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

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

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

	0	1
0	е	н
1	ш	о

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

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

Получаем: 10 00 01 01 11 01 (коды символов для простоты разделены пробелами).