Способы построения двоичных кодов

Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды

Как следует из названия, в способах кодировании, относящихся к этой группе, знаки первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (т.е. 0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Длительности элементарных сигналов при этом одинаковы %%(τ_0 = τ_1 = τ)%%. Очевидно, для передачи информации, в среднем приходящейся на знак первичного алфавита, необходимо время %%K(A,2) \cdot τ%%.

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

За счет чего возможна такая оптимизация? Очевидно, суммарная длительность сообщения будет меньше, если применить следующий подход: тем знакам первичного алфавита, которые встречаются в сообщении чаще, присвоить меньшие по длине коды, а тем, относительная частота которых меньше - коды более длинные. Другими словами, коды знаков первичного алфавита, вероятность появления которых в сообщении выше, следует строить из возможно меньшего числа элементарных сигналов, а длинные коды использовать для знаков с малыми вероятностями.

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

00100010000111010101110000110

Каким образом она может быть декодирована? Если бы код был равномерным, приемное устройство просто отсчитывало бы заданное (фиксированное) число элементарных сигналов (например, 5, как в коде Бодо) и интерпретировало их в соответствии с кодовой таблицей. При использовании неравномерного кодирования возможны два подхода к обеспечению различимости кодов. Первый состоит в использовании специальной комбинации элементарных сигналов, которая интерпретируется декодером как разделитель знаков. Второй - в применении префиксных кодов. Рассмотрим подробнее каждый из подходов.

Неравномерный код с разделителем

Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов-слов - 000 (признак конца слова - пробел). Довольно очевидными оказываются следующие правила построения кодов:

• код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться 00);
• коды букв не должны содержать двух и более нулей подряд в середине (иначе они будут восприниматься как конец знака);
• код буквы (кроме пробела) всегда должен начинаться с 1;
• разделителю слов (000) всегда предшествует признак конца знака; при этом реализуется последовательность 00000 (т.е., если в конце кода встречается комбинация ...000 или ...0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).

В соответствии с перечисленными правилами построим кодовую табл. 3.1 для букв русского алфавита, основываясь на приведенных ранее (табл. 2.1.) вероятностях появления отдельных букв.

Теперь можно найти среднюю длину кода К(r,2) для данного способа кодирования:

$$К(r,2)=\sum^{32}_{j=1} {p_jk_j}=4.964$$

Поскольку для русского языка, %%I_1(r) = 4,356 бит%%, избыточность данного кода, согласно (3.5), составляет:

$$Q(r,2)=\frac{4.964}{4.356}-1 \approx 0.14$$

это означает, что при данном способе кодирования будет передаваться приблизительно на 14% больше информации, чем содержит исходное сообщение. Аналогичные вычисления для английского языка дают значение %%К(e,2) = 4,716%%, что при %%I_1(e) = 4,036%% бит приводят к избыточности кода %%Q(e,2) = 0,168%%.

Таблица 3.1.

Буква	Код	%%p_j\cdot 10^3%%	%%k_j%%	Буква	Код	%%p_j\cdot 10^3%%	%%k_j%%
пробел	000	174	3	я	1011000	18	7
о	100	90	3	ы	1011100	16	7
е	1000	72	4	з	1101000	16	7
а	1100	62	4	ь,ъ	1101100	14	7
и	10000	62	5	б	1110000	14	7
т	10100	53	5	г	1110100	13	7
н	11000	53	5	ч	1111000	12	7
с	11100	45	5	й	1111100	10	7
р	101000	40	6	х	10101000	9	8
в	101100	38	6	ж	10101100	7	8
л	110000	35	6	ю	10110000	6	8
к	110100	28	6	ш	10110100	6	8
м	111000	26	6	ц	10111000	4	8
д	111100	25	6	щ	10111100	3	8
п	1010000	23	7	э	11010000	3	8
у	1010100	21	7	ф	11010100	2	8

Рассмотрев один из вариантов двоичного неравномерного кодирования, попробуем найти ответы на следующие вопросы: возможно ли такое кодирование без использования разделителя знаков? Существует ли наиболее эффективный (оптимальный) способ неравномерного двоичного кодирования?

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

• В языковедении термин «префикс» означает «приставка».

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом*) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления с таблицей кодов всегда можно точно указать, где заканчивается один код и начинается другой.

Пример.Пусть имеется следующая таблица префиксных кодов:

а	л	м	р	у	ы
10	010	00	11	0110	0111

Требуется декодировать сообщение:

00100010000111010101110000110

Декодирование производится циклическим повторением следующих действий:

• (a) отрезать от текущего сообщения крайний левый символ, присоединить справа к рабочему кодовому слову;
• (b) сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);
• (c) декодировать рабочее кодовое слово, очистить его;
• (d) проверить, имеются ли еще знаки в сообщении; если «да», перейти к (а).

Применение данного алгоритма дает:

шаг	рабочее слово	текущее сообщение	распознанный знак	декодированное сообщение
0	Пусто	0010001000011101010101110000110	-	-
1	0	0100010000111010101110000110	нет	-
2	00	1000100001110101011110000110	м	м
3	1	0001000011101010101110000110	нет	м
4	10	0010000111010101110000110	а	ма
5	0	010000111010101110000110	нет	ма
6	00	10000111010101110000110	м	мам
...

Доведя процедуру до конца, получим сообщение: «мама мыла раму».

Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков. Однако условие Фано не устанавливает способа формирования префиксного кода и, в частности, наилучшего из возможных. Мы рассмотрим две схемы построения префиксных кодов.