Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Доказательство. Назовем полным деревом порядка п с алфавитом объема D дерево, содержащее D'1 концевых узлов порядка п, в котором D узлов порядка i появляются из каждого узла порядка i — 1 для каждого г, 1 <; i <; п. Заметим, что доля D'1 узлов любого порядка i ^ 1 исходит из каждого из?) узлов первого порядка. Точно так же доля D~2 узлов любого порядка i ^ 2 исходит из каждого из D2 узлов порядка 2 и доля D~l узлов любого порядка, большего или равного г, исходит из каждого из D1 узлов порядка г.
Пусть теперь пи ..., п^ удовлетворяют (3.2.3). Покажем, как построить префиксный код с этими длинами/ исходя из полного дерева порядка п, равного наибольшему из nk, и полагая различные узлы в этом полном дереве концевыми узлами кодового дерева. Так что, когда по-
64
строение будет закончено, кодовое дерево будет вложено в полное дерево, как показано на рис. 3.2.3. Для простоты обозначений, предположим, что nk упорядочены в порядке возрастания < п2 <; ... < Выберем какой-либо узел порядка пх, допустим х1; в полном дереве в качестве первого концевого узла кодового дерева. Все узлы полного дерева любого порядка, большего или равного п1г еще можно использовать как концевые узлы кодового дерева, за исключением доли узлов, которые исходят из узла хх. Далее выберем какой-нибудь оставшийся узел порядка п2, например х2, в качестве следующего концевого узла кодового дерева. Все узлы полного дерева любого порядка, большего или равного пг, еще можно использовать как концевые узлы, за исключением доли D-r,< + D~n2 узлов, которые исходят из узлов хх и х2. Продолжая этот процесс, после образования k-ro концевого узла кодового дерева все узлы полного дерева любого порядка, большего или равного nh, все еще можно использовать, за исключением доли k __
2 D исходящей из хь ..., хк. Согласно (3.2.3) эта доля всегда ;= 1
строго меньше, чем 1 при k < К и, следовательно, всегда существует некоторый оставшийся узел, который может быть рассмотрен как следующий концевой узел.
Чтобы доказать вторую часть теоремы, заметим, что кодовое дерево, соответствующее любому префиксному коду, может быть вложено в. полное дерево, порядок которого равен наибольшей длине кодового слова. Из концевого узла порядка пк кодового дерева исходит доля D~nk концевых узлов полного дерева. Так как множества концевых узлов полного дерева, исходящие из различных концевых узлов кодового дерева, являются непересекающимися, то эти доли в сумме не могут превосходить 1, давая (3.2.3). |
Докажем теперь теорему о длинах кодовых слов однозначно декодируемых кодов, которая оправдает наше рассмотрение кодов, обладающих свойством префикса.
Теорема3.2.2110. Пусть задан код сдлинами кодовых слов пи ..., пя, с кодовым алфавитом из D символов. Если код однозначно декодируем, неравенство Крафта (3.2.3) удовлетворяется.
Доказательство. Пусть L — произвольное положительное целое число. Рассмотрим тождество
К. \ L, К. К. К.
=2 2 ••• 2 D_[%+%+'"+V- (3.2.4)
k=l / fc1==lfe.,= l kL= 1
Рис. 3.2.3. Двоичное кодовое дерево (сплошные линии), дополненное до полного дерева (пунктирные линии) порядка 3.
*> Эта теорема принадлежит Макмиллану (1956). Приведенное доказательство принадлежит Карушу (1961).
3 Зак. 2 10 65
Заметим, что в выражении, стоящем в правой части (3.2.4), различные слагаемые соответствуют каждой возможной последовательности из L кодовых слов. Более того, сумма + ... + nhL равна
общему числу кодовых букв, соответствующему последовательности кодовых слов. Следовательно, если через Лг- обозначить число последовательностей из L кодовых слов, имеющих общую длину г — число кодовых букв, то (3.2.4) можно переписать в виде
где птах является наибольшим из
Если код однозначно декодируем, то все последовательности кодовых слов из i кодовых букв являются различными и, следовательно, At < D1. Подставляя это неравенство в (3.2.5), получаем
Неравенство (3.2.7) справедливо для всех положительных целых чисел L; переходя к пределу при Lсо, получаем (3.2.3), что доказывает теорему. |
Так как длины кодовых слов любого однозначно декодируемого кода удовлетворяют (3.2.3) и так как можно построить префиксный код для любого множества длин, удовлетворяющих (3.2.3), то любой однозначно декодируемый код можно заменить на префиксный код без изменения длин кодовых слов. Таким образом, последующие теоремы относительно средней длины кодового слова приложимы как к однозначно декодируемым кодам, так и к подклассу префиксных кодов.
Теорема 3.3.1. При заданных конечном ансамбле источника U с энтропией Н (U) и кодовом алфавите из D символов можно так приписать кодовые слова буквам источника, что будет выполняться свойство префикса и средняя длина кодового слова я будет удовлетворять условию
