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

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

Вариант 1.

Вероятность.	P1.	P2.	P3.	P4.	P5.	P6.	P7.	P8.
Значение.	0,12.	0,04.	0,16.	0,08.	0,05.	0,33.	0,15.	0,07.

Вероятностная модель кодируемых сообщений

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

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

(1).

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

(2).

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

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

Таблица 1.

Сообщение.	Вероятность.	Кодовое слово.	Длина кодового слова.
s1.	1/55.
s2.	2/55.
s3.	3/55.
s4.	4/55.
s5.	5/55.
s6.	6/55.
s7.	7/55.
s8.	8/55.
s9.	9/55.
s10.	10/55.

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

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

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

(бит/сообщение), т. е. кодирование словами переменной длины оказывается более эффективным.

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

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

Заметим, что если.

.

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