3.6    Однозначно декодируемые коды. Неравенство Крафта

Для уменьшения длины кодового текста и с целью экономии времени его передачи сообщения, встречающиеся чаще, кодируют словами мень­шей длины, а редкие сообщения кодируют словами большой длины. От­четливо это видно на примере азбуки Морзе. Рассмотрим произвольный ансамбль сообщений А = {А\,..., Ап} с набором вероятностей Р(А\) >

> Р(А2) > ••• > Р{Ап),'^2 Р(Аг) = 1. Применим т.н. алгоритм кодирования Фано. Разобьем множество А на две группы так, чтобы суммы веро­ятностей сообщений каждой из двух групп были как можно более близки друг к другу:

Припишем сообщениям 1-ой группы А\ символ 0, сообщениям из груп­пы А2 - символ 1. По этому принципу каждая из групп А\, А2 разбивается на два множества: А\ = А[ и А'{, А2 = А2 и А2. Припишем сообщениям из А[ символ 00, из А'{ - символ 01, из А2 - символ 10, из А2 - символ 11. Продолжаем данный алгоритм до получения множеств, состоящих из 1 сообщения. В результате каждому сообщению ставится в соответствие пкодовое слово из 0 и 1. Чем больше вероятность Р(щ) сообщения А;и тем короче будет соответствующее кодовое слово. Указанный алгоритм может быть интерпретирован на языке теории графов. Именно, первый шаг ал­горитма Фано соответствует графу (дереву):

Л А2

 

В результате мы получим кодовое дерево Фано нашего ансамбля (множе­ства) сообщений. Разберем пример. Пусть дано множество А = {А\,..., А?} из 7 сообщений, вероятности которых равны соответственно р\ = р2 = = 1/4, Рз = Р4=Р5 = 1/8 и р6 = р7 = 1/16.

При первом разбиении А\ = {А\, А2},   А2 = {Л3, -Ь- -Ь- Л(;. А>?}.

При втором разбиении А[ = {А\}, А'{ = {А2}, А2 = {Л3, А4}, А2 = {Л5, Лб, Л7}. Продолжая аналогичные разбиения с множествами А2 и Л2', мы получаем следующее дерево и соответствующие кодовые слова:

а)

сообщения

Аг

А2

А5

А4

А5

А6

А7

кодовые слова

00

01

100

101

ПО

1110

1111

Покажем экономность вышеприведенного кодирования Фано примера из семи сообщений {Аі,..., А7} по сравнению с равномерным кодированием: Аі -> 000, А2 -> 001, А3 -> 010, Л4 -> 011, А5 -> 100, Л6 -> ПО, Л7 -> 101. Действительно, если нам предстоит передать текст, состоящий из 1000 сообщений в алфавите {А\,..., А7}, то при равномерном кодировании мы используем 3000 двоичных символов, а при кодировании методом Фано мы используем

250-2+250-2+125-3+125-3+125-3+1§5-4+^-4 = 2625 двоичных символов. Критерием экономности кода является т.н. средняя длина кодового слова

г=\

где іі - длина кодового слова для А{. Для нашего примера ё=2'| + 2- | + ^ +    • 2 = 2| ~ 2,62.

Упражнение 1. Закодировать двоичным кодом Фано следующие мно­жества сообщений, найдя соответствующую среднюю длину и построив ко­довое дерево:

а) десять сообщений с вероятностями

Р\ = Р-> = 0, 22; рз = р4 = р5 = р6 = 0,1; р7 = р8 = р9 = рю = 0,04;

б) четыре сообщения с вероятностями

Р\ = 0, 5; р2 = 0, 25; р3 = р4 = 0,125.

Выяснить выигрыш по сравнению с равномерным кодированием.

Применяя в алгоритме Фано разбиение не на две группы с одинаковыми суммарными вероятностями, а на оі равновероятных групп, мы придем к кодировке сообщений алфавитом из оі символов. Соответствующее дерево имеет в каждой вершине не более оі ребер.

Упражнение 2. Закодировать троичным кодом Фано 9 сообщений с вероятностями 1/3, 1/9, 1/9, 1/9, 1/9, 1/9, 1/27, 1/27,1/27.

Упражнение 3. Закодировать троичным кодом Фано 8 сообщений с вероятностями 0,3; 0,15; 0,15; 0,15; 0,07; 0,07; 0,07; 0,04.

Кодирование методом Фано является неравномерным. Ясно, что нерав­номерное кодирование приводит порой к неоднозначности декодирования. Например, если сообщения А\ и А2 кодируются соответственно 1 и 11, то кодированная последовательность 111 может быть дешифрована одним из следующих способов:

{АЪА2},{А2,А1},{АЬАЬА1\.

Если код удовлетворяет условию, что каждая последовательность кодовых символов единственным образом разбивается на кодовые слова, то такой код называется однозначно декодируемым (или кодом без запятой). При­мерами таких кодов является любой равномерный код, а также префикс­ный код (т.е. код, в котором никакое кодовое слово не является началом другого кодового слова). Код Фано является префиксным, так как кодовые слова соответствуют концевым вершинам кодового дерева. Более того, этот двоичный код является полным, т.е. добавление любого нового кодового слова в данном алфавите нарушает свойство префиксности.

Упражнение 4. Доказать, что соответствующие коды являются одно­значно декодируемыми и не являются префиксными

{1,10}, {01,10,011}.

Пусть V = {а1,..., адг} - некоторый префиксный двоичный код. Из пре­фиксности следует, что V - концевые вершины некоторого (двоичного) гра­фа (дерева)

Пусть щ - число кодовых слов длины к, т.е. щ - число вершин к-ото этажа. Ясно, что      < 2к. Так как из каждой вершины г-го этажа вырастает (априори) 2к~г вершин к-ото этажа, то в случае префиксного кода имеем неравенства

пк<2к - 2/-'Л/, - 2к^2п2-----2 • /7/,^,.

П\      По Пь

— + — Н-----Ь — < 1

2     22 2*

Если I - максимальная длина кодовых слов, то получаем так называемое неравенство Крафта

е

(1). £ % < 1 или 2^Г + 2^ Н-----Н     < 1, где ^ - длина Щ. I < N.

'1=1

Обратно, если выполнено неравенство (1), то существует префиксный код с длинами кодовых слов 12,..., 1м- Из (1) следуют неравенства: п\ < 2, гг2 < 4 — 2//1. щ < 8 — 4/71 — 2/7-2. • • • • На первом этаже двоичного дере­ва выберем п\ вершин, на 2-м этаже выберем произвольные п2 вершин, исходящие из свободных (невыбранных)вершин первого этажа и т.д. Соот­ветствующие двоичные кодировки образуют искомый префиксный код.

Упражнение 5. Префиксный код является полным тогда и только то­гда, когда ^г + 2^Н-----1-^=1.

УКАЗАНИЕ. Воспользоваться интерпретацией кода как двоичной запи­сью концевых вершин некоторого графа (дерева).

Замечание. Аналогично доказывается, что в алфавите из о1 символов существует префиксный код с длинами кодовых слов в1,...,едг тогда и только тогда, когда ^г + ^Н-----Ь ^ < 1.

Префиксный код Фано не является (в общем случае) оптимальным в том смысле, что средняя длина кодовых слов не является минимальной. Рассмотрим метод кодирования, принадлежащий Д. Хаффмену (1952 г.) и дающий префиксный оптимальный код. Рассмотрим ансамбль (множе­ство) сообщений А = {А\,..., Лдг}, вероятности которых равны соответ­ственно р\.р->- ■ ■ ■ -Рх- При этом можно считать, что р\ > р-> > • • • > р\. Предположим, что эти сообщения закодированы в двоичном алфавите сло­вами а\,а2,... ,а^, длины которых равны соответственно 1\,12,... Если < 1%, то, поменяв кодовые обозначения для Л^ и Л^, мы получим, что средняя длина уменьшится на величину

Р%к + Рш1ш - р%1ш - Ршк = {р% - Рш){к - 1ш) > 0.

Таким образом, при р^ < р^ мы можем уменьшить среднюю длину, если //_/ < //. Если р-, = />,-_ | и /;_| < //. то переставим сообщения Л; II Л^+1 местами (и соответственно переставим их кодовые слова).

В результате указанных действий мы, стремясь к оптимальности коди­рования, можем так упорядочить наши сообщения Л1..... Л д- и так из­менить порядок кодирования словами {щ}, что р\ > Р2 > ••• > Рн и ^1<^2<"*<^л/'-В частности, сообщение Лдг кодируется словом наиболь­шей ДЛИНЫ /дг. ЕСЛИ Такое СЛОВО ЯВЛЯеТСЯ еДИНСТВеННЫМ (т.е.   /7у-1 < Ы),

то, отбрасывая последний символ слова адг (длины /дг), мы получим пре­фиксный КОД С Меньшей Средней ДЛИНОЙ. ЕСЛИ // = //_| = • • • = /дг, //_| < //

и среди слов щ,..., адг нет слов, отличающихся от адг последним символом, то опять, отбрасывая в слове адг последний символ, мы получим префикс­ный код с меньшей длиной. Если же слово ай(в < N — 1) имеет ту же длину /V (т.е. /.,. = 18+\ = • • • = / у) и отличается от адг последним символом, то, меняя местами кодовые слова а8 и а у_|. мы можем считать, что два по­следних слова наибольшей длины а/у_1,а/у отличаются только последним символом.я/у-1 а>м

 

Вернемся к нашему исходному множеству сообщений

Л = {Л,. Л2..... Лл-^. Л\-}.

где р; = р(Л/). / < N. Рассмотрим его сжатие Л11) = {Л |. Л2,..., Лдг^2, Л}. где р{Л;) = р;.1 < N — 2 и р(Л) = /;.у_| + /->у• Пусть для Л( 1' построена кодировка = {ах, а2, • • •, а/у-2> а}, т.е. кодовое дерево с концевыми вер­шинами а\,..., а/у_2, а. Сопоставим исходной системе Л следующую систе­му кодовых обозначений К = {а\,..., а/у_2, аО, а1}, т.е. а/у_1 = аО, адг = я1-Такое сопоставление называется расщеплением.

Лемма. Код К является оптимальным для системы Л, если код К^ был оптимальным для системы Л^.

ДОКАЗАТЕЛЬСТВО. Предположим противное. Тогда существует код системы К\ системы Л, для которого средняя длина 1\ = 1{К\) < 1{К) = I. Пусть К\ = {61,.... Ь\-\. Ь.х}- Согласно предыдущим замечаниям мы мо­жем считать, что Ь^^\ и бдг - кодовые слова для наименее вероятных со­общений Лдг^1 и Лдг. Причем они отличаются только последним симво­лом, т.е. 6дг-1 = ЬО, бдг = Ь1 (или Ь\-\ = Ь\. 6у = ЬО). Рассмотрим код к[1] = {Ъъ..., 6д^2, Ь} для Л{1). Имеем /"1 = 1[ + р (/; = /(^(1))). Так как 1[ <1к1 = ?+р (где V = 1(К^)), то ^ < V. Противоречие.

Согласно лемме, мы, используя несколько раз сжатие множества сообще­ний (соответственно, расщепление кодовых обозначений), можем построить оптимальный код (сначала сжимая, а потом расширяя).

Пример.


сообщ.

вероят-

сообщ.

вероят-

сообщ.

вероят-

средняя

л

ности

ам

ности

А®

ности

длина

Аг

0,5

0

Аг

0,5

0

Аг

0

0,5

 

А2

0,25

10

А2

0,25

10

А

1

0,5

1,75

А3

0,125

ПО

А

0,25

11

 

 

 

 

А4

0,125

111

 

 

 

 

 

 

 

Упражнение 6. Закодировать двоичным кодом Хаффмена множество сообщений с вероятностями:

а) 0,4; 0,15; 0,15; 0,15; 0,15;

б) 0,25; 0,2; 0,15; 0,15; 0,15; 0,1.