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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Неравенство Макмиллана)
Строка 23: Строка 23:
 
Для удобства при кодировании вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</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>N \in \mathbb N</tex>: <tex>(P_1+P_2+...P_k)^N</tex>. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.
  
 
Вот пример для однозначного кода со словами <tex>a,ab,bb</tex> и <tex>N=2</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+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 N\times{\max(n_i)}</tex> верно для любого <tex>N</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 N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.

Версия 04:12, 13 января 2012

Необходимые определения

Определение:
Пусть заданы два произвольных конечных множества, которые называются, соответственно, кодируемым алфавитом и кодирующим алфавитом. Их элементы называются символами, а строки (последовательности конечной длины) символов — словами. Длина слова — это число символов, из которого оно состоит.

В качестве кодирующего алфавита часто рассматривается множество [math]\{0, 1\}[/math] — так называемый двоичный или бинарный алфавит.


Определение:
Кодом для алфавита [math]A[/math] называется функция [math]C[/math], которая для каждого символа [math]x[/math] из [math]A[/math] указывает слово [math]C(x)[/math], кодирующее этот символ.


Определение:
Код называется однозначным, если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.


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

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

Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи".

Пусть имеется однозначный код с [math]k[/math] кодовыми словами [math]P_1, ..., P_k[/math]. Необходимо доказать, что их длины [math]n_i=|P_i|[/math] удовлетворяют неравенству Макмиллана.

Для удобства при кодировании вместо нулей и единиц будем использовать [math]a[/math] и [math]b[/math] соответственно.

Представим сумму всех слов (кодируемых через [math]a[/math] и [math]b[/math]) и возведем эту сумму в степень [math]N \in \mathbb N[/math]: [math](P_1+P_2+...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=\frac{1}{2}[/math] в неравенство. Для кодового слова [math]P_i[/math] длины [math]{n_i}[/math] получим [math]2^{-n_i}[/math]. В левой части получится выражение из неравенства Макмиллана: [math](2^{-n_1}+2^{-n_2}+...+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}+...+2^{-n_k})^N \le N\times{\max(n_i)}[/math] верно для любого [math]N[/math]. Так как показательная функция растет быстрее линейной, то при основании большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.
[math]\triangleleft[/math]

Ссылки

Литература

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