С.В. Яблонский - Введение в дискретную математику (1060464), страница 39
Текст из файла (страница 39)
1Ч. ТЕОРИЯ КОДИРОВАНИЯ печного множества взаимно однозначным. Трудоемкость ко такого алгоритма можно грубо оценить как г . Оказывается, что данный алгоритм не может быть использован даже в простых примерах. П р и м е р 6. Рассмотрим алфавитное кодирование (см. пример 5). Мы имеем г 5, )т' = 2, Ь = 16. г о 51з что весьма велико. $ 2.
Алгоритм распоанавания однозначности декодирования Иа докааательства критерия однозначности декодирования можно извлечь достаточно аффективный алгоритм для распознавания. возможности декодирования. Этот алгоритм формулируется на языке теории графов (Марков Ал. А. [22 — 241).
Пусть алфавитное кодирование задано схемой Е1 а,— В„ а,— В,. Для каждого злементарного кода В, рассмотрим все нетривиальные представления вида В, = 5 В1, ... В1 й; (1) в которых 5' и (1 отличны от элементарных кодов. Обозначим через 6, множество, содержащее: а) пустое слово Л; б) слова 5, которые встречаются в разложениях вида (1) как в форме префиксов, так и окончаний. Далее, каждому слову нз 6, сопоставим точку на плоскости. Пусть 5', 5" ж 6,. Рассмотрим все нетривиальные разложения вада (1). Для каждого из пих соединяем соответствующие словам 5' и 5" вершины направлекпым отревком (от(1' к 5 ), которому прпписано слово В1,, В1„.
Полученный граф обозпачим через Г(Е). гвэ ч, 1у. теОРия коднвования Отметим особо тривиальный случай, когда свойство взаимной однозначности алфавитного кодирования со схемой Е нарушается из-за того, что существует элементарный код В, с разложением вида (1), в котором 1)' Л (т. е. В~ разбивается на элементарные коды). В этом случае граф Г(Х) содержит петлю при вершине Л. Теорема 4. Ал(баеитное кодирование со схемой Е не обладает свойством взаимной однозначности тогда и только тогда, когда Г (Х) содержит ориентированный цикл, кроходягций через вершину Л. Доказательство. Необходимость. Пусть алфавитное кодирование не обладает свойством взаимной однозначности.
Тогда найдется неприводимое слово В вида (см. $1) Ц 'еь 1г 1а1 1г 1ее для которого В„- В,... В „()'г 1„ю В,, ()'В,... В, ~'г 1 в ~ в ... в 1г 1Р Поэтому в графе Г (Х) имеется ориентированный цикл (см. рис. 8), проходящий через вершину Л, д4- д1'~,е Зтгг Ряс. б Рвс. 9 Достаточность. Пусть Г (Х) содержит ориентированный цикл, проходящий через вершину Л (см, губ ч. РР ткория кодиРОВАнпя рис. 8).
Тогда слово В, где В = В а... В, р'В 1... В, 8"... (3 В р... В р 11 1шо |1 1в1 |1 | Р имеет две расшифровки, определяемые двумя разбиениями В =~В,~... ~В, ~ Р В,... В, Р"~(В,~ ... (В, ) (()" В,... В, 8") ..., В=(В|а ° ° ° Ва ~)(В1) ° ° ° (В,а)~1 В|а ° ° ° В а р ) ° ° ° Теорема доказана. Таким образом, алгоритм состоит из построения гра- фа Г(Х) и выявления ориентированных циклов, прохо- дящих через Л. П р и м е р 7. Рассмотрим алфавитное кодирование (см.
пример 5) со схемой а, — Ь1Ь|, а, — Ь!Ь,Ь,', а, — ь,ь„ (~). а| Ь1ЬаЬ!Ьа, а, — Ь,Ь,Ь,Ь,Ь,. Имеем следующие нетривиальные разложения: В, =(Ь,) (Ьа), Ва =(Ьа) (Ь|Ь|) (д|Ь|) (Ьа)| В, =(Ьа) (Ь.), В.-(ьа) (Ь Ьаь )-(Ь,ь,) (Ьаьа)'=(Ь,ьаьа) (Ьа)', В, - (Ь,) (Ь Ь,Ь.Ь,)-(Ь,) (Ь Ь,) (Ь Ь,)-(Ь,Ь,) (Ь,Ь|Ь,)- (Ь,Ь,Ь,) (Ь,Ь,) (Ь,Ь,Ь,Ь,) (Ь,), Очевидно, 6| (Л, Ь„Ь,Ь~) и с ним связаны разложения Ва (Ь1Ьа) (Ьа), В,-(Ь,Ь,) (Ь,Ь',)-В,(Ь,Ь,), Ва (Ьа)(ЬаЬ|)(Ь,Ь,) (Ьа)В,В|.
Это дает возможность построить граф Г (Е) (см. ркс. 9). Г (Е) содержит ориентированный цикл, порождающий слово В, В = В,Ь,Ьаь|В|В|| 27$ Ч. 1У. ТЕОРИЯ КОДИРОВАНИЯ имеющее две расшифровки: В (В,Ь,Ь,)(Ь,В,В,), т. е. А'=ага„ В=В|(Ь|ЬаЬ|)В|В|, т. е. А" а,а,а,а,. П р и и е р 8. рассмотрим алфавитное кодирование со схемой а,— Ь„ а, — Ь,Ь„ а, — Ь,Ь,Ь„ (Х) а, — Ь,Ь,Ь,Ь„ а, — Ь,Ь,Ь,Ь,. Имеем следующие нетривиальные разложения в, (ь,) (ь,) =(ь,)в,; В, (Ъ,) (Ьаьа) В,(Ь,Ь,); В, =(Ь,Ь,) (Ьа); В, ° (Ь,) (Ьа) (Ьаь|) (Ьа)В|(ЬаЬ|); В, (Ь,) (Ь,Ь,Ь,)=(Ь,)В,; в, (ь,ь,) (ь,ь,) в,(ь,ь,); в, (ь,ь,ь,) (ь,)'; В, (Ь,) (Ь,Ь,Ь,) (Ь,Ь,) (Ьаьа)=(ьаьаьа) (Ьа).
Очевидно, 6, (Л, Ь„Ь,Ь„Ь,Ь,Ь,) и с нкм связаны Б|Б Бг Ркс. ХО разложения В, (Ь)в;, в, в,(ь ь ); в,-(ь.)в,(ь',ь,); в,-(ь.)в;, в,-в,(ь,ь,); Ва (Ьа) (ЬаЬаЬа) (ЬаЬа) (Ь|Ьа) = (ЬаЬ|Ьа) (Ьа), Мы получаем граф Г (у) (см. рис. 10), не содержащий ориентированного цикла, проходящего через вершину Л. г7г ч. »т. теОР»»я кодитовлн»»я Следовательно алфавитное кодирование со схемой Е обладает свойством взаимной однозначности. Данное заключение не может быть выведено нз теоремы 2, $3. Об одном свойстве взапмио однозначных кодов') В алфавитном кодировании важное место занимают схемы, для которых выполнено.
свойство взаимной однозначности. Здесь мы докажем несколько результатов для таких кодов. Пусть задано алфавитное кодирование со схемой Е а,— В„ ° Ф В а,— В,. Пусть, как и раньше, о — число букв в алфавите 6 и »» )(В») (1 1, ..., г). 'Теорема 5 (неравенство Макмиллана [43]). Если ая»равитное кодирование со схемой Х обладает свойствен вваиз»ной однозначности, то Х1 (;1, (2) »=1 Я Докааательство. Рассмотрим всевозможные слова в алфавите 6, имеющие длину я. Все ови мо»ут быть порождены выражением (а,+...+а,)", если перемножать скобки (например слева) бев употребления закона коммутативности и рассматривать произведение а»,а»»...
а»„ как запись слова в алфавите И. Здесь, очевидно, символ а», будет принадлежать первой скобке, ໠— второй н т. д., ») До сях яор слово»кол» употреблялось в общепряяятом смысле. Однако е теории кояяроваявя, а еще равьшв в техяяяе слово «яод» стало трактоваться также в как множество (элемевтарвмх) иодов сообщеввй. Начяяая с етого места, слово»яол» будет употребляться в обовх смыслах. Иа текста, как аревало, будет ясно, какой яз явх имеется е виду. (Дрим»ч. лед.) ч. »ч. теогпл»»од»»говлн»»я а»„- п-й скобке. Мы имеем (а + ... +а,)" ~ а;,а», а,„, (»»»»"' ) Соответствующие этим словам коды получаются, если осуществить замену символов а„..., а„на элементарные коды В„..., В„используя схему алфавитного кодирования. Мы получим (В,+ ... + В.)" ~ В»,В», В»„(3) (»»»к»а) В силу взаимной однозначности алфавитного кодирования, если (»„..., („)чьц„...,)„),т.е.
а» ... а»„~а)» ... а»„, то В»» В»п Чй В)1 В)о Тождеству (3) соответствует тождество Очевидно, что здесь членам с одинаковым знаменателем из правой суммы соответствуют в (3) слова В»,В»,... „, В»„одинаковой длины. Введем обозначения; З=(»»+ в" +(»„» ч(я, () — число словВ» В» ... В»„пз (3)',нмеющпхдлнну »е), и г- ° г», »л»л~ Мы получим о» (»,...»„)ч'» "' '" »» е Из взаимной однозначности алфавитного кодирования вытекает ч(я, »)»~ о» ч) ч(л, ») О, если слов длины» в (3) нот.
Ч. П'. ТЕОРИЯ КОДИРОВАНИЯ и, следовательно, Объединяя последнее неравенство с (4), мы получим У ;)" ,—,', а-.7~н1. »»е Это неравенство справедливо для любого п. Поэтому оно справедливо и при переходе к пределу при и ч, Окончательно имеем Хт » 1в Теорема полностью доказана. Данное утверждение дополняется следующим фактом. Теорема 6. Если числа 1„..., 1, удовлетворяют неравенству (2) (неравенству Макмиллана), то существует алфавитное кодирование со схемой У а,— В„ (Х') У ат — Вте обладающей свойством префикса и удовлетворяющей равенством 1(В,) 1„..., 1(В,) 1„ Докааательство. Можно считать, что ... < 1,. Разобьем числа 1„..., 1, на классы так, что 1» н 1, принадлежат одному классу тогда и только тогда, когда 1» 1».
Пусть р. (т < р < т) — число классов, а А„ ..., А„, ч„..., т„обозначают соответственно предста ангелой и мощности классов. Можно также считать, что ~»<д,«...)~,. Неравенство Макмиллана можно переписать в виде и Х+-ь $1Ф ч. <т. теОРия кодиРОВАния 275 Это неравенство порождает серию вспомогательных не- равенств ч — ($ нля ч<(д Х< ~1 ч, ьг лг-ь< — + — (1 илн чг(д — т<у Ь< Лг ч ч —, + -5-+ ... + —,:~2 или ч, ч ' ч„ е е з т~~ 'Е-Ь< ЬЕ-Ьз "е Ьз 1 та(~ ч — ч<ч — чзч ° ° че-<ч Рассмотрим слова в алфавите <й, имеющие длину йо Ь< Так как т<~д, то можно выбрать из них ч< слов дли- Ф ныйо ОбозначимйхчерезВ<< ...,Вч<.
Исключим из даль- 1 Р нейшнх рассмотрений слова, начинающиеся с В„..., В,, Далее, возьмем множество слов в алфавите 6, имеющих 2 Р длину $в, которые не начинаются со слов В<, ..., Вч; Ьз 11-1, Очевидно, что таких слов будет д . — ч<д . Так как Хг ьг-Ь< чг~ (у — чзэс, то из этого множества можно выбрать ! ч, слов — обозначим их через Вчд<< ° * ° Вч<+чг Исключим нз дальнейшего рассмотрения слова, начинаю- Р Р щиеся таки<о и с Вч<+<...,„В,<+,ги т. д. Используя постепенно вспомогательные неравенства, мы построим в слова Вм ...„В,~т ~ ч; . Если нх взять в качестве < 1 элементарных кодов, то мы получим искомую схему 2", Для Х' выполнено свойство префикса и 1(В,') -1и,.„1(В',) - 1„.
Теорема доказана. Следствие 1. Неравенство Макмиллана является необходимым и достаточным условием существования ал<бавитного кодирования, у которого схема обладает свойством Яре<бикса и длины элементарных кодов равны соответственно 1О ..., 1,. Следствие 2. Если существует взаимно однозначное алЯавитное кодирование с заданными длинаки эле- ч. зт.
теОРия коднговання ментарных кодов, то существует также ал1давитное кодирование со схемой, обладающей свойством нреЯикса, и с теми же длинами элементарных кодов. Для доказательства следует применить сначала теорему 5, а затем теорему 6. 4 4. Коды с минимальной избытечностью Предположим, что задан алфавит И (аь ..., а,) т (г>2) и набор вероятностей р„...,р, ~,~ р~ 1 появле- $-1 ний символов а„..., а,. Пусть, далее, задан алфавит 6 (йи ..., 6,) (о> 2).
Тогда можно построить целый ряд схем Х алфавитного кодирования а,— В„ а,— В„ обладающих свойством взаимной однозначности. В частности, всегда моя~но взять в качестве кодов В„ ..., В, различные слова в алфавите 6 одинаковой длины ), где 1 ))об,г~. Для каждой схемы Х можно ввести среднюю длину 1„, определяемую как математическое ожидание длины элементарного кода, т. е. )„-~рд, 1,=)~В,). $-1 Ф Очевидно, что величина 1„(!., > 1) показывает, во сколь- ко раз увеличивается средняя длина слова при кодиро- вании со схемой Х.
Пример 9. Пусть г 4, д 2 и р, 0,40, рз 0,25, р,-0,20, р, 0,15. Рассмотрим две схемы алфавитного кодирования: а, — 00, а,— 1, а,— 01, а,— 01, (ВФ ) а,— 10, о, — 000, а~ — 11 а, — 001. Они, очевидно, обладают свойством взаимной однозначно- сти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
