Изменения

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

Необходимое и достаточное условие существования префиксного кода в Пусть <tex>r\Sigma</tex>-ичном дереве для источника с — [[Основные определения, связанные со строками|алфавитомалфавит]] <tex>S</tex> из <tex>n</tex> [[Основные определения, связанные со строками|символов]] , кодовые слова которого имеют длины <tex>s_il_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>, где <tex>i\in \left [ 1, n \right ]</tex>, кодовые слова которого имеют длины .  Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n Sigma</tex>, состоит в выполнении неравенства:

Неравенство Крафта легко доказать с помощью Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева декодирования, существование рёбра которого следует из существования префиксного кодасоответствуют символам алфавита, а листья соответствующим кодам. Будем рассуждать Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]].  '''Необходимость:'''

Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>.  База: Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника.  Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</tex>. Для данного дерева максимальной высоты <tex>n</tex> ребра из первой вершины ведут к двум поддеревьям, высоты которых не превышают <tex>n - 1</tex>; для этих поддеревьев имеем неравенства <tex>K_1 \leqslant 1</tex> и <tex>K_2 \leqslant 1</tex>, где <tex>K_1, K_2</tex> — значения соответствующих им сумм. Каждая длина <tex>l_i</tex> в поддереве увеличивается на <tex>1</tex>, когда поддерево присоединяется к основному дереву, поэтому возникает дополнительный множитель <tex>\dfrac{1}{2}</tex>. Таким образом, имеем <tex>\dfrac{1}{2} K_1 + \dfrac{1}{2} K_2 \leqslant 1</tex>.