Изменения

Перейти к: навигация, поиск

Неравенство Макмиллана

34 байта убрано, 03:27, 13 января 2012
Нет описания правки
<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=\frac{1}{2}</tex> в неравенство для того, чтобы получить . Для кодового слова <tex>P_i</tex> длины <tex>{\frac{1}{2}}^{n_i}=2^{-n_i}</tex>, где получим <tex>{2^{-n_i}</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_in_k})^N \le N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.
}}
Анонимный участник

Навигация