Коды Грея

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

Цифра	Прямой код	Код Грея

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

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

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

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

	номера столбцов
номера строк

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

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

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

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

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

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

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

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

	е	н
	ш	о

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

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

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

1.4 Коды, учитывающие частоту символов

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

Учет частоты символов позволяет строить “экономные” для техники коды постоянной длины. Например, условимся, что двоичная единица технически реализуется включенной лампочкой накаливания (как это и было в первых ламповых компьютерах), а двоичный ноль – выключенной лампочкой. Пусть также известны частоты букв русского алфавита, и в соответствии с этой частотой буквам назначены коды (мы умышленно задались неполным алфавитом русского языка), показанные в таблице.

Буква	Частота	Коды
о	0,090
е	0,072
а	0,062
и	0,062
я	0,018
ы	0,016

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

Очевидно, чем больше частота исходного символа, тем меньше в соответствующем коде единиц, т.е. тем меньше включенных лампочек применяется для представления символа в компьютере, а значит меньше тратится электроэнергии.

Дата добавления: 2014-01-06