2015-01-21
600
Построить по методике Шеннона-Фано эффективный код для букв первичного алфавита, 
. Вероятности появления букв в сообщениях:
; 
;
.
Процедура построения кода и результат приведены в таблице 2.1.
Из таблицы видно, что ни одна более длинная кодовая комбинация не является продолжением более короткой, следовательно, полученный код является разделимым.
Таблица 2.2
Процедура построения кода
Для определения того, является ли полученный код оптимальным или нет, необходимо сравнить значения реально полученной средней длины кодовой комбинации, вычисляемой в соответствии с (2.4), с минимально достижимой по теореме Шеннона. Имеем:
Так как вторичный код является двоичным 
, то минимальная средняя длина кодовой комбинации, определяемая по (2.5) и выраженная в символах, численно будет совпадать с энтропией первичного алфавита, выраженной в битах:
Таким образом, реально полученная средняя длина кодовой комбинации в точности равна энтропии первичного алфавита, выраженной в битах, следовательно, построенный код является оптимальным.
|
|
|
Для построения эффективного кода по методике Хаффмена буквы первичного алфавита вписываются в столбец в порядке убывания вероятностей (последнее не является обязательным, но желательно) и строится кодовое дерево в следующей последовательности. Сначала две буквы с наименьшими вероятностями объединяются в новую букву с вероятностью, равной сумме вероятностей объединенных букв. В дальнейшем новая буква и оставшиеся исходные буквы рассматриваются как равноценные и выполняется такая же процедура объединения. Этот процесс продолжается до тех пор, пока не получается единственная вспомогательная буква с вероятностью, равной 1.
При каждом парном объединении одна из ветвей кодового дерева обозначается символом 1, а другая 0. Код для каждой буквы представляет собой последовательности нулей и единиц, обозначающих ветви кодового дерева, по которым нужно пройти от вершины кодового дерева до данной буквы.
