Министерство образования и науки Российской Федерации

Рязанский Государственный Радиотехнический Университет
Кафедра вычислительной и прикладной математики
 «Изучение методов рационального кодирования сообщений»
по курсу
«Теория информации»
                    
Рязань 2008
Цель работы: Получение навыков кодирования сообщений рациональными методами.
Задание: Ансамбль сообщений задан следующей таблицей:

Xi	X1	X2	X3	X4	X5	X6	X7	X8
P(Xi)	0.22	0.2	0.16	0.16	0.1	0.1	0.04	0.02

Корреляционные связи между сообщениями отсутствуют. Длительность сообщения есть τ.

Произвести кодирование двоичным кодом по методам Шеннона-Фано и Хаффмена.

Определить основные характеристики кодов.
Результаты выполнения работы:
 Метод Шеннона-Фано.

Кодовые комбинации, для соответствующих состояний источника находятся следующим образом. Состояния источника сообщений ранжируются в порядке убывания их вероятностей. Весь алфавит источника сообщений делится на две группы таким образом, чтобы суммарные вероятности сообщений каждой группы были примерно одинаковы. Далее, каждому состоянию из одной группы ставится в соответствие символ 1, а другой – 0. Там  для каждой группы снова производится разбиение на равновероятные подгруппы и так далее до тех пор, пока в каждой подгруппе не останется по одному символу. Рассмотрим процесс построения кодовых комбинаций для источника с 8-ю состояниями (табл. 1).
Таблица 1.

I	P(Xi)	1-й шаг	2-й шаг	3-й шаг	4-й шаг	5-й шаг	6-й шаг	7-й шаг	Код Шеннона-Фано	Равномер ный код	Длит. сообщ.
1	0.22	/2	/2						00	000	2 τ
2	0.2								01	001	2 τ
3	0.16			/2	/2				100	010	3 τ
4	0.16								101	011	3 τ
5	0.1					/2			110	100	3 τ
6	0.1						/2		1110	101	4 τ
7	0.04							/2	11110	110	5 τ
8	0.02								11111	111	5 τ

Энтропия источника, рассчитанная с помощью меры Шеннона:

Предельная энтропия для источника сообщений с 8-ю состояниями в соответствии с мерой Хартли:

.

Относительная энтропия m = H(X)/H_max(X) » 0,92. Коэффициент избыточности r = 1 - m » 0,08.
 Средней длительности кодовой комбинации:

=2,8 (при равномерном кодировании 3)

Процесс декодирования непрерывной последовательности кодовых комбинаций основан на процедуре, накопления получаемых символов до тех пор, пока не будет принят символ 1 или длина последовательности нулей не станет равной 7.

 

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

    Кодовые комбинации, для соответствующих состояний источника находятся следующим образом. Состояния источника ранжируем в порядке убывания их вероятностей. Два состояния, имеющие минимальные вероятности, объединяем в одно, вероятность которого равна сумме вероятностей объединяемых состояний. В результате объединения получаем новый набор состояний, число которых на единицу меньше первоначального. Полученные состояния снова ранжируем. Операция объединения повторяется. Так продолжается до тех пор, пока в результате объединения не будет получено одно состояние с вероятностью 1 (Рис.1). На основании результатов объединения состояний строится бинарное кодовое дерево. Узлам данного кодового дерева сопоставляются вероятности объединяемых состояний, а ветвям – символы 0 или 1 (Рис. 2).

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



Рис.1
символов 0 и 1 в кодовой комбинации, кодовые комбинации приведены в таблице 2.Сообщению с меньшей вероятностью соответствуют кодовые комбинации большей длины и наоборот.

Таблица 2



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

Энтропия источника, рассчитанная с помощью меры Шеннона: 2,75. Предельная энтропия для источника сообщений с 8-ю состояниями в соответствии с мерой Хартли: 3. Относительная энтропия m = H(X)/H_max(X) » 0,92. Коэффициент избыточности r = 1 - m » 0,08.Средняя длительность кодовой комбинации в данном случае: L_m = 2.8 (при равномерном кодировании 3).
Рис. 2
Скорость передачи информации при использовании кода Шеннона-Фано:  

Iш-ф=H(X)/Lm=0,98 Сд бит/сек;

При использовании равномерного кода: Iр=H(X)/Lm=0,92 Сд бит/сек;

При использовании кода Хаффмана: Iх=H(X)/Lm=0,98 Сд бит/сек.

Коэффициент использования канала при использовании кода Шеннона-Фано: λш-ф=0,98;

При использовании равномерного кода: λр=0,92;

При использовании кода Хаффмана: λх=0,98.
Скорость передачи информации по сравнению с равномерным кодом возрастет в 1,07 раза при использовании кода Шеннона-Фано или кода Хаффмана.