Изменения

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

<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le leqslant 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого [[Кодирование информации | однозначно декодируемого кода.]]

Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи". Пусть имеется [[Кодирование информации | однозначный код ]] с <tex>k</tex> кодовыми словами <tex>P_1, ...\dots, P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.

Рассмотрим любой однозначный код с <tex>k</tex> кодовыми словами <tex>P_1, ..., P_k</tex>. Для удобства при кодировании вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> соответственно.

Представим сумму всех слов (кодируемых через <tex>a</tex> и <tex>b</tex>) и возведем эту сумму в степень <tex>N \in \mathbb N</tex> (любое натуральное число): <tex>(P_1+P_2+...\dots+P_k)^N</tex>. Раскрывая Раскроем скобки, сохраним порядок переменных и не будем собирать их вместе (то есть возводить их в степень)подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.

Вот пример для [[Кодирование информации | однозначного кода ]] со словами <tex>a,ab,bb</tex> и <tex>N=2</tex>:<tex>(a+ab+bb)^2</tex><tex>=(a+ab+bb)\times{(a+ab+bb)}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.</tex> Все получившиеся слагаемые (слова) различны (соответствует определению однозначности).

Если неравенство верно для букв, то оно верно для любых числовых значений. Подставим <tex>a=b=</tex> <tex dpi = 150> \frac{1}{2}</tex> в неравенство. Для кодового слова <tex>P_i</tex> длины <tex>{n_i}</tex> получим <tex>2^{-n_i}</tex>. В левой части получится выражение из неравенства Макмиллана: <tex>(2^{-n_1}+2^{-n_2}+...\dots+2^{-n_k})^N</tex>. Всего имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex> равных <tex>2^{-l}</tex>, следовательно слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых: <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...\dots+2^{-n_in_k})^N \le leqslant N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании (сумма <tex>2^{-n_i}</tex>) большем единицы неравенство нарушается. Поэтому, для [[Кодирование информации | однозначного кода ]] выполняется неравенство Макмиллана.

== Ссылки См.также ==

== Литература Источники информации ==*[http://ru.wikipedia.org/wiki/Неравенство_Крафта_—_Макмиллана Википедия — Неравенство Макмиллана]*''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9