Изменения
Нет описания правки
{{Теорема
|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</tex> и <tex>b</tex> соответственно.
Представим сумму всех слов (кодируемых через <tex>a</tex> и <tex>b</tex>) и возведем эту сумму в степень <tex>N \in \mathbb N</tex> (любое натуральное число): <tex>(P_1+P_2+...\dots+P_k)^N</tex>. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.
Вот пример для [[Кодирование информации | однозначного кода ]] со словами <tex>a,ab,bb</tex> и <tex>N=2</tex>:<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=</tex> <tex dpi = 150> \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}+...\dots+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}+...\dots+2^{-n_in_k})^N \le leqslant N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании (сумма <tex>2^{-n_i}</tex>) большем единицы неравенство нарушается. Поэтому, для [[Кодирование информации | однозначного кода ]] выполняется неравенство Макмиллана.
}}
== Ссылки См.также ==
*[[Неравенство Крафта]]
== Литература Источники информации ==*[http://ru.wikipedia.org/wiki/Неравенство_Крафта_—_Макмиллана Википедия — Неравенство Макмиллана]*''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия]]