Неравенство Макмиллана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Неравенство Макмиллана)
м (rollbackEdits.php mass rollback)
 
(не показаны 23 промежуточные версии 5 участников)
Строка 1: Строка 1:
== Необходимые определения ==
+
При необходимости построить префиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной. Но неравенство Макмиллана даёт необходимое условие существования префиксных и любых [[Кодирование информации | однозначно декодируемых кодов]], обладающих заданным набором длин кодовых слов.
{{Определение
 
|definition=
 
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}
 
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.
 
 
 
{{Определение
 
|definition=
 
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}
 
{{Определение
 
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.
 
}}
 
 
 
== Неравенство Макмиллана ==
 
 
{{Теорема
 
{{Теорема
 +
|about=Неравенство Макмиллана (англ. McMillan's inequality)
 
|statement=
 
|statement=
  <tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.
+
  <tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \leqslant 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого [[Кодирование информации | однозначно декодируемого кода.]]
 
|proof=
 
|proof=
Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи".
+
Пусть имеется [[Кодирование информации | однозначный код]] с <tex>k</tex> кодовыми словами <tex>P_1,\dots, P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.
 
 
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.
 
  
Так как нет разницы из чего составлять коды, то вместо нулей и единиц будем использовать <tex>a</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>a</tex> и <tex>b</tex> соответственно.
  
Например, для кода со словами <tex>0,10,11</tex>, то есть <tex>a,ba,bb</tex> и для <tex>N=2</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex>
+
Представим сумму всех слов и возведем эту сумму в степень <tex>N \in \mathbb N</tex>: <tex>(P_1+P_2+\dots+P_k)^N</tex>. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.
  
<tex>=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</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=\frac{1}{2}</tex> в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^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<N\times{\max(n_i)}</tex> и это верно при любом <tex>N</tex>. Если основание степени в левой части больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта{{---}}Макмиллана.
+
Подставим <tex>a=b= </tex> <tex dpi = 150> \frac{1}{2}</tex> в неравенство. Для кодового слова <tex>P_i</tex> длины <tex>{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_k})^N \leqslant N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании (сумма <tex>2^{-n_i}</tex>) большем единицы неравенство нарушается. Поэтому, для [[Кодирование информации | однозначного кода]] выполняется неравенство Макмиллана.
 
}}
 
}}
  
== Ссылки ==
+
== См.также ==
*[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0 Неравенство Крафта]
+
*[[Неравенство Крафта]]
  
== Литература ==
+
== Источники информации ==
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9
+
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта_—_Макмиллана Википедия — Неравенство Макмиллана]
 +
*''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Алгоритмы сжатия]]
 
[[Категория: Алгоритмы сжатия]]

Текущая версия на 19:39, 4 сентября 2022

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

Теорема (Неравенство Макмиллана (англ. 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]

См.также

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