Изменения

Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.

Так как нет разницы из чего составлять коды, то вместо нулей и единиц будем использовать Рассмотрим любой однозначный код с <tex>ak</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,11a</tex>, то есть и <tex>a,ba,bbb</tex> ) и для возведем эту сумму в степень <tex>N=2</tex> получаем (любое натуральное число): <tex>(aP_1+baP_2+bb...P_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=\frac{1}{2}</tex> в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева В левой части получится выражение из неравенства Макмиллана: <tex>(2^{-n_1}+2^{-n_2}+...+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}+...+2^{-n_i})^N<\le N\times{\max(n_i)}</tex> и это верно при любом для любого <tex>N</tex>. Если основание степени в левой части больше единицы, то при больших <tex>N</tex> это неравенство нарушится (Так как показательная функция растет быстрее линейной), то при основании большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.