Изменения

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

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

Есть разные способы решить эту задачу, но будет приведено простое и красивое, хотя и несколько загадочное, решение. <br />Пусть имеется [[Кодирование информации | однозначный код ]] с <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>NmaxN\times{\max(n_i)}</tex>. Итак, получаемПолучаем, что <tex>(2^{-n_1}+2^{-n_2}+...\dots+2^{-n_in_k})^N<Nmax\leqslant N\times{\max(n_i)}</tex> и это верно при любом для любого <tex>N</tex>. Если основание степени в левой части больше единицыТак как показательная функция растет быстрее линейной, то при больших основании (сумма <tex>N2^{-n_i}</tex> это ) большем единицы неравенство нарушится (показательная функция растет быстрее линейной)нарушается. Поэтому, для [[Кодирование информации | однозначного кода ]] выполняется неравенство Крафта{{---}}Макмиллана. Что и требовалось доказать.

== Ссылки См.также == *[[Неравенство Крафта]]

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