Код Шеннона-Фано

ЛАБОРАТОРНАЯ РАБОТА 9

Эффективное кодирование

Цель: Изучение методик эффективного кодирования.

Задание.

1. Построить код Шеннона-Фано по выбранным вариантам и результаты свести в таблицы.

2. Построить код Хаффмана по выбранным вариантам и результаты свести в таблицы. Для каждого построенного кода построить кодовое дерево.

 

Отчет по лабораторной работе должен содержать:

– краткие теоретические сведения о коде Шеннона-Фано и коде Хаффмана;

– построить коды Шеннона-Фано и Хаффмана при различных вариантах входных данных (для каждого кода выбрать произвольно три группы по 12 символов в каждой, присвоить каждому символу вероятность (сумма равна единице) и построить указанные коды).

– выводы.

Основные понятия и определения

 

Код Шеннона-Фано

 

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

Пример 1. Проведем эффективное кодирование ансамбля из восьми знаков, характеристики которого представлены в табл. 3.1.

 

Таблица 3.1

 

Характеристики ансамбля из восьми знаков

 

Знаки	Вероятность	Кодовые комбинации	Ступень разбиения
Z1	0.22
Z2	0.2
Z3	0.16
Z4	0.16
Z5	0.1
Z6	0.1
Z7	0.04
Z8	0.02

 

 

-2-

 

Рис. 3.1. Дерево группового разделения вероятностей Шеннона-Фано

Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждого знака требуется три двоичных символа. Используя методику Шеннона-Фано, получаем совокупность кодовых комбинаций, приведенных в табл. 3.1.

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

,

и среднее число символов на знак

,

где – число символов в кодовой комбинации, соответствующей знаку .

В общем случае для алфавита из восьми знаков среднее число символов на знак будет меньше трех, но больше энтропии алфавита .

 

Пример 2. Определим среднюю длину кодовой комбинации при эффективном кодировании знаков ансамбля. Приведенного в табл. 3.2.

Энтропия ансамбля равна 2,76. В результате сопоставления отдельным знакам ансамбля кодовых комбинаций по методике Шеннона-Фано (табл. 3.2) получаем среднее число символов на знак, равное 2,84.

Таблица 3.2

 

Характеристики ансамбля из восьми знаков

 

Знаки	Вероятность	Кодовые комбинации	Ступень разбиения
Z1	0,22
Z2	0,20
Z3	0,16
Z4	0,16
Z5	0,10
Z6	0,10
Z7	0,04
Z8	0,02

 

Следовательно, некоторая избыточность в последовательностях символов осталась. Из теоремы Шеннона следует, что эту избыточность также можно устранить, если перейти к кодированию достаточно большими блоками.

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

От указанного недостатка свободна методика Хаффмана. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.