93
правки
Изменения
→Неравенство Макмиллана
|proof=
Есть разные способы решить эту задачу, но будет приведено простое и красивое, хотя и несколько загадочное, решение. <br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., 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</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex>
<tex>=(a+ba+bb)(a+ba+bb)=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex> В этом примере все одночлены в правой части различны (если не переставлять переменные), и это не случайно: так будет для любого однозначного кода. В самом деле, по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.
Теперь подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство(если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex> (в скобке как раза раз выражение из неравенства Крафта-Макмиллана). Правую часть мы оценим сверху, сгруппировав слова пол по длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>Nmax(n_i)</tex>. Итак, получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<Nmax(n_i)</tex> и это верно при любом <tex>N</tex>. Если основание степени в левой степени части больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта-Макмиллана. Что и требовалось доказать.
}}
== Ссылки ==
[[Неравенство Крафта]]
