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

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

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

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

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

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

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

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

Код называется разделимым (или однозначно декодируемым), если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.

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

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

Введение

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

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

Теорема:

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

Ссылки

• Неравенство Крафта — Википедия
• ftp://remotesensing.ru/InfoTheory_lec05.pdf

Литература

• А.Шень "Программирование: теоремы и задачи".