Теория информации

Код Хаффмана также учитывает статистические свойства сигналов, при которых вероятности появления букв p 1 , р 2 , …р к не равные между собой, поэтому: H < log n. Код Хаффмана строится следующим образом: 1) буквы располагают в порядке убывания их вероятностей. 2) Складывают вероятности двух последних букв, и ряд переписывают снова с учетом новой вероятности (суммы). 3) Далее повторяют шаги 1 и 2, пока не останется только один символ с вероятностью 1. 4) Нижнюю букву всегда кодируют нулем, а верхнюю – единицей, то есть приписывают компонентам составных символов: 0 и 1 – первой компоненте приписывают 0, а второй – 1. Для составления кодовых комбинаций строится кодовое дерево. Двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию. Код Хаффмана, также как и Шеннона-Фано является префиксным, то есть в таком коде ни одна комбинация не совпадает с началом более длинной комбинации, а это позволяет обеспечить однозначное декодирование без введения разделительных символов: