Неравенство Крафта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 19: Строка 19:
 
*любому кодовому слову <tex>C_j</tex> сопоставлен свой отрезок <tex>M_{C_j}</tex> (Например, кодовому слову <tex>1011</tex> соответствует отрезок <tex>M_{1011}</tex>);
 
*любому кодовому слову <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>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>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>C</tex>: так как ни одно из кодовых слов не является '''[[Основные определения, связанные со строками | префиксом]]''' никакого другого кодового слова, то никакие два отрезка не пересекаются.
  
 
Если на отрезке <tex>[0;1]</tex> выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет <tex>1</tex>, то есть <tex> \sum\limits_{i = 1}^{I} M_{C_i} \leqslant 1</tex>.
 
Если на отрезке <tex>[0;1]</tex> выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет <tex>1</tex>, то есть <tex> \sum\limits_{i = 1}^{I} M_{C_i} \leqslant 1</tex>.

Версия 23:18, 13 января 2015

Теорема:
Для любого префиксного кода [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].

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