ЕЩЕ О СВОЙСТВЕ ПРЕФИКСА И ОДНОЗНАЧНОЙ ДЕКОДИРУЕМОСТИ

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

Вопросы такого рода можно было бы продолжить, отве­чая на них в каждом конкретном случае. Но на самом деле можно установить общие условия (необходимые и достаточные) для существования префиксного и вообще произволь­ного однозначно декодируемого кода.

Пусть— префиксный двоичный

код, дерево которого схематически изображено на рис. 10.

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

так как 2^к — максимально возможное число вершин h.j k-u этаже двоичного дерева. Однако в случае префиксного кода для п_к можно получить гораздо более точную оценку, чем (1). В самом деле, если п_и п₂, ... ♦ n_h__t — число конце­вых вершин 1; 2; ... ; k—1 этажей дерева, то число всех вершин k-ro этажа кодового дерева равно

и потому

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

или иначе

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

Если /х, h, .... fa — длины кодовых слов a_lf а₂, ... , a_N, то неравенство (4) запишется в таком виде:

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

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

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

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

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

Из неравенства (2) при k= \ получаем «i<2, т. е. требуй мое число не превосходит общего числа вершин первого этажа. Значит, на этом этаже можно выбрать какие-то я* вершин в качестве концевых (/ii равно О, I или 2). Если это сделано, то из общего числа вершин второго этажа (их 2®=4) для построения кода можно использовать лишь 4—2л_г (почему?). Однако нам хватит и этого числа вер- шин, так как из неравенства (2) при k=2 вытекает

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

Правая часть его вновь совпадает с допустимым для по­строения префиксного кода числом вершин третьего этажа, если на первых двух этажах уже выбраны п_х и п₂ концевых вершин. Значит, снова можно выбрать п_а концевых вершин на третьем этаже. Продолжая этот процесс вплоть до k=L, мы и получим требуемый код.

Если кодовый алфавит содержит d символов, то подоб­ным же образом доказывается, что необходимым и достаточ­ным условием для существования префиксного кода с дли­нами слов /f, /s, ... , In является выполнение неравенства

Оказывается, неравенству (6) обязаны удовлетворять и длины кодовых слов произвольного однозначно декодируе­мого кода. Поэтому, если существует однозначно декоди­руемый код с длинами слов U, U................... l_N, то существует и префиксный код с теми же длинами слов. Префиксными же кодами пользоваться удобнее по причине, указанной в до­полнении 11 к § 4.

Предлагаю ознакомиться с аналогичными статьями: