Изменения

== Необходимые определения =={{Определение |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,P_2, ...\dots, P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Крафта{{---}}Макмиллана.

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

Например, для кода со словами <tex>0,10,11</tex>, то есть <tex>a,ba,bb</tex> Представим сумму всех слов и для возведем эту сумму в степень <tex>N=2\in \mathbb N</tex> получаем : <tex>(aP_1+P_2+ba\dots+bbP_k)^2</tex><tex>=N</tex>. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.

Вот пример для [[Кодирование информации | однозначного кода]] со словами <tex>a,ab,bb</tex> и <tex>N=2</tex>:<tex>(a+baab+bb)^2</tex><tex>=(a+ab+bb)\times{(a+baab+bb)}=aa+abaaab+abb+baaaba+babaabab+babbabbb+bba+bbbabbab+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_in_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<\leqslant N\times{\max(n_i)}</tex> и это верно при любом для любого <tex>N</tex>. Если основание степени в левой части больше единицыТак как показательная функция растет быстрее линейной, то при больших основании (сумма <tex>N2^{-n_i}</tex> это ) большем единицы неравенство нарушится (показательная функция растет быстрее линейной)нарушается. Поэтому, для [[Кодирование информации | однозначного кода ]] выполняется неравенство Крафта{{---}}Макмиллана.

== Ссылки См.также ==*[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0 [Неравенство Крафта]]

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