5. ЕЩЕ О СВОЙСТВЕ ПРЕФИКСА И ОДНОЗНАЧНОЙ ДЕКОДИРУЕЛЮСТИ

Возникает вопрос: каковы возможные длины кодовых слов однозначно декодируемого, в частности, пре­фиксного кода? Понятно, например, что не существует дво­ичного префиксного кода с длинами кодовых слов 1, 1,2. Несколько труднее ответить на такой вопрос: существует ли префиксный двоичный код, содержащий 100 слов с дли­нами от 1 до 100? Оказывается, существует. Кодовое дерево Для требуемого кода, содержащее 100 «этажей», изображено на рис. 9 (пунктиром отмечены пропущенные этажи).Вопросы такого рода можно было бы продолжить, отве­чая на них в каждом конкретном случае. Но на самом деле можно установить общие условия (необходимые и достаточ­ные) для существования префиксного и вообще произволь ного однозначно декодируемого кода.

Пусть У={ах, а2, ... , адг} — префиксный двоичный код, дерево которого схематически изображено на рис. 10

 

 

Пусть пк — число кодовых слов длины к (пк совпадает с числом концевых вершин 6-го этажа). Конечно, справедливо

 

Деля обе части последнего неравенства на 2й, получаем:

 

неравенство

 

 

так как 2й — максимально возможное число вершин нл к-м этаже двоичного дерева. Однако в случае префиксного кода для пк можно получить гораздо более точную оценку, чем (1). В самом деле, если пи ... , пк_1 — число конце­вых вершин 1; 2; ... ; к—1 этажей дерева, то число всех вершин 6-го этажа кодового дерева равно и потому или иначе

Неравенство (3) верно для любого к^Ь (Ь —- макси­мальная длина кодовых слов), в частности

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

Оказывается, что неравенство (5), называемое в теории кодирования неравенством Крафта, является также доста­точным условием того, чтобы существовал префиксный код с длинами кодовых слов /2, ... , /Л,.

Рассуждаем так. Если среди чисел /(, /2, ... , имеется ровно П{ чисел, равных I, то неравенство (5) можно перепи­сать в виде (4), где Ь — максимальное из данных чисел. Из справедливости (4) подавно следует, что верны неравенства (3) для всех       а, следовательно, и неравенство (2).

Обратимся к рис. 11, на котором изображено дерево «вы­соты» Ь, имеющее наибольшее число вершин и ветвей (ре­бер). Все концевые вершины (их 21) такого дерева находят­ся на последнем 1-ом этаже, а из каждой вершины промежу­точного этажа исходят ровно две вэтви.

 

Если к, и, ■■■ . 'л — длины кодовых слов аи а2, ... , аК, ■го неравенство (4) запишется в таком виде:

 

Для построения нужного префиксного кода мы должны подходящим образом выбрать пг слов длины 1, п2 слов дли­ны 2, вообще пк слов длины к (1         или, иными слова­ми, щ концевых вершин на первом, п2 — на втором, ... , пк — на й-ом этаже.

Из неравенства (2) при к= 1 получаем «1<2, т. е. требуй мое число не превосходит общего числа вершин первого этажа. Значит, на этом этаже можно выбрать какие-то щ вершин в качестве концевых (п! равно 0, 1 или 2). Если это сделано, то из общего числа вершин второго этажа (их 2В=4) для построения кода можно использовать лишь 4—2я* (почему?). Однако нам хватит и этого числа вер­шин, так как из неравенства (2) при к=2 вытекает ,1

Правая часть его вновь совпадает с допустимым для по­строения префиксного кода числом вершин третьего этажа, если на первых двух этажах уже выбраны Пг и п2 концевых вершин. Значит, снова можно выбрать п3 концевых вершин на третьем этаже. Продолжая этот процесс вплоть до к—Ь, мы и получим требуемый код.

Если кодовый алфавит содержит й. символов, то подоб-| ным же образом доказывается, что необходимым и достаточ-1 ным условием для существования префиксного кода с дли-1 нами слов 1и        1ц является выполнение неравенства

 

 

Оказывается, неравенству (6) обязаны удовлетворять и длины кодовых слов произвольного однозначно декодируе­мого кода. Поэтому, если существует однозначно декодируемый код с длинами слов /2      то существует и

префиксный код с теми же длинами слов. Префиксными же кодами пользоваться удобнее по причине, указанной в до-1 полнении 11 к § 4.

Задачи и дополнения

1. Каково минимальное число слов полного двоичногоМ префиксного кода с максимальной длиной Какими будут длины ко- Ц довых слов такого минимального кода? (Ответы на эти вопросы подска-1 бывает рис. 9.)

Решить те же вопросы в случае й-ичного кода.

 

Аналогично, при к=3 имеем неравенство:

 

2. Доказать, что префиксный код является полным тогда и только тогда, когда в неравенстве Крафта достигается равенство:

 

Указание. То, что из предыдущего равенства вытекает пол­нота, очевидно. Для доказательства обратного утверждения следует предположить, что неравенство (6) строгое. Тогда из него выводится

 

 

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

3. Утверждение предыдущей задачи допускает следующую забав­ную интерпретацию, являющуюся одновременно и его доказательством (он заимствована из книги [6]).

Рассмотрим дерево, соответствующее полному префиксному коду. Представим себе, что на это дерево взбирается обезьяна. Начав с корня, она наугад выбирает любую из й исходящих из него ветвей; вероятность такого выбора равна \!й. Добравшись до очередной развилки, обезьяна снова наугад выбирает некоторую ветвь с вероятностью Мй (напомним, что из каждой промежуточной вершины дерева полного кода исходит ровно (I ветвей). Тогда вероятность того, что обезьяна достигнет какой- то определенной концевой вершины, находящейся на высоте к, равна (1 Если таких вершин я*, то с вероятностью      обезьяна оста-

чпвится на высоте к. На какой-то высоте от 1 до С обезьяне придется остановиться (вероятность этого равна 1). Поэтому

(В приведенном рассуждении мы использовали правила сложения и умножения вероятностей.)

 

 

4. Префиксный код с данными длинами кодовых слов может быть построен далеко не единственным способом. Пусть й-нчный префиксный код (не обязательно полный) имеет п/, слов длины к (1 </г«гХ). Доказать, что число различных таких кодов с фиксированными Ь н равно про­изведению

где =С|— число сочетаний из « элементов по /.

 

чисе'10 считать' что           •           Рассмотрим последовательность

 

Например, число двоичных префиксных кодов с 1=4, П|=0, я2= 1, «8=2, п. = 4 равно

 

 

5. Выше было доказано, что если для чисел /2, . . ., /д? выполня­ется неравенство Крафта, то существует префиксный код с длинами 'ь • . ., /дг. Найти этот код можно, строя этаж за этажом его кодо­вое дерево. Другой более удобный метод решения этой задачи был при­думан Шенноном, н (применительно к двоичным кодам) он состоит в следующем.

итогов же неравенство

Пусть числа Ц, и, > , 1кг удовлетворяют неравенствуЗаметим, что все эти числа заключены в пределах 0<</у-<1, поэтому Каждое из них может быть представлено двоичной дробью вида ' п

V         где каждое есть 0 или 1. При этом из (7) можно заклю-

чить, что все эти дроби конечны, и двоичная запись для д: имеет не бо- лее /1 значащих цифр. Таким образом, любое число ду однозначно представимо в виде:

где всякое сц есть 0 или 1. Следовательно, каждому однозначно от­вечает слово Ч/= с1уС2/- . . . С[ I длины /у. Рассмотрим код V" {VI, о2, ..

..., Цд/}. Покажем, что он обладает свойством префикса. Пусть V^ н двг

слова (&>/). Тогда, согласно (7), дк—ду->2 /, а это означает, что (,-й символ слова V/ не совпадает с 1]-и символом слова Следовательно, V/ не является началом откуда и вытекает префиксность кода У.

Разъясним сказанное на примере. Построим префиксный код с дли­нами слов /1=1, /2=1'з=3, /4=4. В этом случае

 

 

 

 

 

 

 

 

Двоичная запись этих чисел с нужным числом I,- знаков следующая;

 

 

 

 

 

В результате мы получим искомый код:

 

 

 

 

 

 6. Используя метод Ше. лона, найти префиксные коды с указанными Ниже длинами слов:

 

 

 

 

 

 

 

 

 Построить кодовые деревья для полученных кодов. Определить, какой Из этих кодов является полным.