Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
{!10, 11, 100, 00, 10);
{100, 001, 101, 1101, 11011}.
11. Префиксные коды иногда называют мгновенными (или мгновенно декодируемыми), поскольку конец кодового слова опознается сразу, как только мы достигаем конечного символа слова при чтении кодовой последовательности. В зтом состоит преимущество префиксных кодов перед другими однозначно декодируемыми кодами, для которых конец каждого кодового слова, как мы видели, может быть найден лишь после анализа одного или нескольких последующих символов, а иногда и всей кодовой последовательности. Таким образом, в отличие от префиксного кода декодирование здесь осуществляется с запаздыванием по отношению к передаче сообщения.
5. ЕЩЕ О СВОЙСТВЕ ПРЕФИКСА
И ОДНОЗНАЧНОЙ ДЕКОДИРУЕМОСТИ
Возникает вопрос: каковы возможные длины кодовых слов однозначно декодируемого, в частности, префиксного кода? Понятно, например, что не существует двоичного префиксного кода с длинами кодовых слов 1, 1,2. Несколько труднее ответить на такой вопрос: существует ли префиксный двоичный код, содержащий 100 слов с длинами от 1 до 100? Оказывается, существует. Кодовое дерево для требуемого кода, содержащее 100 «этажей», изображено на рис. 9 (пунктиром отмечены пропущенные этажи).
Вопросы такого рода можно было бы продолжить, отвечая на них в каждом конкретном случае. Но на самом деле можно установить общие условия (необходимые и достаточ-
27 ные) для существования префиксного и вообще произвольного однозначно декодируемого кода.
Пусть V= {ol, Cl2..... aN) — префиксный двоичный
код, дерево которого схематически изображено на рис. !0.
dflf-T aN
/
Q ? nV V Ы
\ /
"4
Л/ \
VV
Рис. 10.
Пусть nk — число кодовых слов длины k (nh совпадает с числом концевых вершин k-ro этажа). Конечно, справедливо неравенство
я* <2*. (1)
так как 2к — максимально возможное число вершин на к-м этаже двоичного дерева. Однако в случае префиксного кода для tih можно получить гораздо более точную оценку, чем (1). В самом деле, если пъ п2, ... , пк_х — число концевых вершин 1; 2; ... ; k—1 этажей дерева, то число всех вершин k-ro этажа кодового дерева равно
2ft—2Jfe-1Zi1—2ft- 2H2-. .. — 2п,_1(
и потому
nk^2h—2il-1nl — 2k'2ni—.. . —2пк_т (2)
или иначе
2**4 + 2и-гПі + . .. + 2пк_і + пк < 2й.
Деля обе части последнего неравенства на 2к, получаем:
к
(3)
і = 1
28 Неравенство (3) верно для любого k^JL (L мальная длина кодовых слов), в частности
E п,2-'<1.
макси•
(4)
Если li, I2...../.у — длины кодовых слов аи а2, ... , aN,
то неравенство (4) запишется в таком виде:
2-'» + 2-'«+. . .+2"'л'< 1. (5)
Это и есть то условие, которому обязаны удовлетворять длины кодовых слов двоичного префиксного кода.
Оказывается, что неравенство (5), называемое в теории кодирования неравенством Крафта, является также достаточным условием того, чтобы существовал префиксный код с длинами кодовых слов I1, I2, ... , lN.
Рассуждаем так. Если среди чисел li, I2, ... , In имеется ровно tit чисел, равных і, то неравенство (5) можно переписать в виде (4), где L — максимальное из данных чисел, Из
1» <? 9 Ч
^ / \і \ / \/ V
* ? H ? Ч і / - ^ / *
t Ч Г t
/ \
У
P щ 9 <t P %
\ / W \ /
H і \
л / »
,.W \ I
* Ї Ї
JiJ
Рис. 11.
справедливости (4) подавно следует, что верны неравенства (3) для всех /г<Х, а, следовательно, и неравенство (2).
Обратимся к рис. 11, на котором изображено дерево «высоты» L, имеющее наибольшее число вершин и ветвей (ребер). Все концевые вершины (их 21) такого дерева находятся на последнем L-ом этаже, а из каждой вершины промежуточного этажа исходят ровно две в.ггви.
Для построения нужного префиксного кода мы должны подходящим образом выбрать H1 слов длины 1, п2 слов длины 2, вообще nh слов длины k (l^k^L) или, иными словами, щ концевых вершин на первом, пг — на втором, ... , nh — на /е-ом этаже.
29 Из неравенства (2) при k=l получаем /1^2, т. е. требуемое число не превосходит общего числа вершин первого этажа. Значит, на этом этаже можно выбрать какие-то rii вершин в качестве концевых (/Z1 равно 0, 1 или 2). Если это сделано, то из общего числа вершин второго этажа (их 22=4) для построения кода можно использовать лишь 4—2/J1 (почему?). Однако нам хватит и этого числа вершин, так как из неравенства (2) при /е = 2 вытекает
/г2<4—2гц.
Аналогично, при /е=3 имеем неравенство: п3-<23—4/ix—2/ia.
Правая часть его вновь совпадает с допустимым для построения префиксного кода числом вершин третьего этажа, если на первых двух этажах уже выбраны /Z1 и /г2 концевых вершин. Значит, снова можно выбрать па концевых вершин на третьем этаже. Продолжая этот процесс вплоть до k=L, мы и получим требуемый код.
Если кодовый алфавит содержит d символов, то подобным же образом доказывается, что необходимым и достаточным условием для существования префиксного кода с длинами слов I1, I2, ... , In является выполнение неравенства
d-'i + d-'' +...1. (6)
Оказывается, неравенству (6) обязаны удовлетворять и длины кодовых слов произвольного однозначно декодируемого кода. Поэтому, если существует однозначно декодируемый код с длинами слов I1, I2, ... , lN, то существует и префиксный код с теми же длинами слов. Префиксными же кодами пользоваться удобнее по причине, указанной в дополнении 11 к § 4.
