Процедура Шеннона-Фано

В этом алгоритме предварительно производится упорядочивание сообщений по возрастанию или убыванию вероятностей pj. Разбиение на подмножества производится путем выбора разделяющей границы в упорядоченной последовательности так, чтобы суммарные вероятности подмножеств были по возможности одинаковыми. Кодовое дерево, построенное этим методом для примера в таблице 1.1, приведено на рис.1.5. Возле каждой вершины дерева указывается суммарная вероятность соответствующего подмножества.

Рис.1.5

Кодовое дерево в процедуре Шеннона-Фано

 

Выполнив расчеты по формуле 1.3, получим: λkS=3,145(бит/сообщение).Таким образом, код, полученный при помощи процедуры Шеннона-Фано, оказывается более экономным, чем код из таблицы 1.1.

 

Процедура Хафмана

 

Рассмотренная в §13процедура Шеннона-Фано является простым, но не всегда оптимальным алгоритмом построения экономного кода. Причина состоит в том, что способ разбиения на подмножества ограничен: вероятности сообщений, отнесенных к первому подмножеству, всегда больше или всегда меньше вероятностей сообщений, отнесенных ко второму подмножеству. Оптимальный алгоритм, очевидно, должен учитывать все возможные комбинации при разбиении на равновероятные подмножества. Это обеспечивается в процедуре Хафмана.

Процедура Хафмана представляет собой рекурсивный алгоритм, который строит бинарное дерево «в обратную сторону», т.е. от конечных вершин к корню. Основная идея алгоритма состоит в том, чтобы объединить два сообщения с наименьшими вероятностями – например, p1 и p2 – в одно множество и далее решать задачу с m-1 сообщениями и вероятностями p1’ = p1 + p2; p2’ = p3; … ; pm-1’ = pm. Кодовое дерево, построенное процедурой Хафмана для рассматриваемого примера, приведено на рис.1.6.

 

Рис.1.6

Кодовое дерево в процедуре Хафмана

 

Расчеты по формуле 1.3 дают среднее значение длины кодового слова λkS=3,145(бит/сообщение), что совпадает с результатом применения процедуры Шеннона-Фано. Это означает, что для данного примера процедура Шеннона-Фано также оказалась оптимальной.

 

<== предыдущая лекция | следующая лекция ==>
Кодирование сообщений словами переменной длины | Помехоустойчивость данных


Дата добавления: 2017-11-04; просмотров: 13; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2017 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.