Изменения
Нет описания правки
Для любого префиксного кода <tex>C</tex>, отображающего произвольный алфавит <tex>A</tex> на двоичный алфавит <tex> \{0,1\} </tex> , длины кодовых слов должны удовлетворять неравенству:
<center><tex> \sum\limits_{i = 1}^{I} 2^{-l_i} \le leqslant 1 , </tex></center>
где <tex>|A| = I</tex> , а <tex>l_i</tex> {{---}} длины кодовых слов.
Рассмотрим префиксный код <tex>C</tex>: так как ни одно из кодовых слов не является префиксом никакого другого кодового слова, то никакие два отрезка не пересекаются.
Если на отрезке <tex>[0;1]</tex> выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет <tex>1</tex>, то есть <tex> \sum\limits_{i = 1}^{I} M_{C_i} \le leqslant 1</tex>.
Отсюда следует, что <tex>\sum\limits_{i = 1}^{I} M_{C_i} = \sum\limits_{i = 1}^{I} 2^{-l_i} \le leqslant 1</tex>.
}}
Можно обобщить неравенство Крафта для случаев, когда кодирующим алфавитом является k-ичный. В доказательстве изменятся некоторые пункты:
*отрезок <tex>[0;1]</tex> придется делить не на <tex>2</tex>, а на <tex>k</tex> равных частей;
*соответственно неравенство примет вид: <tex>\sum\limits_{i = 1}^{I} k^{-l_i} \le leqslant 1 </tex>.
== Ссылки ==
