Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
§ 3. Об одном свойстве взаимно однозначных кодов*)
В алфавитном кодировании важное место занимают схемы, для которых выполнено свойство взаимной однозначности. Здесь мы докажем несколько результатов для
таких кодов.
Пусть задано алфавитное кодирование со схемой ? а1 - Ви
. . . (2):
аг - Вг.
Пусть, как в раньше, q — число букв е алфавите 53 и (1-1, ..., г)..
Теорема 5 (неравенство Макмиллана [43]). Если, алфавитное кодирование со схемой 2 обладает свойством взаимной однозначности, то
2^<‘- (2)
1-1 9
Доказательство. Рассмотрим всевозможные слова в алфавите 21, имеющие длину и. Все они ыллут быть порождены выражением
(й^ + .-. + Ог)",
если перемножать скобки (например слева) без употребления закона коммутативности и рассматривать произведение
как запись слова в алфавите 21. Здесь, очевидно, символ а«! будет принадлежать первой скобке, сц2~ второй и т. д.,
*) До сих пор слово «код» употреблялось в общепринятом смысле. Однако в теории кодирования, а еще раньше в технике слово «код» стало трактоваться также и как множество (элементарных) 'кодов сообщений. Начиная с этого места, слово «код» будет употребляться в обоих смыслах. Из текста, как правило, будет ясно, какой из них имеется в виду. {Примеч. ред.)
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ 273
й{„— п-в скобке. Мы имеем
(йі+ ... + аг)п = 2 ачаі2 • - * аіп*
*п)
Соответствующие этим словам коды получаются, если осуществить замену символов аи ат на элементарные коды Ви ..Вт, используя схему алфавитного кодирования. Мы получим
(В, + ...+ Вг)п =. 2 в, в, ... в, (3)
(ііі3--іп)
В силу взаимной однозначности алфавитного кодирования, если (К, (Л,...,/*).Т.е. аіх ... тлФа}х ,..
• * * «і*
Ч • • * віп ф в31,,, вул.
Тождеству (3) соответствует тождество
(Д+... + -^у= 2 1^7- <4>
Очевидно, что здесь членам с одинаковым знаменателем из правой суммы соответствуют в (3) слова В^В^ ,.,
,,, 2з^одинаковой длины. Введем обозначения;
і — 1%^ “Н • • • Н~
\’(л, і)— число слов • . * Віи из (3)’, имеющих длину
?*), и
I = шах Іі.
1<І<Т
Мы получим
гЛ
2 і у V (И, І)
О +...гО Jш* ? Л *
(Ч-іп)я 1 п 1 в
Из взаимной однозначности алфавитного кодировав вия вытекает
\(п,
*) у(п» 0 = если СП03 Длины { в (3) нет* 18 С. Б. Яблонский
274 ч. IV. ТЕОРИЯ КОДИРОВАШГЯ
и, следовательно,
й Г
Объединяя последнее неравенство с (4), мы получим
Это неравенство справедливо для любого п. Поэтому оно справедливо И при переходе К пределу при п -*? оо, Окончательно имеем
1=1(2
Теорема полностью доказана. Данное утверждение дополняется следующим фактом.
Теорема 6. Если числа 1и 1Г удовлетворяют неравенству (2) (неравенству Макмиллана), то существует алфавитное кодирование со схемой
Й1 — в'и
. . . . (2')
?Е/ В ^
обладающей свойством префикса и удовлетворяющей равенствам
1{Ю = 1и
Доказательство. Моягно считать, что ... ^ 1Т. Разобьем числа 1и . -К на классы так, что и и 1} принадлежат одному классу тогда и только тогда, когда и — I}. Пусть р. (1 ^ р < г) — число классов, а Хи .
..., VI, ..обозначают соответственно представителей и мощности классов. Можно также считать, что
?ч < < ... < К-
Неравенство Макмиллана можно йерепнсать в виде
в
1=1 я
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ 275
Это неравенство порождает серию вспомогательных неравенств
-у- ^ 1 или ^
ч 1
^ + пли ^ “ — \\д
-г + т" + • ? • + ~г < 1 ЕЛИ
Л| Г*л Лц ^
Ьи ^ц~^2 Ьц-Ьи_1
Рассмотрим слова в алфавите Э, имеющие длину Так какУ!^^1, то можно выбрать из них V» слов длины^. Обозначим их через Ви .. .3 ВЧ1. Исключил! из дальнейших рассмотрений слова, начинающиеся с2?!, ..5^. Далее, возьмем множество слов в алфавите 59, имеющих длину К2, которые не начинаются со слов Ви
7 7 —7
Очевидно, что таких слов будет д' —V!*? 2 Так как
%2 ^-2 ^ 1 -^ й — ’'ЧЗ 1 то из этого множества можно выбрать
\г слов — обозначим их через ^,+1? • • •> ^У1+У2. Исключил! из дальнейшего рассмотрения слова, начинающиеся также и с В^^и .. .х ВХ1+У2ш т. д. Используя постепенно вспомогательные неравенства, мы построим
слова Ви ,. ,г В’г = 2 V,Если их взять в качестве
элементарных кодов, то мы получим искомую схему 2', Для 2' выполнено свойство префикса и
I (/?2) = 11з {Вг) = 1Т•
Теорема доказана.
Следствие 1. Неравенство Макмиллана является необходимым и достаточным условием существования алфавитного кодирования, у которого схема обладает свой-ством префикса и длины элементарных кодов равны соответственно и,..1Т.
Следствие 2. Если существует взаимно однозначное алфавитное кодирование с заданными длинами эле-18*
276
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
появло-
мептарных кодов, то существует также алфавитное кодирование со схемой, обладающей свойством префикса, и с теми же длинами элементарных кодов.
Для доказательства следует применить сначала теорему 5, а затем теорему 6.
§ 4. Коды с минимальной избыточностью Предположим, что аадап алфавит 9С = {<21, ..аг}
г (г> 2) и набор вероятностей /ц,.. .,рг (^2 Р1 — 1^
иий символов а,, ..ат. Пусть, далее, задан алфавит ® = {^1, Ъч) (д > 2). Тогда можно построить целый ряд схем 2 алфавитного кодирования
в. -Ви (2)'
