4.5. Неравенство Крафта

Рассматриваемое ниже неравенство Крафта дает условие существования мгновенных кодов; оно показывает, для каких длин кодовых слов существует мгновенный код, но не показывает, как его строить.

Теорема. Необходимое и достаточное условие существования мгновенного кода для источника с алфавитом из символов кодовые слова которого имеют длины состоит в выполнении неравенства

где основание (число символов) в кодовом алфавите.

Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из возможности мгновенного декодирования. Будем рассуждать по индукции. Для простоты рассмотрим сначала случай двоичного алфавита (рис. 4.5.1). Если максимальная длина пути на дереве равна 1, то на нем есть одно или два ребра длины 1. Таким образом, либо 1/2 — для одного символа источника, либо для двух символов источника. Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше Для данного дерева максимальной длины ребра из первой вершины ведут к двум поддеревьям, длины которых не превышают для этих поддеревьев имеем неравенства где значения соответствующих им сумм. Каждая длина в поддереве увеличивается на 1, когда поддерево присоединяется к

основному дереву, поэтому возникает дополнительный множитель 1/2. Таким образом, имеем

В случае произвольного недвоичного основания имеется не более ребер, исходящих из каждой вершины, т. е. не более поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель Отсюда снова следует утверждение теоремы.

Рис. 4.5.1. Доказательство неравенства Крафта: а — верно для дерева длины 1; предположим, что верно для длины верно для дерева длииы

Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то 1. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Если, однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.

Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является мгновенным, однако в этом случае сущест в уют коды с теми же являющимися мгновенными.

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

Покажем теперь, почему коды с запятой удовлетворяют неравенству Крафта. Код с запятой, алфавит которого состоит из символов основание), имеет один фиксированный символ, называемый запятой; он используется для обозначения конца всех кодовых слов, за исключением самых длинных; конец слов максимальной длины декодер узнает непосредственно по их длине.

Имеется одно слово — сама запятая — длины 1. Число слов Длины 2 равно длины длины наконец, число слов длины равно Объединяя агаемые всех слов одинаковой длины, можно записать сумму Крафта в виде

Сумма последних двух членов равна

Производя раз аналогичное преобразование, получаем, что ряд сводится к выражению — так что для кодов с запятой неравенство Крафта переходит в равенство.

В следующих двух примерах предполагается, что заданы только длины кодовых слов, поскольку в теорему входят только они, а не сами слова. Если длины двоичных кодовых слов равны 1, 3, 3 и 3, то сумма Крафта равна и мгновенный код с такими длинами существует. Одно из слов длины 3 может быть сокращено до слова длины 2. Если, однако, длины равны 1, 2, 2 и 3, то сумма равна и мгновенный код с такими длинами не существует.

Применим теорему еще к одному примеру. Предположим, что и требуется получить слова с длинами 1, 2, 2, 2, 2, 2, 3, 3, 3 и 3. Левая часть неравенства Крафта равна , так что найти мгновенный код с такими параметрами невозможно. Если удалить последнее кодовое слово длины 3, то сумма в точности равна 1, и такой код можно найти. Для нахождения мгновенного кода с такими длинами положим При таком построении непосредственно просматривалось дерево декодирования (рис. 4.5.2) и троичные (основание 3) численные эквиваленты кодов систематически увеличивались с тем, чтобы легко было следить за рассуждениями. Читатель должен. иметь в виду, что 0, 1 и 2 — это произвольные символы, а не числа. Поэтому произвольная перестановка трех символов переводит код в практически ему эквивалентный.

Задачи

4.5.1. Удовлетворяет ли неравенству Крафта код с запятой с (имеющей бесконечную длину)? Используйте

4.5.2. Обобщите задачу 4.5.1 на произвольное основание

Рис. 4.5.2. Дерево декодирования