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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
(Неравенство Макмиллана)
Строка 17: Строка 17:
 
  <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} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.
 
|proof=
 
|proof=
Докажем теорему способом, приведенным А. Шенем.
+
Докажем теорему способом, приведенным в книге А. Шеня.
  
 
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., 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>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>0,10,11</tex> (которые теперь записываются как <tex>a,ba,bb</tex>) и для <tex>N=2</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex>
+
Например, для кода со словами <tex>0,10,11</tex>, то есть <tex>a,ba,bb</tex> и для <tex>N=2</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex>
  
 
<tex>=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex> Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.
 
<tex>=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex> Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.

Версия 06:01, 15 декабря 2011

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

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

В качестве кодирующего алфавита часто рассматривается множество [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_2, ..., P_k[/math]. Необходимо доказать, что их длины [math]n_i=|P_i|[/math] удовлетворяют неравенству Крафта—Макмиллана.

Так как нет разницы из чего составлять коды, то вместо нулей и единиц будем использовать [math]a[/math] и [math]b[/math]. Запишем формально сумму всех кодовых слов как алгебраическое выражение [math]P_1+P_2+...P_k[/math] (многочлен от [math]a[/math] и [math]b[/math], в котором одночлены записаны как произведения переменных [math]a[/math] и [math]b[/math], без возведения в степень). Теперь возведём это в степень [math]N[/math] (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в одночленах: [math](P_1+P_2+...P_k)^N=[/math] сумма одночленов.

Например, для кода со словами [math]0,10,11[/math], то есть [math]a,ba,bb[/math] и для [math]N=2[/math] получаем [math](a+ba+bb)^2[/math][math]=[/math]

[math]=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.[/math] Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.

Далее подставим [math]a=b=\frac{1}{2}[/math] в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится [math](2^{-n_1}+2^{-n_2}+...+2^{-n_i})^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_i})^N\lt N\times{\max(n_i)}[/math] и это верно при любом [math]N[/math]. Если основание степени в левой части больше единицы, то при больших [math]N[/math] это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта—Макмиллана.
[math]\triangleleft[/math]

Ссылки

Литература

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