Изменения
Нет описания правки
|about=Неравенство Макмиллана (англ. McMillan's inequality)
|statement=
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le leqslant 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.
|proof=
Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи".
<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>{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_k})^N \le leqslant N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании (сумма <tex>2^{-n_i}</tex>) большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.
}}
