93
правки
Изменения
→Неравенство Макмиллана
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.
|proof=
Докажем теорему способом, приведенным в книге А. ШенемШеня.
Пусть имеется однозначный код с <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>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> Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.
