0,36 0,14 0,13 0.12 0,10 0.09 0,04 0.02

О 0,06

0,27

0,22

0,15

0.63

0,37

Рис. 3.3 6. Код Хаффмена для примера 3.3 2

где y?,/J = 7?-среднее ЧИСЛО битов на исходный СИМВОЛ. Следовательно, R можно сделать как угодно близким к Н(Х), выбирая J достаточно большим.

Пример 3.3.3. Выход ДИБП состоит из символов jc, ,jc, и Хз с вероятностями 0,45, 0,35 и 0,20 соответственно. Энтропия этого источника Я(.А) =1,518 бит/символ. Код Хаффмена для этого источника, данный в табл. 3.3.2, требует Л, =1,55 бит/символ и приводят к эффективности 97,9 %, Если посредством алгоритма Хаффмена символы закодированы парами, результирующий код выглядит так, как показано в табл. 3.3.3. Энтропия источника для пар символов 2Я(А) = 3,036 бит/пара символов. С другой стороны, код Хаффмена требует = 3,0675 бит/пара символов. Таким образом, эффективность кодирования увеличилась до 2Н{Х)1К = 0,990 (до 99,0 %).

Таблица 3.3.2. Код Хаффмена для примера 3.3.3

Символ

Вероятность

Собственная информация

Итак, мы продемонстрировали, что эффективное кодирование для ДИБП может быть выполнено на посимвольной основе, если использовать неравномерный код, основанный на алгоритме Хаффмена. Кроме того, эффективность процедуры кодирования увеличивается при кодировании блоков из J символов одновременно. Таким образом, выход ДИБП с энтропией Н{Х) может быть закодирован неравномерным кодом со средним числом битов на исходный символ, которое может быть сделано как угодно близким к Н{Х).

Таблица 3.3.3. Код Хаффмена для кодирования пар символов

3.3.2. Дискретные стационарные источники

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

Оценим энтропию некоторой последовательности символов от стационарного источника. Из определения в (3.2.13) и результата, данного в (3.2.15), энтропия блока случайных переменных XXj.-.X равна

ЩХ,Х,...Х,) = ZЩХ, I Х,Х,...Jr,.,), (3.3.14)

где Н{Х, I XX ...X,) - условная энтропия /-го символа при условии, что источник выдат предыдущие /-1 символов. Энтропия на символ для -символьного блока определяется как

Н,{Х) = -Н{Х,Х.,...Х,). (3.3.15)

Мы определяем количество информации стационарного источника как энтропию на символ в (3.3.15) в пределе при ->ос, т.е.

Н{Х) = lini Н, {X) = \\т-Н{Х,Х. ...X,). (3.3.16)

Существование этого предела установлено ниже.

В качестве альтернативы мы можем определять энтропию на символ источника как условную энтропию H{X\XX.j-- Xi в пределе при А:->оо. К счастью, этот предел также существует и идентичен пределу в (3.3.16). То есть

Я„() = ИтЯ(Г, ад...Х,.,). (3.3.17)

Этот результат также установлен ниже. Наше изложение использует подход Галлагера (1968). Во-первых, мы покажем, что

Н{Х, IХ,Х, ...Х, ,)<Я(Х, , IХ,Х,...Х, ,) (3.3.18)

для Л>2. С учётом предьщущего результата, согласно которому наложение условий на случайную переменную не может увеличивать её энтропию, мы имеем

Н(Х, IХ,Х,...Jr, ,) < ЩХ, I Х,Х, ...AV.). (3.3.19)

В силу стационарности источника имеем

Н{Х,\Х2Х,...Х, ,)Н{Х,,,\Х,Х,...Х,,). (3.3.20)

Следовательно, (3.3.18) следует немедленно. Этот результат демонстрирует, что НХ/. I А, Аз • • X ) - не возрастающая последовательность (с ростом к).

Во-вторых, мы имеем результат

Н,(Х)>ЩХ,\Х,Х,-Х,,,), (3.3.21)

который следует непосредственно из (3.3.14) и (3.3.15) и того факта, что последний член в сумме (3.3.14) является нижней границей для каждого из остальных к-\ членов. В-третьих, по определению Н{Х) мы можем записать

Я,(АГ) -j[HiX,X, ...Х, ,) + Н(Х, IX, ...Х, ,)] = к

= к(к- 1)Я,.,(X) + ЩХ, \Х,...Х, ,)]<Я,.,(X) +1Я,iX), к к к

что приводит к

Н,(Х)<НаХ). (3.3,22)

Следовательно, Я (X) - не возрастающая последовательность (с ростом к). Поскольку Н{Х) и условная энтропия Я(А AiA",...Aj ,) не отрицательны и не возрастающие (с ростом к), оба предела должны существовать. Их предельные выражения могут быть установлены с использованием (3.3.14) и (3.3.15), чтобы выразить Н{Х) как

H,.j{X)-mx,x,...x, ,)+

к + J

+-[щх,\х,...х, ,)+тх,,,\х,...х,)+...+щх,,\х,...х,, Л k+J

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

Н,(Х)<-ЩХ,Х,...Х, ,) + {ЩХ,\Х,Х,...Х, ,). (3.3.23)

k+j k+j

Для фиксированного к в пределе для (3.3.23) при j -со получаем

Н„(Х)<Н(Х,\Х,Х,...Х, ,). (3.3.24)

Но (3.3.24) справедливо для всех к; следовательно, это справедливо и для к-*<у:. Поэтому

H„(X)<\imH(X,\X,X,...X, ,). (3.3.25) С другой стороны, с учётом (3.3.21) мы получаем в пределе для к ->оо

Н{Х)>ШН(Х,\X,X,...X,.j, (3.3.26)

что устанавливает (3.3.17).

Теперь предположим, что мы имеем дискретный стационарный источник, который

вьщаёт J символов с энтропией на символ Hj{X). Мы можем кодировать

последовательность J символов кодом Хаффмена переменной длины, который удовлетворяет префиксному условию при использовании процедуры, описанной в предыдущем разделе. Результирующий код имеет среднее число бит для блока с J