5.3. Код Хаффмена

Кодирование по методу Хаффмена осуществляется следующим образом:

1. Все подлежащие кодированию символы записываются в порядке убывания их априорных вероятностей. Если некоторые символы имеют одинаковые вероятности, то их располагают рядом в произвольном порядке.

2. Выбирают символы с минимальными вероятностями по 2 и одному приписывают 0, а другому 1.

3. Выбранные символы объединяют в промежуточные символы с суммарной вероятностью.

4. Снова находят пару символов с наименьшими вероятностями и поступают аналогично.

В таблице 2 приведен пример кодирования по методу Хаффмена для источника сообщений с заданными вероятностями символов алфавита:

x₁ = 0,4; x₂ = x₅ = 0,2; x₃ = 0,1; x₄ = x₆ = 0,05.

Таблица 2

Энтропия источника равна

Средняя длина кодовой комбинации данного кода

Длина кодовой комбинации примитивного кода определяется соотношением

(11.7)

Округляя до ближайшего целого в большую сторону, получим l = 3.

Эффективность ОНК максимальна, если .

Коэффициент относительной эффективности равен

.

Коэффициент статистического сжатия равен

.

Неравномерный код можно передавать блоками заданной длины, а на приемной стороне декодировать всю последовательность.

Пример 1. Построить оптимальные неравномерные коды (ОНК) по методу Шеннона-Фано и по методу Хаффмена для передачи сообщений, в которых вероятности символов первичного алфавита равны:

p(a₁) =0,1; p(a₂) =0,07; p(a₃) =0,02; p(a₄) =0,17;

p(a₅) =0,42; p(a₆) =0,09; p(a₇) =0,08; p(a₈) =0,05.

Оценить эффективность каждого кода, т. е. насколько они близки к оптимальным. Определить емкость (пропускную способность) канала связи для каждого кода, если скорость передачи двоичных символов (V = 1/) равна 1000 симв/с, т.е. время передачи одного символа вторичного алфавита (двоичного символа) равна  = 0,001с = 1мкс.

Решение: Построим код по методу Шеннона-Фано, используя следующий алгоритм:

1. Символы сообщения располагаем в порядке убывания их априорных вероятностей.

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

3. Верхней группе присваиваем символ 1, а нижней 0.

4. Процесс деления повторяем до тех пор, пока в каждой подгруппе останется по одному символу.

Процесс построения кода приведем в таблице 3.

Таблица 3

. .

Могут быть и другие варианты построения кода, но l_ср при этом не меняется.

Определим энтропию источника сообщений:

= -(0,42 log₂0,42+0,17 log₂0,17+0,1log₂0,1+0,09log₂0,09+0,08log₂0,08+

+0,07log₂0,07+0,05log₂0,05+0,02log₂0,02) = 0,5256+0,4346+0,3322+

+0,3126+0,2915+0,2686+0,2161+0,1129 = 2,49 бит/симв.

Оценим эффективность построенного кода, которая определяется коэффициентами относительной эффективности и статистического сжатия.

Коэффициент относительной эффективности равен

Коэффициент статистического сжатия равен

.

Необходимая пропускная способность канала связи для передачи сообщений оптимальными кодами вычисляется по формуле

.

Для полученного кода она равна С = 10³ 2,54 = 2,54 Кбит/с.

Построим код по методу Хаффмена, используя следующий алгоритм:

1. Символы первичного алфавита располагаем в порядке убывания их вероятностей.

2. Последние два символа объединяем в один, с суммарной вероятностью.

3. Упорядочиваем символы с учетом вновь образованных и последние два символа объединяем в один с суммарной вероятностью. Эту процедуру повторяем до тех пор, пока не останется два символа.

4. Строим кодовое дерево, вершиной которого является 1 (суммарная вероятность всех символов сообщения).

При построении дерева символы, в принципе, можно не упорядочивать.

Процесс построения кода приведен в таблице 4.

Коэффициент статистического сжатия равен

.

Коэффициент относительной эффективности

.

Необходимая пропускная способность канала связи

Кбит/c.

Tаблица 4

. .

Построенные коды Шеннона – Фано и Хаффмена равноценны, т. к. они имеют одинаковые показатели эффективности. Оба кода отличаются от оптимального на 2%.