11

Кодирование информации при передаче без помех эффективное кодирование код шенона-фано

Используется для случая отсутствия статистической взаимосвязи между знаками.

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

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

Знаки	Вероятность	Кодовые комбинации		По методу Хаффмана
Z1	0,21	1 1		0 1
Z2	0,18	1 0 1		1 1 1
Z3	0,16	1 0 0		1 1 0
Z4	0,12	0 1 1		1 0 0
Z5	0,1	0 1 0		0 0 1
Z6	0,08	0 0 1 1		1 0 1 1
Z7	0,06	0 0 1 0		1 0 1 0
Z8	0,04	0 0 0 1		0 0 0 1
Z9	0,03	0 0 0 0 1		0 0 0 0 1
Z10	0,02	0 0 0 0 0 1		0 0 0 0 0

Средняя энтропия на один знак:

H(Z) = – (0,21 * log₂0,21 + 0,18 * log₂0,18 + 0,16 * log₂0,16 + 0,12 * log₂0,12 + 0,1 * log₂0,1 + 0,08 * log₂0,08 + 0,06 * log₂0,06 + 0,04 * log₂0,04 + 0,03 * log₂0,03 + 0,02 * log₂0,02 = 3,083 (бит).

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

= 0,21 * 2 + 0,18 * 3 + 0,16 *3 + 0,12 * 3 + 0,1 * 3 + 0,08 * 4 + 0,06 * 4 + 0,04 * 4 + 0,03 * 5 + 0,02 * 6 = 3,13.

Метод хаффмана

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

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

Для двоичного кода методика сводится к следующему:

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

2. Два последних знака объединяются в один вспомогательный знак с суммарной вероятностью.

3. Знаки снова сортируются по убыванию вероятностей.

4. Пункты 2 и 3 повторяются до тех пор, пока не останется единственный знак с вероятностью, равной 1.

Знаки	Вероят-ности	Вспомагательные столбцы
		1	2	3	4	5	6	7	8	9
Z1	0,21	0,21	0,21	0,21	0,21	0,26	0,34	0,4	0,6	1
Z2	0,18	0,18	0,18	0,18	0,19	0,21	0,26	0,34	0,4
Z3	0,16	0,16	0,16	0,16	0,18	0,19	0,21	0,26
Z4	0,12	0,12	0,12	0,14	0,16	0,18	0,19
Z5	0,1	0,1	0,1	0,12	0,14	0,16
Z6	0,08	0,08	0,09	0,1	0,12
Z7	0,06	0,06	0,08	0,09
Z8	0,04	0,05	0,06
Z9	0,03	0,04
Z10	0,02

Строим кодовое дерево:

1. Из точки р = 1 направляем две ветви, причем ветви с большей вероятностью присваиваем 1, а с меньшей – 0.

2. Возле каждой стрелки ставим вероятности, на которые разделяется эта сумма (для однозначности слева ставим большую вероятность, справа – меньшую вероятность).

3. Производим ветвление до тех пор, пока не дойдем до вероятности каждого знака.

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