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

Теорема 1. Если целые числа n₁, n₂, …, n_k удовлетворяют неравенству

, (3.1)

существует префиксный код с алфавитом объемом m, длины кодовых слов которого равны этим числам. И обратно, длины кодовых слов любого префиксного кода отвечают неравенству Крафта (3.1).

Доказательство

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

Упорядочим длины n_i в порядке возрастания ( ).

Выберем какой-либо узел x₁ порядка n₁ в полном кодовом дереве в качестве концевого. Это запретит использование части узлов n₁-го и более высокого порядка для выбора в качестве концевых для других кодовых слов.

Среди тех узлов, которые еще можно использовать в качестве концевых, выберем узел x₂ порядка n₂ в качестве концевого. Это запретит использование еще части узлов n₂-го и более высокого порядка для выбора в качестве концевых для других кодовых слов и т.д.

Сумма на j-м этапе <1 и это значит, что для следующего i+1-го кодового слова еще есть возможность выбора узла.

Запрещенные к использованию узлы не пересекаются. Следовательно, общая доля запрещенных узлов равна сумме долей, запрещенных к использованию уже выбранными концевыми узлами. Эта доля равна по предположению . А это означает, что остались некоторые узлы более высокого порядка, разрешенные к использованию в качестве концевых.

Для этого мы расположили n в порядке возрастания. Для пояснения нужно обратиться к кодовому дереву (рис.3.2).

Для доказательства второй части теоремы о том, что длины любого префиксного кода отвечают неравенству Крафта (3.1), заметим, что префиксному коду соответствует определенный набор концевых узлов, каждый из которых закрывает долю узлов того же и более высокого порядка для использования в качестве концевых. Эти доли не пересекаются, следовательно, их сумма не может превышать 1. Отсюда , что и требовалось доказать.

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

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

Теорема 2.

Формулировка. Пусть задан код с длинами кодовых слов n₁, n₂, … , n_k и с алфавитом объема m. Если код однозначно декодируем, неравенство Крафта удовлетворяется.

Доказательство.

Пусть z – произвольное положительное число.

Рассмотрим тождество:

. (3.2)

Заметим, что можно понимать как сумму длин z кодовых слов. Обозначим эту сумму через j (j= ), а количество комбинаций, дающих одинаковую сумму длин A_j . Тогда (3.2) можно записать в виде: .

Если код однозначно декодируем, то все последовательности кодовых слов с суммарной длиной j кодовых букв (букв вторичного алфавита) являются различными. Поэтому A_j <=m^j , так как m^j – общее число всевозможных комбинаций из m букв по j. Из этого следует:

;

.

Поскольку z – произвольное число, устремим его в бесконечность:

, что можно доказать, используя правило Лопиталя.

Отсюда следует, что − неравенство Крафта.

Согласно теореме 1 существует префиксный код с теми же n₁, n₂, … ,n_k . Поэтому все результаты, полученные для префиксных кодов относительно средней длины кодового слова n_ср , распространяются и на все однозначно декодируемые коды.

Теорема 2 доказана.