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

Для применения кода на практике желательно, чтобы кодовые слова были как можно короче. Однако чем слова короче, тем их запас меньше. В этом легко убедиться, посмотрев на изображение словарного универсума на рис.6.3. Если попытаться построитьпрефиксный код с очень короткими длинами кодовых слов, то можно потерпеть неудачу - кода с такими длинами слов может не быть. Например, нетрудно убедиться, что не существует префиксного кода с длинами слов 1, 1, 2. При необходимости построитьпрефиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной. К счастью, найдены необходимые и достаточные условия на длины кодовых слов для существования префиксного и любого однозначно декодируемого кода. Эти условия известны как теорема Крафта - Макмиллана. Необходимые и достаточные условия сформулируем в виде двух теорем.

Теорема (необходимые условия). Пусть - префиксный двоичный код с длинами кодовых слов . Тогда выполняется неравенство Крафта

( 6.3)

Доказательство. Рассмотрим, сколько слов длины может быть в префиксном коде. Максимальное число таких слов равно . В этом случае все кодовых слова имеют длину .

Для каждого кодового слова длины имеется слов длины , для которых данное слово является префиксом и по этой причине не является кодовым. Это следует из структуры словарного дерева (см. рис. 6.3). Множества и слов длины , для которых кодовые слова и являются префиксами, не пересекаются, так как в противном случае более короткое из этих слов было бы префиксом более длинного. Значит, если в префиксном коде имеется слов длины слов длины слов длины 1, то число слов длины удовлетворяет неравенству

( 6.4)

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

( 6.5)

Слагаемое вида , представляющее в неравенстве (6.5) кодовых слов длины , можно записать в виде суммы

С учетом такого представления неравенство (6.5) можно переписать следующим образом:

где - общее число слов префиксного кода. Теорема доказана.

Выполнение неравенства Крафта доказано для префиксного кода. Однако в 1956 году Макмиллан доказал более общую теорему, согласно которой неравенство Крафта выполняется и для любого однозначно декодируемого кода. Доказательство теоремы изложено в [29], [31].

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

Теорема (достаточные условия). Если положительные целые числа удовлетворяют неравенству Крафта

то существует префиксный код с длинами кодовых слов

Доказательство. Если среди чисел имеется ровно чисел, равных , то неравенство Крафта можно записать в виде

где - максимальное из данных чисел. Из справедливости этого неравенства следует, что верны неравенства (6.5) для всех , а следовательно, и неравенство (6.4).

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

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

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

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

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

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

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