Эффективное кодирование Алгоритм Хаффмена

Алгоритм Хаффмена предполагает построение «кодового дерева».

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

2. Объединяем два наименее вероятных сообщения в одно с суммарной вероятностью появления (т.е. складываем вероятности объединяемых сообщений).

3. Вновь располагаем сообщения в порядке убывания вероятностей и т.д., пока не получим сумму вероятностей, равную единице. Очевидно, количество подобных итераций равна n - 1, где n - количество символов в алфавите источника.

«Кодовое дерево» для нашего примера представлено на рис. 2.

Алгоритм кодирования новым двоичным кодом следующий:

-идём от корней кодового дерева к вершине (справа – налево),

-если в узле мы идём вверх, то в кодовую комбинацию записывается единица, если вниз — ноль. В результате получим после первого от корня узла: дибит D₀ кодируется одной двоичной единицей 0, а объединение дибитов D₁, D₂ и D₃ кодируется 1. После второго разветвления дибит D₁ кодируется 10, а объединение дибитов D₂ и D₃ - 11. Окончательный результат дает третий узел. D₂ кодируется как 111, а D₃ - 110.

Таким образом имеем D₀ => "0"; D₁ => "10"; D₂ => "111"; D₃ => "110".

Рис. Кодовое дерево алгоритма Хаффмена

В результате кодирования получен неравномерный код. Наиболее вероятный дибит D₀ кодируется кодом минимальной длины, а наименее вероятные дибиты D₂ и D₃ - имеют коды максимальной длины. Поэтому средняя длина комбинации кода Хаффмена равна

0.46×1 + 0.22×2 + 0.20×3 + 0.12×3 = 1.86 бит

и приближается к энтропии исходного кода Н₂ = 1.827 дв. ед./дибит, что уменьшает длину и время передачи всего сообщения. Исходное сообщение содержало 100 дв. ед.

После кодирования передаваемое сообщение

10.0.0.0.111.0.0.0.110.10.10.110.0.0.111.10.111.0.111.0.111.

111.111.0.0.10.0.0.111.110.10.0.0.0.111.0.0.0.110.10.10.110.

0.0.111.10.0.10.10.110

содержит всего 23×1 + 11×2 + 10×3 + 6×3 = 93 дв. ед., на 7 дв. ед. меньше исходного.

Код Хаффмана обладает префиксными свойствами, т.е. никакая короткая кодовая комбинация не должна являться началом более длинной комбинации. При этом не нужно использовать дополнительные разделительные символы. Однако возникают и проблемы. Если произойдет ошибка при передаче информации, то нарушается разбиение кодовых комбинаций и возникает несколько ошибок при декодировании.

Так, например, пусть десятый и двадцатый символы передаваемой последовательности приняты неверно (эти символы подчеркнуты)

10.0.0.0.111.0. 1. 0.110.10.10.1 0 0.0.0.111.10.111.0.111.0.111.

111.111.0.0.10.0.0.111.110.10.0.0.0.111.0.0.0.110.10.10.110.

0.0.111.10.0.10.10.110.

После декодирования кода Хаффмена получим последовательность дибитов

01.00.00.00.10.00.0 1. 11. 0 1.01.01. 00. 00.00.10.01.10.00.10.00.10. 10.10.00.00.01.00.00.10.11.01.00.00.00.10.00.00.00.11.01.01.11.00.00.10.01.00.01.01.11.

Сравнение с переданной последовательностью

01.00.00.00.10.00.00.00.11.01.01.11.00.00.10.01.10.00.10.00.10.10.10.00.00.01.00.00.10.11.01.00.00.00.10.00.00.00.11.01.01.11.00.00.10.01.00.01.01.11.

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

И В Г Х И В М И Х А И Л И В А Н О В И Ч вместо переданной

И В А Н О В М И Х А И Л И В А Н О В И Ч,

т.е. три буквы приняты неверно.

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