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

Материал из Викиконспекты
Перейти к: навигация, поиск

При необходимости построить префиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной. Но неравенство Крафта даёт необходимое и достаточное условие существования префиксных и любых однозначно декодируемых кодов, обладающих заданным набором длин кодовых слов.

Теорема (неравенство Крафта (англ. Kraft's inequality)):
Для любого префиксного кода [math]C[/math], отображающего произвольный алфавит [math]A[/math] на двоичный алфавит [math] \{0,1\} [/math] , длины кодовых слов должны удовлетворять неравенству:
[math] \sum\limits_{i = 1}^{I} 2^{-l_i} \leqslant 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} \leqslant 1[/math].

Отсюда следует, что [math]\sum\limits_{i = 1}^{I} M_{C_i} = \sum\limits_{i = 1}^{I} 2^{-l_i} \leqslant 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} \leqslant 1 [/math].

Источники информации