Изучение методов рационального кодирования сообщений

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

Рязанский Государственный  Радиотехнический Университет 
 

Кафедра вычислительной и  прикладной математики 
 
 
 
 
 

  «Изучение методов рационального кодирования сообщений» 
 

по курсу 

«Теория информации» 
 
 
 
 
 
 

                      
 
 
 
 
 
 

Рязань 2008 
 

Цель работы: Получение навыков кодирования  сообщений рациональными методами. 

Задание: Ансамбль сообщений задан следующей таблицей: 

 

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

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

Определить основные характеристики кодов. 

Результаты выполнения работы: 

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

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

Таблица 1.

 

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

 

   Предельная  энтропия для источника сообщений  с 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 раза при  использовании кода Шеннона-Фано или  кода Хаффмана.