Кодирование дискретных источников информации по методики Д.Хаффмана
Методика Д. Хаффмана свободна от недостатка неоднозначного кодирования, рассмотренного в предыдущей лабораторной работе. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом двоичных разрядов на символ.
Алгоритм Хаффмана для двоичного кода:
Шаг 1. Символы алфавита, составляющего сообщение, выписываются в основной столбец в порядке убывания вероятностей. Два последних символа объединяются в один вспомогательный, которому приписывается суммарная вероятность.
Таблица 4
Шаг 2. Вероятности символов, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последних объединяются. Процесс продолжается до тех пор, пока не получим единственный вспомогательный символ с вероятностью, равной единице. Эти два шага алгоритма иллюстрирует таблица 4 для уже рассмотренного случая кодирования восьми символов.
Шаг 3. Строится кодовое дерево, и формируются кодовые слова, соответствующие кодируемым символам. Для составления кодовой комбинации, соответствующей данному сообщению, необходимо проследить путь перехода сообщений по строкам и столбцам таблицы. Для наглядности строится кодовое дерево (рис.1). Из точки, соответствующей вероятности 1, направляются две ветви. Ветви с большей вероятностью присваивается символ 1, а с меньшей — символ 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до каждого символа.
Рис.1 Кодовое дерево
Символам источника сопоставляются концевые вершины дерева. Кодовые слова, соответствующие символам, определяются путями из начального узла дерева к финальным. Каждому ответвлению влево соответствует символ 1 в результирующем коде, а вправо — символ 0. Ни одно кодовое слово не будет началом другого, т.к. только концевым вершинам кодового дерева сопоставляются кодовые слова. Таким образом гарантируется возможность разбиения последовательности кодовых слов на отдельные кодовые слова.
Двигаясь по кодовому дереву сверху вниз можно записать для каждой буквы соответствующую ей кодовую комбинацию
Таблица 5
Рассмотрим пример. Возьмем сообщение, состоящее из 6 символов.
Например, а2 а3 а1 а1 а4 а2 .Тогда код сообщения приобретает следующий вид:
Возможный способ декодирования представлен на таблице 6:
Таблица 6
Вывод: мною были освоены методы построения кодов дискретного источника информации по примеру Шеннона-Фано и Д.Хаффмана. К обоим примерам построены таблицы декодирования сообщений, которые показывают однозначность раскодирования приведенных сообщений.