2. Кодирование по методу Хаффмена

Как и в предыдущем пункте ЭВМ устанавливает значения вероятностей букв первичного алфавита. Рекомендуется предварительно заполнить предлагаемую таблицу вручную по методике, изложенной на с. 5-6 настоящей методической разработки (Табл. 2). Правильность заполнения таблицы проверяется на ЭВМ, при этом после ввода каждого численного значения следует нажимать клавишу «Enter».

По заполненной таблице строится кодовое дерево (Табл. 3).

3. Расчет численных значений основных характеристик эффективных кодов

Требуется рассчитать на микрокалькуляторе численные значения следующих характеристик эффективного кода: средней длины кодовой комбинации – формула (1), энтропии источника дискретных сообщений – формула (3), коэффициента статистического сжатия – формула (7), коэффициента относительной эффективности – формула (8).

Рассчитанные значения введите в ЭМВ, после ввода числового значения нажимайте клавишу «Enter», и сравните свои значения с рассчитанными на ЭВМ. При большом расхождении сравниваемых значений выдается сообщение об ошибке.

4. Составьте отчет и сделайте соответствующие выводы Общие сведения

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

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

Пусть имеется сообщение, записанное с помощью букв некоторого первичного алфавита , содержащего букв. Требуется закодировать это сообщение, т.е. указать правило сопоставления каждой букве первичного алфавита последовательности из символов «0» и «1», образующих вторичный алфавит.

При передаче дискретных сообщений по каналам связи буквы алфавита обычно отображаются кодовыми комбинациями постоянной длины (равномерное кодирование). Длина кодовой комбинации выбирается из условия . Применение эффективного кодирования позволяет уменьшить среднее число двоичных символов на букву сообщения

(1)

где – длина кодовой комбинации, отображающей -ю букву,

– вероятность появления -й буквы.

Уменьшение средней длины кодовой комбинации, отображающей букву сообщения, позволяет увеличить скорость передачи.

Эффективное кодирование базируется на теореме Шеннона для каналов без шума. Согласно этой теореме (основной теореме кодирования), сообщения, составленные из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов, приходящихся на букву, будет сколь угодно близко к энтропии источников этих сообщений , но не менее этой величины, т.е.

(2)

Под энтропией дискретного источника понимается среднее количество информации, приходящееся на одну букву сообщения:

(3)

Для построения эффективных кодов наибольшее распространение нашли методики Шеннона-Фано и Хаффмена.

Метод Шеннона-Фано.

1. Все букв алфавита располагаются в один столбец в порядке убывания их вероятностей.

2. Эти буквы разбиваются на две группы: верхнюю и нижнюю так, чтобы суммы вероятностей в каждой из групп были по возможности ближе друг к другу.

3. Для букв верхней группы в качестве первого символа кодовой комбинации выбирается «1», а для нижней – «0».

4. Вновь каждую из полученных групп делят на две части с близкими, по возможности, суммарными вероятностями.

5. Верхним частям вновь образованных групп присваивается «1», а нижним – «0». Эти значения элементов считаются вторыми разрядами формируемых кодовых комбинаций.

Эти процедуры повторяются до тех пор, пока в каждой группе останется по одной букве.

Построение кода Шеннона-Фано для ансамбля из 8 букв приведено в Табл. 1 на с. 6.

При равномерном кодировании 8-ми букв кодовые комбинации содержат по три двоичных разряда. При использовании кода Шеннона-Фано средняя длина кодовой комбинации составляет:

Это меньше, чем при равномерном кодировании и не очень далеко от энтропии

Метод Хаффмена.

1. Буквы алфавита выписываются столбцом в порядке убывания вероятностей.

2. Находится сумма вероятностей последних двух букв.

3. Вероятности букв, не участвующих в объединении, и полученная суммарная вероятность снова располагаются столбцом в порядке убывания.

Второй и третий этапы повторяются до тех пор, пока суммарная вероятность не будет равна единице.

