ТОИП РГР Теория

КОДИРОВАНИЕ СООБЩЕНИЙ С ИСПОЛЬЗОВАНИЕМ ПРОЦЕДУР ШЕННОНА–ФАНО, ХАФФМАНА

1. Цель работы

Целью данной работы является приобретение студентами навыков кодирования сообщений с использованием процедуры Шеннона–Фано и процедуры Хаффмана.

2. Задача

На вход канала связи поступают сообщения. Количество передаваемых сообщений известно и известны вероятности поступления каждого из сообщений на вход. Задачей является построение бинарного дерева, формирование кодов для каждого сообщения на основе полученного бинарного дерева процедурами Шеннона–Фано и Хаффмана, а также расчет средней длины кодового слова для каждого случая.

3. Теоретическая часть

Вероятностная модель кодируемых сообщений. Будем считать, что последовательность, которую нужно закодировать составлена из сообщений, принадлежащих некоторому конечному множеству с известным числом элементов N. Появление сообщений в последовательности носит вероятностный характер, т.е. каждому j -му сообщению () можно поставить в соответствие вероятность его появления () – условие нормировки. Сообщения кодируются последовательности двоичных знаков (0 и 1). В качестве критерия экономности кода выступает средняя длина кодового слова, необходимая для кодирования одного сообщения. Экономное кодирование основано на использовании кодов с переменной длиной кодового слова. Для кодирования сообщений будем использовать множество двоичных кодовых слов переменной длины , причем = – длина кодового слова , соответствующего сообщению .

Тогда в качестве критерия эффективности кодирования сообщений множества S кодовыми словами множества K выступает величина , называемая средней длиной кодового слова и определяемая следующим образом:

(1)

Рассмотрим пример. Пусть множество сообщений характеризуется вероятностями появления, определяемыми по следующей формуле:

(2)

(можно проверить, что условие нормировки при этом соблюдается).

Воспользуемся для кодирования данных сообщений кодовыми словами рассмотренного выше префиксного кода так, как это показано в таблице 1.

Таблица 1.

Сообщение	Вероятность	Кодовое слово	Длина кодового слова
s1	1/55	111111	6
s2	2/55	111110	6
s3	3/55	11110	5
s4	4/55	1110	4
s5	5/55	1001	4
s6	6/55	1000	4
s7	7/55	110	3
s8	8/55	101	3
s9	9/55	01	2
s10	10/55	00	2

По формуле (1) получим:

(бит/сообщение).

Если бы мы закодировали сообщения равномерным кодом, то, согласно формуле (1.1 в лекционных материалах) нам потребовались бы кодовые слова длины (бит/сообщение), т.е. кодирование словами переменной длины оказывается более эффективным.

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

Как же выбирать кодовые слова в общем случае, чтобы для заданных вероятностей p₁, p₂, … , p_m обеспечить по возможности меньшую среднюю длину кодового слова, т.е. ?

Заметим, что если , то минимальную среднюю длину кодового слова обеспечивает равномерное двоичное кодирование. На каждом шаге двоичного кодирования производится разбиение множества сообщений на два подмножества, причем одному из них приписывается единица, а другому – ноль. Таким образом, на каждом шаге производится кодирование подмножеств равномерным кодом длиной в один двоичный знак. Отсюда следует принцип: нужно стремиться так производить разбиение на два подмножества, чтобы суммарные вероятности подмножеств были одинаковыми или как можно более близкими друг к другу.

Процедура Шеннона-Фано.

В этом алгоритме предварительно производится упорядочивание сообщений по возрастанию или убыванию вероятностей . Разбиение на подмножества производится путем выбора разделяющей границы в упорядоченной последовательности так, чтобы суммарные вероятности подмножеств были по возможности одинаковыми. Кодовое дерево, построенное этим методом для примера в таблице 1, приведено на рис.1. Возле каждой вершины дерева указывается суммарная вероятность соответствующего подмножества.

Выполнив расчеты по формуле (1), получим: =3,145 (бит/сообщение). Таким образом, код, полученный при помощи процедуры Шеннона-Фано, оказывается более экономным, чем код из таблицы 1.

Рис.1.

Кодовое дерево в процедуре Шеннона-Фано

Процедура Хаффмана.

Рассмотренная выше процедура Шеннона-Фано является простым, но не всегда оптимальным алгоритмом построения экономного кода. Причина состоит в том, что способ разбиения на подмножества ограничен: вероятности сообщений, отнесенных к первому подмножеству, всегда больше или всегда меньше вероятностей сообщений, отнесенных ко второму подмножеству. Оптимальный алгоритм, очевидно, должен учитывать все возможные комбинации при разбиении на равновероятные подмножества. Это обеспечивается в процедуре Хаффмана.

Процедура Хаффмана представляет собой рекурсивный алгоритм, который строит бинарное дерево «в обратную сторону», т.е. от конечных вершин к корню. Основная идея алгоритма состоит в том, чтобы объединить два сообщения с наименьшими вероятностями – например, p₁ и p₂ – в одно множество и далее решать задачу с m-1 сообщениями и вероятностями p₁’ = p₁ + p₂; p₂’ = p₃; … ; p_(m-1)’ = p_m. Кодовое дерево, построенное процедурой Хаффмана для рассматриваемого примера, приведено на рис.2.

Расчеты по формуле (1) дают среднее значение длины кодового слова =3,145 (бит/сообщение), что совпадает с результатом применения процедуры Шеннона-Фано. Это означает, что для данного примера процедура Шеннона-Фано также оказалась оптимальной.

Рис.2

Кодовое дерево в процедуре Хаффмана

4. Порядок выполнения работы

Для выполнения работы необходимо:

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

2. Получить у преподавателя вариант задания (все варианты приведены в отдельном файле).

3. В соответствии с заданием построить бинарное дерево, сформировать код каждого сообщения на основе полученного бинарного дерева и рассчитать среднюю длину кодового слова.

4. В соответствии со стандартными требованиями оформить отчет по работе.

9