Лекции по теории информации. Фурсов В.А. - 82 стр.

UptoLike

Составители:

Рубрика:

ности обрабатываемого узла. Так продолжают до достижения узлов, соответст-

вующих вероятностям исходных знаков.

Процесс кодирования по кодовому дереву осуществляется следующим об-

разом. Одной из ветвей, выходящей из каждого узла, например, с более высо-

кой вероятностью, ставится в соответствие символ 1, а с меньшей – 0. Спуск от

корня к нужному знаку дает код этого знака. Правило кодирования в случае

равных вероятностей оговаривается особо. Таблицы 9.3, 9.4 и рисунок 9.1 ил-

люстрируют применение методики Хаффмана. Жирным шрифтом в таблице 9.3

выделены объединяемые позиции, подчеркиванием – получаемые при объеди-

нении позиции.

Таблица 9.4

Знаки Коды

111

110

100

1011

10101

10100

Рис. 9.1. Кодовое дерево

Замечательным свойством кодов, построенных с применением методик

Шеннона-Фано или Хаффмана, является их префиксность. Оно заключается в

том, что ни одна комбинация кода не является началом другой, более длинной

комбинации. Это позволяет при отсутствии ошибок осуществлять однозначное

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

которыми отсутствуют разделительные символы.