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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Необходимые определения)
Строка 1: Строка 1:
 
== Необходимые определения ==
 
== Необходимые определения ==
 +
{{Определение
 +
|definition=
 +
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}
 +
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.
 +
 +
{{Определение
 +
|definition=
 +
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}
 
{{Определение
 
{{Определение
|definition='''''Алфавит''''' {{---}} конечное множество.
+
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код..
}}
 
{{Определение
 
|definition='''''Символами''''' или '''''буквами''''' называются элементы этого алфавита.
 
}}
 
{{Определение
 
|definition='''''Кодовым словом''''' или просто '''''кодом''''' символа называется двоичное слово (Двоичное слово {{---}} конечная последовательность нулей и единиц).
 
}}
 
{{Определение
 
|definition='''''Кодом''''' для алфавита <tex>A</tex> называется функция (таблица) <tex>\alpha</tex>, которая для каждого символа <tex>a</tex> из <tex>A</tex> указывает двоичное слово <tex>\alpha(a)</tex>. Не требуется, чтобы коды всех символов имели равные длины.
 
}}
 
{{Определение
 
|definition=Хороший код должен позволять декодирование (восстановление последовательности символов по ее коду). Пусть фиксирован алфавит <tex>A</tex> и код <tex>\alpha</tex> для этого алфавита. Для каждого слова <tex>P</tex> в алфавите <tex>A</tex> (то есть для любой конечной последовательности букв алфавита <tex>A</tex>) рассмотрим двоичное слово <tex>\alpha(P)</tex>, которое получается, если записать подряд коды всех букв из <tex>P</tex> (без каких-либо разделителей). Код <tex>\alpha</tex> называется '''''однозначным''''', если коды различных слов различны: <tex>\alpha(P)\ne\alpha(P')</tex> при <tex>P\ne{P'}</tex>.
 
 
}}
 
}}
  

Версия 04:26, 31 октября 2011

Необходимые определения

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

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


Определение:
Кодом для алфавита [math]A[/math] называется функция [math]C[/math], которая для каждого символа [math]x[/math] из [math]A[/math] указывает слово [math]C(x)[/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]k[/math] кодовыми словами [math]P_1,P_2, ..., P_k[/math]. Необходимо доказать, что их длины [math]n_i=|P_i|[/math] удовлетворяют неравенству Крафта—Макмиллана.

Вместо нулей и единиц будем использовать [math]a[/math] и [math]b[/math] (из чего составлять коды разницы нет). Запишем формально сумму всех кодовых слов как алгебраическое выражение [math]P_1+P_2+...P_k[/math] (многочлен от [math]a[/math] и [math]b[/math], в котором одночлены записаны как произведения переменных [math]a[/math] и [math]b[/math], без возведения в степень). Теперь (ещё более странное на первый взгляд действие) возведём это в степень [math]N[/math] (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в одночленах: [math](P_1+P_2+...P_k)^N=[/math] сумма одночленов.

Например, для кода со словами [math]0,10,11[/math] (которые теперь записываются как [math]a,ba,bb[/math]) и для [math]N=2[/math] получаем [math](a+ba+bb)^2[/math][math]=[/math]

[math]=(a+ba+bb)*(a+ba+bb)=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.[/math] В этом примере все одночлены в правой части различны (если не переставлять переменные), и это не случайно: так будет для любого однозначного кода. В самом деле, по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.

Теперь подставим [math]a=b=\frac{1}{2}[/math] в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится [math](2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N[/math] (в скобке как раз выражение из неравенства Крафта—Макмиллана). Правую часть мы оценим сверху, сгруппировав слова по длинам: имеется не более [math]2^l[/math] слагаемых длины [math]l[/math], каждое из которых равно [math]2^{-l}[/math], и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть [math]N*\max(n_i)[/math]. Итак, получаем, что [math](2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N\lt N*\max(n_i)[/math] и это верно при любом [math]N[/math]. Если основание степени в левой части больше единицы, то при больших [math]N[/math] это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта—Макмиллана. Что и требовалось доказать.
[math]\triangleleft[/math]

Ссылки

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

Литература

А. Шень "Программирование: теоремы и задачи" (Издание четвёртое, Москва, Издательство МЦНМО, 2011) стр. 206 - 210