Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Имеется некоторая трудность при распространении этой процедуры на недвоичные коды. Лемма 1 остается справедливой для недвоичного кодового алфавита. А лемма 2 не остается справедливой и возникает вопрос, имеются ли еще кодовые слова помимо х^ —ь которые должны отличаться от хк в последнем символе.
Определим полное кодовое дерево как конечное кодовое дерево, в котором из каждого промежуточного узла исходят D узлов следующего более высокого порядка. Как можно заметить из доказательства неравенства Крафта, для полного кодового дерева неравенство Крафта удовлетворяется с равенством.
70
Лемма 3. Число концевых узлов полного кодового дерева с алфавитом объема D имеет вид D -j- т (D — 1), где т — некоторое целое число.
Доказательство. Наименьшее полное дерево с алфавитом объема D имеет D концевых узлов. Если один из этих концевых узлов превращается в промежуточный узел, то образуется D новых концевых узлов и один узел теряется, в результате получаем приращение D — 1. Так как любое полное дерево может быть построено с помощью таких последовательных преобразований концевых узлов в промежуточные узлы и так как каждое такое преобразование увеличивает число узлов на D — 1, то окончательное число узлов должно иметь вид D + т (D —
-D- I
Ксловое Сообщение Р*(ч)
ОО *1 0,3
Of а2 0,25
fO аз 0,25
110 а* 0,10
111 а* 0,10
О
У Ю,55)
а
W, *5) '•
Рис. 3.4.1. Процедура кодирования Хаффмана.
Условимся теперь рассматривать каждое кодовое дерево как полное дерево, может быть, с некоторым числом В неиспользуемых концевых узлов, добавленных для полноты дерева. Ясно, что в оптимальном коде все неиспользуемые концевые узлы имеют ту же самую длину, что и самое длинное кодовое слово. Точно так же, меняя местами используемые и неиспользуемые концевые узлы, можно добиться того, чтобы неиспользуемые концевые узлы отличались лишь в последнем символе. Следовательно, оптимальное кодовое дерево должно иметь не более чем D — 2 неиспользуемых концевых узлов, так как если бы D — 1 неиспользуемых узлов группировались вместе, то соответствующее кодовое слово могло бы быть укорочено без нарушения свойства префикса. Число кодовых слов, сложенное с числом неиспользуемых узлов, имеет вид D + т (D — 1), это выражение однозначно определяет число неиспользуемых узлов полного дерева. Например, если D = 3, то каждое полное дерево имеет нечетное число узлов. Если К четно, то число неиспользуемых концевых узлов В для оптимального кода равно 1, а если К > 2 нечетно, то В = 0.
Для читателя, который лучше ориентируется в языке формул, мы получим точное выражение для В, замечая, что В + К = т (D — 1) + + D. Отсюда К — 2 = т (D — 1) + (Z) — 2 — В). Для оптимального кода 0 < В D — 2 и поэтому 0 D — 2 — В D — 2, следовательно, D — 2 — В равно остатку от деления К — 2 на D — 1; обозначим его черезRd-i (К — 2). Отсюда В = D — 2 — Rd-i (X—
— 2). Используя те же рассуждения, что и в лемме 1, получаем, что существует оптимальный код, у которого имеются В неиспользуемых
7J
узлов и D — В наименее вероятных узлов, соответствующих кодовым словам, отличающихся лишь в последнем символе. Таким образом, первый этап процедуры декодирования состоит в группировании D —
— В = 2 + Rd-i (К — 2) наименее вероятных узлов.
После этого начального этапа построение оптимального кода проходит так же, как и раньше. Производится редуцированный ансамбль с помощью объединения вероятностей предварительно сгруппированных кодовых слов. Легко проверить, что число сообщений в редуцированном ансамбле имеет.вид D -{- т (D — 1) и мы полагаем, что D менее вероятных из них отличаются лишь в последнем символе. Продолжая
Рг,(ак)
0 Ч о л
1 а? 0,3
20 а-ъ 0,2
21 а? 0,05
220 0,03
221 0,02
I 0,05
(0,3)2
Рис. 3.4,2. Кодирование по Хаффману при D = 3.
процедуру таким образом, в итоге получаем редуцированный ансамбль из D сообщений, для которого оптимальный код очевиден. Рис. 3.4.2 показывает построение в случае D = 3. Так как К = 6, то число сообщений, группируемых на начальном этапе, равно 2 + R2 (6 — 2) = = 2.
3.5. дискретные стационарные источники
В предыдущих параграфах рассматривались дискретные источники без памяти. В этом параграфе будет изучен эффект статистической зависимости между буквами источника.
Пусть и — U-1, «о, иъ ...) обозначает последовательность букв, производимую источником, в котором каждая буква иг выбирается из дискретного алфавита. Полное вероятностное описание источника задается вероятностями Рг (ы/+ь uj+2, определенными для
всех L последовательностей всех начальных моментов / и всех последовательностей Uj+1, ..., uj+L. При таком подходе источник представляет собой не что иное, как произвольный дискретный случайный процесс.
Дискретный источник называется стационарным, если вероятностное описание не зависит от начала отсчета времени. Точнее, источник называется стационарным, если
