Задание №1

Практическая работа «Кодирование информации. Код Шеннона-Фано. Код Дэвида Хаффмана»

(2+2+2+2+2+4=14 баллов)

ОПТИМАЛЬНЫЙ ПОБУКВЕННЫЙ КОД – КОД ХАФФМАНА

Предложенный Хаффманом алгоритм построения оптимальных неравномерных кодов – одно из самых важных достижений теории информации как с теоретической, так и с прикладной точек зрения. Этот алгоритм был придуман в 1952 г. студентом Дэвидом Хаффменом в процессе выполнения домашнего задания.

СУТЬ АЛГОРИТМА ХАФФМЕНА

Строится кодовое дерево — граф древовидной формы. Дерево строится от концевых вершин по направлению к корню, снизу вверх.

Разберем алгоритм на примере.

Нам дана последовательность символов X1, X2, X3, X4, X5, X6 с соответствующими вероятностями 0,15; 0,3; 0,2; 0,15; 0,1; 0,1. Необходимо построить код Хаффмана.

1. Упорядочить все элементы сообщения по невозрастанию или по неубыванию (это не принципиально) их вероятностей (частот встречаемости). Эти элементы образуют концевые вершины дерева, называемые также листьями.

Х2 х3 Х1 Х4 Х5 Х6

0,3 0,2 0,15 0,15 0,1 0,1

2. Выбрать две из них с наименьшими вероятностями. Построить новую вершину, одна ветвь которой идет к одному элементу, а другая — к другому. Этой новой вершине припишем вероятность, равную сумме вероятностей вершин, с которыми она соединена.

Х2 х3 Х1 Х4 Х5 Х6

0,3 0,2 0,15 0,15 0,1 0,1

3. Рассмотреть все оставшиеся концевые вершины и только что построенную. Выбрать из них две с минимальными вероятностями и соединить их с новой вершиной, которой припишем сумму вероятностей объединяемых вершин.

Х2 х3 Х1 Х4 Х5 Х6

0,3 0,2 0,15 0,15 0,1 0,1

4. Поступаем так до тех пор, пока не останется ни одной пары вершин, которые можно было бы объединить. В результате получится дерево.

Х2 х3 Х1 Х4 Х5 Х6

0,3 0,2 0,15 0,15 0,1 0,1

5. Разметить ветви, выходящие из вершин: одной из них припишем 1, а другой 0. Сделаем это для всех пар ветвей.

Х2 х3 Х1 Х4 Х5 Х6

0,3 0,2 0,15 0,15 0,1 0,1

00 10 010 011 110 111

6. Последовательность нулей и единиц, которую можно собрать, двигаясь от корня дерева к концевой вершине, образует кодовое слово для соответствующего элеме нта

Средняя длина кодового слова вычисляется как взвешенная вероятностями сумма длин всех кодовых слов:

L_cp = p₁L₁ + p₂L₂ +... + p_nL_n, где p₁,..., p_n — вероятности кодовых слов; L₁,..., L_n — длины кодовых слов.

L_cp = 0,3*2+0,2*2+0,15*3+0,15*3+0,1*3+0,1*3 = 2,5 (бит)

χ = Н / L_ср ; Н=2,8 (бит) χ = 2,5 / 2,5=1

Задание №1.

1.1. Построить код Шеннона-Фано для множества из семи сообщений Х _i с вероятностями 0,1; 0,15; 0,15; 0,3; 0,25; 0,04; 0,01. Определить среднюю длину кодового слова, эффективность кода. (Учитывайте энтропию источника сообщения). Оформить задание в табличном процессоре.

1.2. Построить код Хаффмана для множества из семи сообщений Х _i с вероятностями 0,1; 0,15; 0,15; 0,3; 0,25; 0,04; 0,01. Определить среднюю длину кодового слова, эффективность кода. (Учитывайте энтропию источника сообщения). (Расчеты - в табличном процессоре. Построение дерева Хаффмана – «в ручную»).

Сравнить эффективности кодов, полученных по методу Шеннона-Фано и Хаффмана.

Задание №2. Для последовательности сообщений Z _i с вероятностями 0,04; 0,05; 0,29; 0,17; 0,24; 0,12; 0,08; 0,01 постройте код Шеннона-Фано и Хаффмана. Определите для каждого способа кодирования длину кода и эффективность кода. Сравните эффективности кодов.

Поиск по сайту: