Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
жество двоичных кодовых слов для этого источника и пусть п1( ..., Пц— длины кодовых слов. Кодовые слова хи ..., хд, соответствующие оптимальному коду, в общем случае не являются единственными и часто длины п1г ..., 1%к не являются единственными (см. задачу 3.13). Далее будут получены некоторые условия, которым должен удовлетворять по крайней мере один оптимальный код, и затем будет показано, как построить код, удовлетворяющий этим условиям. Мы ограничимся рас-68
смотрением префиксных кодов, так как любое множество длин, получаемых на однозначно декодируемом коде, можно получить на префиксном коде.
Лемма 1. Для любого заданного источника с К ^ 2 буквами существует оптимальный двоичный код, в котором два наименее вероятных кодовых слова хк и хк — \ имеют одну и ту же длину и отличаются лишь последним символом: хк оканчивается на 1, a x^_i на 0.
Доказательство. Во-первых, заметим, что по крайней мере для одного оптимального кода пк больше или равно остальным длинам кодовых слов. Чтобы показать это, рассмотрим код, в котором tiK <С nt для некоторого г. Если кодовые слова хг и хк заменить одно другим, то п изменится на величину
А = Р (at) пк + Р (ак) ni — P(ai)ni~P (ак) пк =
~ [Р (ai) — Р (ак)) [пк — «Л<0. (3.4.1)
Следовательно, любой код может быть изменен так, чтобы сделать пк максимальной длиной, не увеличивая п. Далее заметим, что в любом оптимальном коде, для которого пк является наибольшей длиной, должно быть другое кодовое слово, отличающееся от хк лишь в последнем символе, в противном случае последний символ хк мог бы быть отброшен без нарушения свойства префикса. Наконец, если х* есть кодовое слово, отличающееся от хк лишь в одной позиции, то должно быть ni S? «/с-i и, как показывает (3.4.1), xt- и х^_1 можно поменять местами без увеличения п. Таким образом, существует оптимальный код, в котором хк и Хк — j отличаются лишь в последнем символе. Эти слова, если необходимо, можно поменять местами, чтобы получить хк оканчивающимся на 1. |
С помощью этой леммы задача построения оптимального кода сводится к задаче построения хь ..., х/с_2 и отысканию первых пк — 1 символов х/с- Определим теперь редуцированный ансамбль U' как ансамбль, состоящий из букв а\, а'2, ..., ak—i с вероятностями
, \P(ak), k<^K—2,
Pr{ak)~ {Р(ак^{) + Р(ак), k = K-1- (3'4'2)
Любой префиксный код для U’ можно превратить в соответствующий префиксный код для U простым добавлением концевого символа
0 к xJc^i для получения xK^i и добавлением концевого римвола 1 к x^_i для получения х^. Это устанавливает взаимно однозначное соответствие между множеством префиксных кодов для U' ^множеством тех префиксных кодов для U, в которых хк и х^_ i отличается лишь последним символом; хк кончается на 1, a xK_i кончается на 0.
Лемма 2. Если некоторый префиксный код для U' является оптимальным, то соответствующий ему префи!й;ный код для U является оптимальным.
69
Доказательство. Длины п'h кодовых слов для V связаны с длинами пк соответствующего кода для U соотношениями
{n'k\ ks^K—2,
"*=K-i + l; k = K-\, К. (3-4-3)
Следовательно, средние длины п и п связаны равенством
К К-2
«=~2 P(ak)nk= 2 Р(ак)Пк + [Р(ак-\) + Р(ак)](пк-1 + 1)-= k=\ k=i
К-2
= 2 Pr(afc)ttft + Pr(«K-i)[«'K-i-rll=-H' + Pr(a/<-i)- (3.4.4)
*= i
Так как п и п' отличаются лишь на фиксированное число, независящее от кода для U', то можно минимизировать п в классе кодов, у которых хк и x/f_i отличаются лишь в последнем символе, минимизируя п . Но согласно лемме 1 код из этого класса минимизирует п по всем кодам, обладающим свойством префикса. |
Задача отыскания оптимального кода сведена теперь,к задаче отыскания оптимального кода для ансамбля, имеющего на одно сообщение меньше. Но теперь редуцированный ансамбль может иметь свои два наименее вероятные сообщения сгруппированными вместе, и может быть произведен следующий редуцированный ансамбль. Продолжая таким образом, мы постепенно достигнем того, что получится ансамбль, состоящий только из двух сообщений, и тогда оптимальный код, очевидно, получается приписыванием 1 одному сообщению и 0 другому.
Систематическая процедура для выполнения описанных выше операций приведена на рис. 3.4.1. Вначале свяжем вместе два наименее вероятных сообщения (в рассматриваемом случае а4 и а5), полагая, что последним символом для а4 является 0 и последним символом а5 является 1. Складывая вероятности сообщений ai и а5, находим, что два наименее вероятных сообщения в редуцированном ансамбле будут а3 и а\. На следующем этапе двумя наименее вероятными сообщениями будут аг и а2, но на этот раз остались только два сообщения. Рассматривая получающийся в результате рисунок, видим, что мы построили кодовое дерево для U, начав с наиболее удаленных ребер и спускаясь вниз с основанию. Кодовые слова считаются по этому дереву справа налево.
