Коды, учитывающие частоту информационных элементов

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

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

Таблица 4.3

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

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

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

Коды Грея

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

Таблица 4.4

Исходная цифра	Прямой код	Код Грея

Как видно, коды лексикографически (в данном случае, по значению) упорядоченных цифр 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₂.

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

00
11

Рис. 4.2. Схема формирования кода Грея для шестнадцати десятичных чисел

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

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

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

(4.1)

Для расчета полного значения двоичного числа a₁a₂…a_n, представленного кодом Грея, служит формула (4.1):

где i – порядковый номер двоичного разряда (слева направо);

k – порядковый номер двоичного разряда, отличного от нуля: k = 1 ¸ n в общем случае (нумерация слева направо);

множитель (2^n-(i-1) – 1) называется весовым коэффициентом или просто весом разряда (или позиции).

Пример 4.2. Рассчитать полное значение числа с кодом Грея 1101.

Имеем (слагаемое с нулевым коэффициентом a_i опущено):

1*(-1)¹⁺¹*(2^4-(1-1) – 1) + 1*(-1)²⁺¹*(2^4-(2-1) – 1) + 1*(-1)³⁺¹*(2^4-(4-1) – 1) =

1*1*(2⁴-1)+1*(-1)*(2³-1)+1*1*(2¹-1) = 15-7+1 = 9.

Коды с весовыми коэффициентами (к ним относится и прямой код) используются при сложении чисел (см. выше).

Код Штибица

Для внутреннего представления отрицательного числа -х в информатике традиционно используется дополнительный код, который облегчает выполнение арифметических операций над отрицательными числами (это будет рассмотрено далее).

Код Штибица (или код плюс-3) используется для кодирования десятичных чисел для простого перехода от двоичного значения числа к его дополнению.

Для построения кода Штибица используется понятие прямого целочисленного эквивалентадвоичного кода – это десятичное число, соответствующее двоичному коду. Тогда код Штибица – это сдвинутый на 3 прямой код: чтобы получить представляемое данным двоичным кодом число, надо из прямого целочисленного эквивалента вычесть 3.

В табл. 4.5 приведены значения кода Штибица для десятичных цифр (для сравнения также указан их прямой код).

Таблица 4.5

Исходная цифра	Прямой код	Код Штибица
Продолжение табл. 4.5

В этом коде используется понятие взаимно дополнительных пар чисел: это такие числа, при сложении двоичных значений которых получается двоичное число, состоящее только из единиц. Примером таких пар чисел могут служить 0 и 9, 1 и 8 и т.д.