Лабораторная работа №9. Кафедра информационных систем и технологий

Кафедра информационных систем и технологий

по дисциплине «Теория информационных процессов и систем».

Тема:

«Эффективное кодирование на примере кода Хаффмена»

Выполнил студент группы ИС-19: Фомичев А.А.

Проверил: Родькина О.Я.

Нижний Новгород

2013 г.

Цель работы: изучение принципа эффективного кодирования источников дискретных сообщений.

Задание:

1) Изучить принцип эффективного кодирования источника дискретных сообщений (метод Хаффмена).

2) Осуществить кодирование каждого сообщения алфавита (см. таблицу 1), используя двоичный код:

· равномерный;

· код Хаффмена, в соответствии с заданным вариантом.

Таблица 1 Вероятности появления сообщений алфавита

Вариант
Знак
a1	0,28
a2	0,04
a3	0,16
a4	0,02
a5	0,13
a6	0,07
a7	0,30

3) Определить значения H_max(x), H(x) и .

4) Рассчитать значения К_сс и К_оэ.

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

Алгоритм кодирования Хаффмена состоит в следующем:

1. Сообщения располагаются в столбец в порядке убывания вероятности их появления.

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

3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.

A	p(ai)	Шаг 1	Шаг 2	Шаг 3	Шаг 4	Шаг 5	Шаг 6
a4	0,30	0,30	0,27	0,30	0,42	0,58
a7	0,28	0,28	0,28	0,28	0,30	0,42
a2	0,16	0,16	0,16	0,26	0,28
a5	0,13	0,13	0,13	0,16
a1	0,07	0,07	0,13
a6	0,04	0,06
a3	0,02

4. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые комбинации можно определить, приписывая левым ветвям объединения символ “1”, а правым - “0”, обозначаем “1” ветвь идущую от узла в сторону сообщения с большей вероятностью появления, “0” с меньшей вероятностью.

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