3.2 Метод кодирования Шеннона-Фано

При кодировании по методу Шеннона следует придерживаться следующих правил.

1. Все сообщения ансамбляранжируются в порядке убывания вероятности реализаций сообщений.

2. Сообщения делятся на две группы сообщений, приблизительно одинаковые по вероятности.

3. Всем сообщениям одной из подгрупп приписывается символ 1, другой – символ 0.

4. Сообщения каждой подгруппы опять делятся на две подгруппы, приблизительно одинаковые по вероятности, и приписываются символы 1и 0.

5. Процедура деления и приписывания символов 1 и 0 продолжается до тех пор пока не останется в каждой подгруппе по одному сообщению.

6. Полученная последовательность символов, соответствующая определённому сообщению, является отображением сообщения в двоичной системе счисления в сжатой форме.

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

,

где - количество символов, употребляемых для кодирования-го сообщения.

Пример 3.2. Процедура кодирования изложена в таблице 3.3.

Таблица 3.3
1	2		3	4	5	6	7	8	9
Анс-ль	Вер. P							Коды	Условн. вер.
	0.20		1	11				11	1
	0.2		1	10	101			101	2/3
	0.19		1	10	100			100	1/3
	0.15		0	01	011			011	2/3
	0.10		0	01	010			010	1/3
	0.08		0	00	001			001	1/3
	0.06		0	00	000	0001		0001	1/4
	0.01		0	00	000	0000	00001	00001	1/5
	0.01		0	00	000	0000	00000	00000	0

В примере используется тот же ансамбль сообщений с теми же вероятностями реализаций элементов ансамбля. В колонке 3 показано разбиения множества сообщений на

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

Кодовое дерево для рассматриваемого примера приведено на рисунке 1.2.

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

Характеристики , ,,,остаются неизменными

3.16993.

=2.79465

0.881615 ,0.118385.

1.

Рассмотрим ансамбль . По формуле полной вероятности получим =0.57367, =0.42633.

Количество информации, содержащееся в каждом символе ансамбля Yравно соответственно

0.801707 , 1.22996.

Энтропия ансамбля Yравна

0.984283 .

Соответственно коэффициент сжатия и коэффициент избыточности будут равны

0.984283,0.015717

Сравнивая коэффициенты сжатия и коэффициенты избыточности ансамблей XиYвидно при кодировании по методу Шеннона, произошло увеличение коэффициента сжатия и уменьшение избыточности ансамбляY. Относительные величины равны соответственно

= 1.11645 , = 7.53229.

=

=2*0.2+3*(0.2+0.19+0.15+0.1+0.08)+4*0.06+5*(0.01+0.01)= 2.9