Рівномірне алфавітне двійкове кодування

Пример 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Данный вариант кодирования был предложен в 1948-1949 гг. независимо Р. Фано и К. Шенноном и по этой причине назван по их именам. Рассмотрим схему на следующем примере: пусть имеется первичный алфавит, состоящий из шести знаков с вероятностями появления в сообщении, соответственно,.

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

В нашем примере в первую группу попадут и с суммой вероятностей - им присвоим первый знак кода. Сумма вероятностей для остальных четырех знаков также 0,5; у них первый знак кода будет "1".

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

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

. Подставляя указанные значения в (5), получаем избыточность кода, т.е. около 2,5%. Однако, данный код нельзя считать оптимальным, поскольку вероятности появления неодинаковы (0,35 и 0,65, соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода.

Префиксный код Хаффмана [1] (David Albert Huffman)

Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом. Построение кодов Хаффмана мы рассмотрим на том же примере.

1. создадим новый вспомогательный алфавит, объединив два знака с наименьшими вероятностями () и заменив их одним знаком (например,);

2. вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е.;

3. остальные знаки исходного алфавита включим в новый без изменений;

4. общее число знаков в новом алфавите, очевидно, будет на меньше, чем в исходном;

5. аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака.

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

Теперь в обратном направлении проведем процедуру кодирования.

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

В нашем примере знак а ₁⁽⁴⁾алфавита A ⁽⁴⁾, имеющий вероятность 0,6, получит код 0, а a ₂⁽⁴⁾с вероятностью 0,4 - код 1.

В алфавите А ⁽³⁾знак a ₁⁽³⁾ получает от a ₂⁽⁴⁾ его вероятность 0,4 и код (1);

коды знаков a ₂⁽³⁾ и a ₃⁽³⁾, происходящие от знака a ₁⁽⁴⁾ с вероятностью 0,6, будут уже двузначным: их первой цифрой станет код их «родителя» (т.е. 0), а вторая цифра - как условились - у верхнего 0, у нижнего - 1; таким образом, a ₂⁽³⁾будет иметь код 00, а a ₃⁽³⁾ - код 01. Полностью процедура кодирования представлена в таблице:

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

Избыточность снова оказывается равной, однако, вероятности сблизились (, соответственно). Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточности кодов для какого-либо естественного языка. Применение описанного метода для букв русского алфавита порождает коды, представленные в табл. 2. (для удобства сопоставления они приведены в формате табл. 1).

Таблица 2

Средняя длина кода оказывается равной; избыточность кода, т.е. не превышает 1 %, что заметно меньше избыточности кода Шеннона-Фано (см. выше).

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

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

В этом случае двоичный код первичного алфавита строится цепочками равной длины, т.е. со всеми знаками связано одинаковое количество информации равное. Формировать признак конца знака не требуется, поэтому для определения длины кода можно воспользоваться формулой. Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует), соотнося ее с таблицей кодов. Правда, при этом недопустимы сбои, например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи или иными способами. С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи, поскольку факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.

Дата добавления: 2013-12-12