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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

При необходимости построить префиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной. Но неравенство Макмиллана даёт необходимое условие существования префиксных и любых однозначно декодируемых кодов, обладающих заданным набором длин кодовых слов.

Теорема (Неравенство Макмиллана (англ. McMillan's inequality)):

[math] \sum\limits_{i = 1}^{|A|} 2^{-l_i} \leqslant 1[/math] (где [math]l_i[/math] — длины кодовых слов) выполняется для любого однозначно декодируемого кода.

Доказательство:

[math]\triangleright[/math]

Пусть имеется однозначный код с [math]k[/math] кодовыми словами [math]P_1,\dots, P_k[/math]. Необходимо доказать, что их длины [math]n_i=|P_i|[/math] удовлетворяют неравенству Макмиллана. Для удобства при кодировании вместо нулей и единиц будем использовать [math]a[/math] и [math]b[/math] соответственно. Представим сумму всех слов и возведем эту сумму в степень [math]N \in \mathbb N[/math]: [math](P_1+P_2+\dots+P_k)^N[/math]. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными. Вот пример для однозначного кода со словами [math]a,ab,bb[/math] и [math]N=2[/math]: [math](a+ab+bb)^2[/math][math]=(a+ab+bb)\times{(a+ab+bb)}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.[/math] Все получившиеся слагаемые различны (соответствует определению однозначности). Подставим [math]a=b= [/math] [math] \frac{1}{2}[/math] в неравенство. Для кодового слова [math]P_i[/math] длины [math]{n_i}[/math] получим [math]2^{-n_i}[/math]. В левой части получится выражение из неравенства Макмиллана: [math](2^{-n_1}+2^{-n_2}+\dots+2^{-n_k})^N[/math]. Всего имеется не более [math]2^l[/math] слагаемых длины [math]l[/math] равных [math]2^{-l}[/math], следовательно слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых: [math]N\times{\max(n_i)}[/math]. Получаем, что [math](2^{-n_1}+2^{-n_2}+\dots+2^{-n_k})^N \leqslant N\times{\max(n_i)}[/math] верно для любого [math]N[/math]. Так как показательная функция растет быстрее линейной, то при основании (сумма [math]2^{-n_i}[/math]) большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.

[math]\triangleleft[/math]

См.также

• Неравенство Крафта

Источники информации

• Википедия — Неравенство Макмиллана
• Шень А. Х. Программирование: теоремы и задачи. — М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9