|
|
| Строка 1: |
Строка 1: |
| − | == Предварительные определения ==
| |
| − | {{Определение
| |
| − | |definition=
| |
| − | Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом '''(англ. ''encoded alphabet'') и '''кодирующим алфавитом '''(англ. ''encoding alphabet''). Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}
| |
| − | В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит (англ. ''binary alphabet'').
| |
| − |
| |
| − | {{Определение
| |
| − | |definition=
| |
| − | '''Кодом '''(англ. ''code'') для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}
| |
| − |
| |
| − |
| |
| − | == Неравенство Крафта ==
| |
| | {{Теорема | | {{Теорема |
| | |statement= | | |statement= |
Версия 23:14, 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].
Источники информации
