Краткие теоретические сведения. В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще

В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Построение кода Хаффмена для восьми сообщений, появляющихся с вероятностями 0,2; 0,2; 0,15; 0,13; 0,12; 0,1; 0,07; 0,03, иллюстрируется рисунками 1 и 2.

Рисунок 1.

Рисунок 2. Кодовое дерево

Из таблицы 1 видно, что полученный код является неравномерным, причем сообщению с максимальной вероятностью появления соответствует минимальная длительность кодовой комбинации - 2, а сообщению с минимальной вероятностью – максимальная - 4.

Таблица 1.

№	Вероятность появления сообщения	Структура кодовой комбинации	Длительность кодовой комбинации
	0,20
	0,20
	0,15
	0,13
	0,12
	0,10
	0,07
	0,03

Среднее число двоичных символов на одно сообщение алфавита объемом , для неравномерных двоичных кодов, определяется выражением

.

Среднее количество информации в сообщениях поступающих от источника, называется энтропией Н(А). Она определяется путем усреднения значений по всему объему алфавита и для источника без памяти равна

. , (1)

где - объем алфавита А передаваемых сообщений.

Э нтропия – это мера неопределенности в поведении источника сообщений (ИС). Она равна нулю, если с вероятностью равной единице источником выдается всегда одно и то же сообщение (в этом случае неопределенность в поведении ИС отсутствует). Энтропия максимальна, если сообщения, выдаваемые источником появляются независимо и с одинаковой вероятностью. В этом случае она равна .

Эффективность неравномерных кодов оценивается следующими параметрами:

§ коэффициентом статистического сжатия, который характеризует уменьшение числа двоичных символов на знак при применении методов эффективного кодирования по сравнению с применением равномерного кода;

,

где - средняя длина кодовой комбинации при равномерном кодировании,

§ коэффициентом относительной эффективности, который показывает степень близости средней длины кодовой комбинации к теоретически возможному пределу .

.

Date: 2015-06-11; view: 549; Нарушение авторских прав