Лабораторная работа по теме: "Исследование оптимальных (в смысле минимальной средней длины кодового слова) кодов на примере кодов Шеннона-Фэно и Хаффмена."

Цель работы -: Закрепление теоретических знаний и приобретение практических навыков построения и использования эффективных (оптимальных) кодов на примере кодов Шеннона-Фэно и Хаффмена.

Теоретическое введение.

Обоснование и алгоритмы построения оптимальных кодов Хаффмена и Шеннона-Фэно изложены в п.п. 3.1 - 3.7 главы 3 учебного пособия по дисциплине Теория информации и кодирование [1].

В данной лабораторной работе предлагается на практике построить и использовать оптимальные коды Хаффмена и Шеннона-Фэно для кодирования и декодирования дискретных сообщений.

Коды Хаффмена

На этом алгоритме построена процедура построения оптимального кода, предложенная в 1952 году доктором Массачусетского технологического института (США) Дэвидэм Хаффменом[17]:

5) буквы первичного алфавита выписываются в основной столбец в порядке убывания вероятностей;

6) две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность;

7) вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние объединяются;

8) процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной единице.

Таблица 3.2.

Методика поясняется примером, представленным табл. 3.2.

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

Рис. 3.3. Кодовое дерево.

Для наглядности строится кодовое дерево. Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваивается символ 1, а с меньшей − 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до каждой буквы. Кодовое дерево для алфавита букв, рассматриваемого в таблице, изображено на рис. 3.3.

Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию (табл. 3.3).

Таблица 3.3

Коды Шеннона−Фэно

Ранее, независимо друг от друга Шенноном и Фэно была предложена другая процедура построения эффективного кода. Получаемый при ее помощи код называют кодом Шеннона−Фэно.

Код Шеннона−Фэно строится следующим образом:

6) буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей;

7) затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы;

8) всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним 0;

9) каждая из полученных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. ;