3.2. Способы построения двоичных кодов 3.2.1. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды

Как следует из названия, в способах кодировании, относящихся к этой группе, знаки первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (т.е. О и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Длительности элементарных сигналов при этом одинаковы (τ₀=τ₁=τ). Очевидно, для передачи информации, в среднем приходящейся на знак первичного алфавита, необходимо время /С(Д2)-т. Таким образом, задачу оптимизации неравномерного кодирования можно сформулировать следующим образом:построить такую схему кодирования, в которой суммарная длительность кодов при передаче (или суммарное число кодов при хранении) данного сообщения была бы наименьшей. За счет чего возможна такая оптимизация? Очевидно, суммарная длительность сообщения будет меньше, если применить следующий подход: тем знакам первичного алфавита, которые встречаются в сообщении чаще, присвоить меньшие по длинекоды, а тем, относительная частота которых меньше -кодыболее длинные. Другими словами,кодызнаков первичного алфавита, вероятность появления которых в сообщении выше, следует строить из возможно меньшего числа элементарных сигналов, а длинныекодыиспользовать для знаков с малыми вероятностями.

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

00100010000111010101110000110

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

Первый состоит в использовании специальной комбинации элементарных сигналов, которая интерпретируется декодером какразделитель знаков. Второй - в применениипрефиксных кодов. Рассмотрим подробнее каждый из подходов.

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

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

• кодпризнака конца знака может быть включен вкодбуквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться00);

• кодыбукв не должны содержать двух и более нулей подряд в середине (иначе они будут восприниматься как конец знака);

• кодбуквы (кроме пробела) всегда должен начинаться с1;

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

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

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

Поскольку для русского языка, как указывалось в п.2.3., I^(r)₁=4,356 бит, избыточность данного кода, согласно (3.5), составляет:

Q(r,2)=4,964/4,356-1≈0,14,

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

Таблица3.1

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

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

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

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

Пример 3.1.

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

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

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

00100010000111010101110000110

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

• (a) отрезать от текущего сообщения крайний левый символ, присоединить справа к рабочему кодовому слову;

• (b) сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);

• (c) декодировать рабочее кодовое слово, очистить его;

• (d) проверить, имеются ли еще знаки в сообщении; если "да", перейти к (а).

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

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

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

Префиксный кодШеннона-Фано

Данный вариант кодирования был предложен в 1948-1949 гг. независимо Р. Фано и К. Шенноном и по этой причине назван по их именам. Рассмотрим схему на следующем примере: пусть имеется первичный алфавитА, состоящий из шести знаков a₁…a₆, с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Расположим эти знаки в таблице в порядке убывания вероятностей (см. табл. 3.2). Разделим знаки на две группы таким образом, чтобы суммы вероятностей в каждой из них были бы приблизительно равными. В нашем примере в первую группу попадута1 и а2 с суммой вероятностей 0,5 - им присвоим первый знак кода "О". Сумма вероятностей для остальных четырех знаков также 0,5; у них первый знак кода будет "1". Продолжим деление каждой из групп на подгруппы по этой же схеме, т.е. так, чтобы суммы вероятностей на каждом шаге в соседних подгруппах были бы возможно более близкими. В результате получаем:

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

К(А,2) =0,3∙2 + 0,2∙2 + 0,2∙2 + 0,15∙3 + 0,1 ∙4 + 0,05∙4 = 2,45

I^(A)₁= 2,390 бит. Подставляя указанные значения в (3.5), получаем избыточность кода Q(A,2) = 0,0249, т.е. около 2,5%. Однако, данныйкоднельзя считать оптимальным, поскольку вероятности появления 0 и 1 неодинаковы (0,35 и 0,65, соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода 0,0147.

Префиксный ход Хаффмана

Способоптимального префиксного двоичного кодирования был предложен Д. Хаффманом. Построение кодов Хаффмана мы рассмотрим на том же примере. Создадим новый вспомогательный алфавит А,, объединив два знака с наименьшими вероятностями (а₅и а₆) и заменив их одним знаком (например, а⁽¹⁾; вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е.-0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что количество таких шагов будет равно N - 2, где N - число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей. Всю процедуру построения представим в виде таблицы:

Теперь в обратном направлении проведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды0 и 1 (которому какой - роли не играет; условимся, что верхний знак будет иметькод0, а нижний - 1). В нашем примере знакаалфавита A(4), имеющий вероятность 0,6 , получиткод0, а вероятностью 0,4 -код1. В алфавитеA знакас -получает ота его вероятность 0,4 икод(1);кодызнаков а и а, происходящие от знакаа с вероятностью 0,6, будут уже двузначным: их первой цифрой станеткодих "родителя" (т.е. 0), а вторая цифра - как условились - у верхнего 0, у нижнего - 1; таким образом, а будет иметькод00, а а -код01. Полностью процедура кодирования представлена в таблице, приведенной на с.70.

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

Избыточность снова оказывается равной Q(A2) = 0,0249, однако, вероятности 0 и 1 сблизились (0,47 и 0,53, соответственно). Более высокая эффективность кодов Хаффмана по сравнению с кодамиШеннона-Фано становится очевидной, если сравнить избыточности кодов для какого-либо естественного языка. Применение описанного метода для букв русского алфавита порождаеткоды, представленные в табл. 3.2. (для удобства сопоставления они приведены в формате табл. 3.1).

Таблица 3.2

Средняя длина кода оказывается равной K(r, 2)= 4,395; избыточность кода Q(r,2) = 0,0090, т.е. не превышает 1 %, что заметно меньше избыточности кодаШеннона-Фано (см. выше).

КодХаффмана важен в теоретическом отношении, поскольку можно доказать, что он являетсясамым экономичным из всех возможных, т.е.ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана (см. [49, с.209-211]).

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