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

Предварительные определения

Определение:

Пусть заданы два произвольных конечных множества, которые называются, соответственно, кодируемым алфавитом и кодирующим алфавитом. Их элементы называются символами, а строки (последовательности конечной длины) символов — словами. Длина слова — это число символов, из которого оно состоит.

В качестве кодирующего алфавита часто рассматривается множество [math]\{0, 1\}[/math] — так называемый двоичный или бинарный алфавит.

Определение:

Кодом для алфавита [math]A[/math] называется функция [math]C[/math], которая для каждого символа [math]x[/math] из [math]A[/math] указывает слово [math]C(x)[/math], кодирующее этот символ.

Определение:

Префиксным кодом называется код, в котором ни одно из кодовых слов не является префиксом никакого другого кодового слова.

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

Теорема:

Для любого префиксного кода [math]C[/math], отображающего произвольный алфавит [math]A[/math] на двоичный алфавит [math] \{0,1\} [/math] , длины кодовых слов должны удовлетворять неравенству: [math] \sum\limits_{i = 1}^{I} 2^{-l_i} \le 1 , [/math] где [math]|A| = I[/math] , а [math]l_i[/math] — длины кодовых слов.

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

[math]\triangleright[/math]

Рассмотрим отрезок [math][0;1][/math] на числовой прямой. Разделим его пополам, причем левую половину обозначим [math]M_0[/math], а правую [math]M_1[/math]. Затем поделим [math]M_0[/math] пополам и обозначим его левую половину [math]M_{00}[/math], а правую [math]M_{01}[/math], и, проделав то же самое с [math]M_1[/math], получим [math]M_{10}[/math], а левую [math]M_{11}[/math]. Будем выполнять эти действия, пока длина индекса полученного отрезка [math]M_j[/math] не превосходит [math]max(l_1, l_2,\ldots,l_I)[/math]. Заметим, что: любому кодовому слову [math]C_j[/math] сопоставлен свой отрезок [math]M_{C_j}[/math] (Например, кодовому слову [math]1011[/math] соответствует отрезок [math]M_{1011}[/math]); длина отрезка [math]M_{C_i}[/math] равна [math]2^{-l_i}[/math] (Например, [math]M_0[/math] имеет длину [math]\frac12[/math], а [math]M_{00}[/math] соответственно [math]\frac14[/math]); Если кодовое слово [math]x[/math] является префиксом кодового слова [math]y[/math], то отрезок [math]M_x[/math] содержит [math]M_y[/math] (Например, кодовое слово [math]01[/math] является префиксом [math]0111[/math], а отрезок[math]M_{01}[/math] содержит [math]M_{0111}[/math], это его самая правая четверть); Рассмотрим префиксный код [math]C[/math]: так как ни одно из кодовых слов не является префиксом никакого другого кодового слова, то никакие два отрезка не пересекаются. Если на отрезке [math][0;1][/math] выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет [math]1[/math], то есть [math] \sum\limits_{i = 1}^{I} M_{C_i} \le 1[/math]. Отсюда следует, что [math]\sum\limits_{i = 1}^{I} M_{C_i} = \sum\limits_{i = 1}^{I} 2^{-l_i} \le 1[/math].

[math]\triangleleft[/math]

Следствие

Можно обобщить неравенство Крафта для случаев, когда кодирующим алфавитом является k-ичный. В доказательстве изменятся некоторые пункты:

• отрезок [math][0;1][/math] придется делить не на [math]2[/math], а на [math]k[/math] равных частей;
• соответственно неравенство примет вид: [math]\sum\limits_{i = 1}^{I} k^{-l_i} \le 1 [/math].

Ссылки

• Неравенство Крафта — Википедия
• Теория информации

Литература

• А.Шень "Программирование: теоремы и задачи"(Москва МЦНМО 2011 стр. 208).