Изменения
Нет описания правки
При необходимости построить префиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной.
Но неравенство Крафта даёт необходимое и достаточное условие существования префиксных и любых '''[[Кодирование информации | однозначно декодируемых кодов]]''', обладающих заданным набором длин кодовых слов.
{{Теорема
|about=неравенство Крафта (англ. Kraft's inequality)
|statement=
Для любого '''[[Кодирование информации | префиксного кода]]''' <tex>C</tex>, отображающего произвольный алфавит <tex>A</tex> на двоичный алфавит <tex> \{0,1\} </tex> , длины кодовых слов должны удовлетворять неравенству:
<center><tex> \sum\limits_{i = 1}^{I} 2^{-l_i} \leqslant 1 , </tex></center>
*любому кодовому слову <tex>C_j</tex> сопоставлен свой отрезок <tex>M_{C_j}</tex> (Например, кодовому слову <tex>1011</tex> соответствует отрезок <tex>M_{1011}</tex>);
*длина отрезка <tex>M_{C_i}</tex> равна <tex>2^{-l_i}</tex> (Например, <tex>M_0</tex> имеет длину <tex dpi = 140> \frac12</tex>, а <tex>M_{00}</tex> соответственно <tex dpi = 140> \frac14</tex>);
*Если кодовое слово <tex>x</tex> является '''[[Основные определения, связанные со строками | префиксом]]''' кодового слова <tex>y</tex>, то отрезок <tex>M_x</tex> содержит <tex>M_y</tex> (Например, кодовое слово <tex>01</tex> является '''[[Основные определения, связанные со строками | префиксом]]''' <tex>0111</tex>, а отрезок<tex>M_{01}</tex> содержит <tex>M_{0111}</tex>, это его самая правая четверть);
Рассмотрим префиксный код <tex>C</tex>: так как ни одно из кодовых слов не является '''[[Основные определения, связанные со строками | префиксом]]''' никакого другого кодового слова, то никакие два отрезка не пересекаются.
Если на отрезке <tex>[0;1]</tex> выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет <tex>1</tex>, то есть <tex> \sum\limits_{i = 1}^{I} M_{C_i} \leqslant 1</tex>.
