Кодирование по методике Хаффмена

Дата добавления: 2015-08-14; просмотров: 729; Нарушение авторских прав

Методика гарантирует построение кода с наименьшим для данного распределения вероятностей средним числом разрядов на букву. Для двоичного кода методика сводится к следующему. Буквы алфавита сообщений выписываются в основной столбец в порядке убывания вероятностей. Две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность. Вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние объединяются. Процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной 1(таблица2.3)

Таблица 2.3

Буквы	Вероятности	Вспомогательные столбцы

z₁	0,22	0,22	0,22	0,26	0,32	0,42	0,58
z₂	0,20	0,20	0,20	0,22	0,26	0,32	0,42
z₃	0,16	0,16	0,16	0,20	0,22	0,26
z₄	0,16	0,16	0,16	0,16	0,20
z₅	0,1	0,1	0,16	0,16
z₆	0,1	0,1	0,1
z₇	0,04	0,06
z₈	0,02

Для составления кодовой комбинации, соответствующей данному сообщению, необходимо проследить путь перехода сообщений по строкам и столбцам таблицы. Для наглядности строится кодовое дерево. Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваивается символ 1, а с меньшей – 0. Такое последовательное ветвление продолжается до тех пор, пока не дойдет очередь до каждой буквы (рисунок 2.3 ).

Рисунок 2.3 – Кодовое дерево

Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию:

z₁	z₂	z₃	z₄	z₅	z₆	z₇	z₈

<== предыдущая лекция	\|	следующая лекция ==>
Код Шеннона-Фано	\|	Кодирование с проверкой на четность