Рис. 3.3.3. Конструирование двоичного дерева, встроенного в полное дерево

Чтобы доказать, что (3.3.8) является необходимым условием, мы заметим, что в дереве порядка п = п, число конечных узлов, отсечённых от общего числа 2 конечных узлов, равно

2"-" < 2". Следовательно, т" < 1,

и доказательство (3.3.8) закончено. Неравенство Крафта можно использовать для доказательства следующей теоремы кодирования источника (без шумов), которая применяется к кодам, удовлетворяющим префиксному условию.

Теорема кодирования источника П. Пусть Jlf-ансамбль символов двоичного источника без памяти с конечной энтропией Н{Х) и выходными символами х/,\<к < L, с соответствующими вероятностями выбора p,\<k<L. Существует возможность создать

код, который удовлетворяет префиксному условию и имеет среднюю длину R , которая удовлетворяет неравенству

ЩХ)<К<ЩХ) + 1. (3.3.9)

Чтобы установить нижнюю границу в (3.3.9), обратим внимание на то, что для кодовых слов, которые имеют длину , 1<к< L, разность Н{Х)- R может быть выражена в виде

Н{Х) -RYjPi log:--Е = Z А log: -

А-1 рк *•! *-1 рк

Используя неравенство Inх < д; -1, из (3.3.10) находим

(3.3.10)

HiX)-R<{\og,e)Y,Pk

. рк

<(log,e)

Е2--1

<0.

где последнее неравенство следует из неравенства Крафта. Равенство имеет место, если, и только если -2" для \ <к< L.

Верхняя фаница в (3.3.9) может быть установлена при предположении что щ,\<к<1 - целые числа, выбираемые из условия 2"<2""**. Но если р>2"" просуммированы по \<k<L, получаем неравенство Крафта, для которого мы демонстрировали, что там существует код, удовлетворяющий префиксному условию. С

другой стороны, если мы берем логарифм < 2 , получаем

logA <-«t+l

или, что эквивалентно,

<l-logft. (3.3.11)

Если умножить обе части неравенства (3.3.11) на рк и просуммировать по \<k<L, получаем желательную верхнюю границу, данную в (3.3.9). Это завершает доказательство (33.9)

Мы установили, что коды переменной длины, которые удовлетворяют префиксному условию, - это эффективные коды для любого дискретного источника без памяти (ДИБП) с символами, имеющими различную априорную вероятность. Опишем теперь алгоритм для построения таких кодов.

Алгоритм кодирования Хаффмена. Хаффмен (1952) разработал алгоритм кодирования переменной длины, основанный на знании априорных вероятностей символов

р(х, / = 1,2 . Z,. Этот алгоритм оптимален в том смысле, что среднее число двоичных

символов, требуемых для представления исходных символов, минимально. Получаемые кодовые слова удовлетворяют префиксному условию, определенному выше, что позволяет уникально и мгновенно декодировать полученную последовательность. Мы проиллюстрируем этот алгоритм кодирования посредством двух примеров.

Пример 3.3.1. Рассмотрим ДИБП с семью возможными символами .....х.

имеющими вероятности выбора, иллюстрируемые рис. 3.3.4.

0.35 0.30 0,20 0,10 0,04 0.005 0,005

0,65

О 0,01

0.05

0.15

0,35

Рис. 3.3.4. Пример кодирования ДИБП кодом переменной длины

Мы упорядочили символы источника в порядке убывания вероятностей, т.е. /(a-)> P(xj>...> . Процесс кодирования начинаем с двух наименее вероятных символов и .v,. Эти два символа объединяем, как показано на рис. 3.3.4, причем верхнему ветвлению присваиваем «О», а нижнему - «1». Вероятности этих двух ветвей складываются, и общему узлу присваивается суммарная вероятность, равная в данном случае 0,01. Теперь мы имеем исходные символы x,,Xj,...,X3 плюс новый символ,

обозначим его .х , полученный объединением и . На следующем шаге снова объединяются два наименее вероятных символа из набора Ху,Хт,х...х,х,х1. Это хих. которые имеют объединенную вероятность 0,05. Переходу от х присваиваем О», а переходу от - «1». Эта процедура продолжается, пока мы не исчерпаем все возможные символы источника. Результат - кодовое дерево с ветвями, которые содержат требуемые

кодовые слова. Кодовые слова получаются, если двигаться от самого правого узла дерева и переходя к самому левому узлу. Результирующие кодовые слова приведены на рис. 3.3.4. Среднее число двоичных элементов на символ этого кода R =2,21 бит/символ. Энтропия источника-2,11 бит/символ.

Заметим, что полученный код не единственно возможный. Например, на предпоследнем шаге процедуры кодирования мы имеем равный выбор между x и х\, имеющими одинаковые вероятности. В этом пункте мы соединили л:, и л:,. В альтернативном коде мы можем соединить х, я х. Результирующий код для этого случая иллюстрируется на рис. 3.3.5.

0.35 6,30 0,20 0,10 0,04 0,005 0,005

О 0,01

0,05

0.15

0,35

0.65

Рис. 3,3.5. Альтернативный код дЛя ДИБП в примере 3.3.1

Среднее число бит на символ для этого кода также равно 2.21. Следовательно, полученные коды одинаково эффективны. Кроме того, назначение «О» верхнему переходу и «1» нижнему (менее вероятному) переходу выбрано произвольно. Мы можем просто поменять местами О и 1 и получить ещё эффективный код, удовлетворяющий префиксному условию.

Пример 3.3.2. В качестве второго примера определим код Хаффмена для выхода ДИБП, иллюстрируемый на рис. 3.3.6. Энтропия этого источника Н{Х) 2,63 бит/символ.

Код Хаффмена, показанный на рис. 3.3.6, имеет среднюю длину R - 2,70 бит/символ. Следовательно, его эффективность составляет 0,97.

Алгоритм кодирования переменной длины (Хаффмена), описанный в предыдущих примерах, генерирует префиксный код, имеющий среднюю длину R, которая удовлетворяет (3.3.9). Однако вместо посимвольного кодирования более эффективной является процедура, основанная на кодировании блоков из J символов одновременно. Б таком случае границы в (3.3.9) в теореме кодирования источника II становятся другими:

JH{X)<Rj <JH(X) + l,

(3.3.12)

так как энтропия У-символьного блока от ДИБП равна JH{X) , и R, - среднее число битов в J-символьном блоке. Если мы разделим (3.3.12) на J, то получим

H(X)<<H(X)+j,

(3.3.13)