Построение кода Хаффмена для ансамбля из 8 букв приведено в Табл. 2.

Таблица 1

Буквы		Деление букв на группы	Код Шеннона-Фано
	0,20		11
	0,20		101
	0,15		100
	0,13		011
	0,12		010
	0,10		001
	0,07		0001
	0,03		0000

Кодовое дерево строится следующим образом (Табл. 3). Сначала находятся буквы с наименьшими вероятностями 0,07 ( ) и 0,03 ( ), а затем от них проводятся линии к точке, изображающей «укрупненный» символ с суммарной вероятностью 0,10. На рисунке эта процедура обозначена цифрой I. Затем берутся две наименьшие вероятности со значением 0,10 и получают новый «укрупненный» символ с вероятностью 0,20 (процедура II). Теперь наименьшие вероятности имеют символы (0,13) и (0,12). Соединяя их линиями формируют новый символ с суммарной вероятностью 0,25 (процедура III).

Эти процедуры повторяются до тех пор, пока линии от основных и «укрупненных» символов не соединятся в точке с суммарной вероятностью, равной 1. Верхнюю линию обозначают цифрой «1», а нижнюю «0». Любая кодова комбинация представляет собой последовательность «1» и «0», которые встречаются на пути от вершины дерева с вероятностью 1 к точке, изображающей нужную букву.

Сравнение рассмотренных методик построения эффективных кодов позволяет сделать вывод, что методика Хаффмена более удобна для практического использования. В общем случае код Хаффмена экономичнее кода Шеннона-Фано.

Нетрудно заметить, что сокращение средней длины кодовой комбинации эффективного кода по сравнению с равномерными кодами достигается благодаря присвоению более вероятным буквам коротких кодовых комбинаций, а менее вероятным буквам – более длинных кодовых комбинаций. Таким образом, эффективность рассматриваемых кодов связана с различием в числе символов кодовых комбинаций. Это приводит к определенным трудностям при декодировании. Конечно, для различия кодовых комбинаций можно ставить разделительный символ, но при этом существенно снижается эффект, который достигается использованием неравномерных кодов, так как средняя длина кодовой комбинации, по существу, увеличивается на одни символ. Более разумным является обеспечение однозначного декодирования без введения разделительных символов. Для этого эффективный код строят так, чтобы ни одна комбинация кода не совпадала с первыми символами более длинной кодовой комбинации. Коды, удовлетворяющие этому условию, называются префиксными.

Коды, представляющие первичные алфавиты с неравновероятными символами, имеющие минимальную среднюю длину кодового слова, называются оптимальными неравномерными кодами (ОНК).

Максимально эффективными будут те ОНК, у которых энтропия дискретного источника H(A) численно равна среднему числу двоичных символов на букву :

(4)

или с учетом (1) и (3)

(5)

Очевидно, что это равенство будет иметь место только тогда, когда

(6)

Величина точно равна H(A), если вероятности представляют собой целочисленные отрицательные степени двойки. Если это не выполняется, то и согласно основной теореме кодирования Шеннона для каналов без шумов средняя длина кодовой комбинации приближается к энтропии источника сообщений по мере укрупнения кодируемых блоков.

Для оценки эффективности ОНК предназначены следующие характеристики.

1. Коэффициент статического сжатия.

(7)

Он характеризует уменьшение количества двоичных символов на букву алфавита при применении ОНК по сравнению с применением методов нестатистического кодирования.

2. Коэффициент относительной эффективности.

(8)

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

Методы устранения избыточности позволяют эффективно использовать пропускную способность канала связи. Они полезны также в тех случаях, когда требуется хранить большой объем информации в различных запоминающих устройствах. Экономия в пропускной способности канала или в объеме запоминающего устройства приводит к снижению стоимости, сокращению размеров и веса аппаратуры. Рассмотренные методы кодирования получили применение при передаче факсимильных сообщений.