Неравенство Макмиллана

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

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

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

В качестве кодирующего алфавита часто рассматривается множество [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}^{|A|} 2^{-l_i} \le 1[/math] (где [math]l_i[/math] — длины кодовых слов) выполняется для любого однозначно декодируемого кода.

Доказательство:

[math]\triangleright[/math]

Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи". Пусть имеется однозначный код с [math]k[/math] кодовыми словами [math]P_1, ..., P_k[/math]. Необходимо доказать, что их длины [math]n_i=|P_i|[/math] удовлетворяют неравенству Макмиллана. Рассмотрим любой однозначный код с [math]k[/math] кодовыми словами [math]P_1, ..., 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]a,ab,bb[/math] и [math]N=2[/math]: [math](a+ab+bb)^2[/math][math]=(a+ab+bb)\times{(a+ab+bb)}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.[/math] Все получившиеся слагаемые (слова) различны (соответствует определению однозначности). Если неравенство верно для букв, то оно верно для любых числовых значений. Подставим [math]a=b=\frac{1}{2}[/math] в неравенство. В левой части получится выражение из неравенства Макмиллана: [math](2^{-n_1}+2^{-n_2}+...+2^{-n_k})^N[/math]. Всего имеется не более [math]2^l[/math] слагаемых длины [math]l[/math] равных [math]2^{-l}[/math], следовательно слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых: [math]N\times{\max(n_i)}[/math]. Получаем, что [math](2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N \le N\times{\max(n_i)}[/math] верно для любого [math]N[/math]. Так как показательная функция растет быстрее линейной, то при основании большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.

[math]\triangleleft[/math]

Ссылки

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

Литература

Шень А. Х. Программирование: теоремы и задачи. — М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9