Теорема 1. Если целые числа n1, n2, …, nk удовлетворяют неравенству
, (3.1)
существует префиксный код с алфавитом объемом m, длины кодовых слов которого равны этим числам. И обратно, длины кодовых слов любого префиксного кода отвечают неравенству Крафта (3.1).
Доказательство
Предположим, что неравенство Крафта выполняется. Построим соответствующий префиксный код (первая часть теоремы).
Упорядочим длины ni в порядке возрастания ( ).
Выберем какой-либо узел x1 порядка n1 в полном кодовом дереве в качестве концевого. Это запретит использование части узлов n1-го и более высокого порядка для выбора в качестве концевых для других кодовых слов.
Среди тех узлов, которые еще можно использовать в качестве концевых, выберем узел x2 порядка n2 в качестве концевого. Это запретит использование еще части узлов n2-го и более высокого порядка для выбора в качестве концевых для других кодовых слов и т.д.
Сумма на j-м этапе <1 и это значит, что для следующего i+1-го кодового слова еще есть возможность выбора узла.
Запрещенные к использованию узлы не пересекаются. Следовательно, общая доля запрещенных узлов равна сумме долей, запрещенных к использованию уже выбранными концевыми узлами. Эта доля равна по предположению . А это означает, что остались некоторые узлы более высокого порядка, разрешенные к использованию в качестве концевых.
Для этого мы расположили n в порядке возрастания. Для пояснения нужно обратиться к кодовому дереву (рис.3.2).
Для доказательства второй части теоремы о том, что длины любого префиксного кода отвечают неравенству Крафта (3.1), заметим, что префиксному коду соответствует определенный набор концевых узлов, каждый из которых закрывает долю узлов того же и более высокого порядка для использования в качестве концевых. Эти доли не пересекаются, следовательно, их сумма не может превышать 1. Отсюда , что и требовалось доказать.