НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

5. Еще о свойстве префикса и однозначной декодируемости

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

Рис. 9
Рис. 9

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

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

Рис. 10
Рис. 10

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

nk ≤ 2k. (1)

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

2k - 2k-1 n1 - 2k-2 n2 - ... - 2nk-1,

и потому

nk ≤ 2k - 2k-1 n1 - 2k-2 n2 - ... - 2nk-1 (2)

или иначе

2k-1 n1 + 2k-2 n2 + ... + 2nk-1 + nk ≤ 2k.

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

ki=1 ni2-i ≤ 1. (3)

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

Li=1 ni2-i ≤ 1. (4)

Если l1, l2, ..., lN - длины кодовых слов a1, а2, ..., aN, то неравенство (4) запишется в таком виде:

2-l1 + 2-l2 + ... + 2-lN ≤ 1. (5)

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

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

Рассуждаем так. Если среди чисел l1, l2, ..., lN имеется ровно ni чисел, равных i, то неравенство (5) можно переписать в виде (4), где L - максимальное из данных чисел. Из справедливости (4) подавно следует, что верны неравенства (3) для всех k ≤ L, а, следовательно, и неравенство (2).

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

Рис. 11
Рис. 11

Для построения нужного префиксного кода мы должны подходящим образом выбрать n1 слов длины 1, n2 слов длины 2, вообще nk слов длины k (l ≤ k ≤ L) или, иными словами, n1 концевых вершин на первом, n2 - на втором, ..., nk - на k-ом этаже.

Из неравенства (2) при k = l получаем n1 ≤ 2, т. е. требуемое число не превосходит общего числа вершин первого этажа. Значит, на этом этаже можно выбрать какие-то n1 вершин в качестве концевых (n1 равно 0, 1 или 2). Если это сделано, то из общего числа вершин второго этажа (их 22 = 4) для построения кода можно использовать лишь 4-2n1 (почему?). Однако нам хватит и этого числа вершин, так как из неравенства (2) при k = 2 вытекает

n2 ≤ 4 - 2n1.

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

n3 ≤ 23 - 4n1 - 2n2.

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

Если кодовый алфавит содержит d символов, то подобным же образом доказывается, что необходимым и достаточным условием для существования префиксного кода с длинами слов l1, l2, ..., lN является выполнение неравенства

d-l1 + d-l2 + d-lN ≤ 1. (6)

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

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru
Поможем с курсовой, контрольной, дипломной
1500+ квалифицированных специалистов готовы вам помочь