Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
разбиения для другой четности /. Отсюда легко получается оценка для максимального числа элементарных кодов, входящих в разбиение. Оно не превосходит
У'-.М ? 1 + [ь-{±1} к < [<иГ + <>^-г + «1].
Мы получаем, что
Если теперь положить А0=тах(1(А'), то
очевидно, что взаимная однозначность кодирования уже
ЛГ0 я
нарушается на множестве 8 (§[), так как А\А"&
е5 ($). Теорема полностью доказана.
Критерий однозначности декодирования дает простой алгоритм для установления по схеме 2, будет алфавитное кодирование обладать свойством взаимной однозначности или нет. Для этого достаточно рассмотреть множество слов в алфавите 91, имеющих длину не более N0,
Чу
т. е. ? 0 {Щ1 и выяснить, будет лп кодирование этого ко-
268
Ч, IV. ТЕОРИЯ КОДИРОВАНИЯ
кечного множества ^взаимно однозначным. Трудоемкость
Л'0
такого алгоритма можно грубо оценить как г . Оказывается, что данный алгоритм не может быть использован даже в простых примерах.
Пример 6. Рассмотрим алфавитное кодирование {см. пример 5). Мы имеем г = 5, IV = 2, /> = 16.
Берем/V,, = ^ ВА?и г + 2> j= 19 и получаем
Л = 519,
что весьма велико.
§ 2. Алгоритм распознавания однозначности декодирования
Из доказательства критерия однозначности декодирования можно извлечь достаточно эффективный алгоритм для распознавания возможности декодирования. Этот алгоритм формулируется на языке теории графов {Марков Ал. А. [22-24]).
Пусть алфавитное кодирование задано схемой 2:
я, В^
............ (I) ?
ат — Вг.
Для каждого элементарного кода В{ рассмотрим все нетривиальные представления вида
^ = Р'Я,, ... П1кР", (1)
в которых р' и р* отличны от элементарных кодов. Обозначим через ЗЗо множество, содержащее:
а) пустое слово Л;
б) слова р, которые встречаются в разложениях вида (1) как в форме префиксов, так и окончаний.
Далее, каждому слову из 330 сопоставим точку на плоскости.
Пусть р/, р" Рассмотрим все нетривиальные разложения вида (1). Для каждого нз них соединяем соответствующие словам р' о Р" вершииы направленным отрезком (от р'к р"), которому приписало слово В^ ... В1у}, Полученный граф обозначим через Г (2),
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
269
Отметим особо тривиальный случай, когда свойство взаимной однозначности алфавитного кодирования • со схемой 2 нарушается из-за того, что существует элементарный код Z?i с разложением вида (1), в котором *=? = {}"=Л (т. е. В, разбивается на элементарные коды). В этом случае граф Г(2) содержит петлю при верпшне Л.
Теорема 4. Алфавитное кодирование со схемой 2 не обладает свойством взаимной однозначности тогда и только тогда, когда Г (2) содержит ориентированный цикл, проходящий через вершину Л.
Доказательство. Необходимость. Пусть алфавитное кодирование не обладает свойством взаимной однозначности. Тогда найдется неприводимое слово В вида (см. § 1)
В = В п . .. В , Р'Я д .. . В L р' .. . ... 2?.р ,
Ti V° Va г1 1«оР
для которого
Я.0 ~ /? 0 ... В „ Р'(
Г,
И I 1
1 ш1
/?.р — • * * В р •
н V'p
Поэтому в графе Г (2) имеется ориентированный цикл (см. рис. 8), проходящий через вершину А.
Достаточпость. Пусть Г (2) содержит ориентированный цикл, проходящий через вершину А (см.
?1\] М. IV. ТЕОРИЯ КОДИРОВАНИЯ
рис. 8). Тогда слово В, где
В = ВЛ...ВЛ рвл...вл р',..ррЯ.р...В.р ,
11 гго° 11 V 11 1и>р
имеет две расшифровки, определяемые двумя разбиениями
а-(^-(в^Г4-Чг)(в«)-
.••(Яд] №"Ва...В(»р,П ....
Теорема доказана.
Таким образом, алгоритм состоит из построения гра-* фа Г (2) и выявления ориентированных циклов, проходящих через Л.
Пример 7. Рассмотрим алфавитное кодирование (см. пример 5) со схемой
йі - Ь,Ь2,
СІІ
й8 Ь2Ь3у (2)'
0-І,
й'5 &2^1^2^2^3*
Имеем следующие нетривиальные разложения:
В% — (&і) (6362) — (Ьі^з) (^а)» В3 ~ (&г) (Ьз),
Вк = (Ь.) (&А6-)' = (ЬіЬ.) (&!&эу= (6,6,6.) (6зу,
Въ^= (Ъг) (Ь1Ь->ЬгЬ3) = (Ь2) (&162) (Ь2&з) = (Ь2Ь1) (&2Ь2Ьз) =
= (&2&і&2) (&2^і) “ (^г^і^^г) (^з)«
Очевидно, 5Э0 = (Л, і?2, Ьі&аУ и с ним связаны разложения Я2 = (Мз)(62),
Я*«(М*)(ВД'~Яі(ЬАЇ, в. =(ба) (ьл) (№) - (мад.
Это дает возможность построить граф Г (2) (см. рис. 9). Г (2) содержит ориентированный цикл, порождающий слово В,
В — ВіЬіЬіЬзВіВ^
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ 271
имеющее две расшифровки:
В = (В1Ь1Ь!1) (ЬлВ^з), т. е. Л' = а4а5,
В — Вх (Ь1ЬаЬг)В1Ва, т. е. Л " =ала2а1а3.
Пример 8. Рассмотрим алфавитное кодирование со схемой
Й1 Ь а2- ЪгЪи
а3 ЬхЬ2Ь2, (2)
а1-Ь2Ь1Ъ2Ьг,
Имеем Следующие нетривиальные разложения в2^{Ь2)(Ьх) = (Ь2)В1;
В3 — {Ь1) ( Ъ2Ъ2} =* Вх (&2&г) ** В& — { &1&2) (&г) ! в, = (Ъг) (Ьх) (Ъ2Ъ2) = (Ъ2)Вх (Ь2Ъ2);
/?(, == (62) (616262) = (йг)Б3;
Вь = [Ь2Ьх) (&г&г)= Вг (Ь2Ь2); В^ — (6261^2) (М;
#5 = (Ь2) (Ь2м>2)- (ЬА) (ЬА) = (ЬЛЬ.) (Ь2).
Очевидно, 5% = {Л, Ь2, Ъ2Ъ2л Ъ2ЬгЬг} и с ним связаны
разложения
Вз = .61 {ЬгЪ2);
1?4 = {Ъ2}Вх (Ъ2Ь2^Вь = (Ь2)В3‘, В± — Вг 5 /?} а (Ьг) (Ьа&з) == {Ря} »
Мы получаем граф Г (2) (см. рис. 10), не содержащий ориентированного цикла, проходящего через вершину Л.
272
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
Следовательно алфавитное кодирование со схемой ? обладает свойством взаимной однозначности. Данное заключение не может быть выведено из теоремы 2.
