Кодирование сообщений словами переменной длины

 

Пусть имеется множество передаваемых сообщений S ={s_j}, i=1,…,m, причем известна вероятность p_j появления каждого из сообщений на входе устройства кодирования (при соблюдении условия нормировки ). Пусть также имеется множество двоичных кодовых слов переменной длины, используемых для кодирования этих сообщений K ={k_j}, причем l_j =l(k_j) – длина кодового слова k_j, соответствующего сообщению s_j.

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

(1.3)

Рассмотрим пример. Пусть множество сообщений S ={s₁, s₂, …, s₁₀} характеризуется вероятностями появления, определяемыми по следующей формуле:

(1.4)

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

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

Таблица 1.1

Сообщение sj	Вероятность pj	Кодовое слово kj	Длина кодового слова lj
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

 

 

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

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

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

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

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

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

Рассмотрим две процедуры экономного кодирования, основанные на использовании этого принципа.

 

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

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

Рис.1.5

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

 

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

 

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

 

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

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

 

Рис.1.6

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

 

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