Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Рис. 12
(см. рис. 12) состоит в перемещении некоторого пучка из д концевых ребер в корень дерева, причем к корню присоединяется одна из концевых вершин (пучок ребер при исключительной вершине пе трогается, если даже д0 = д). Такое преобразование выполняется до тех пор, пока это возможно, и в результате получается дерево, изображенное на рис. 13. Из него видно, что число удовлетворяет уравнению
г = 1(д — 1)+
Вычислим остаток от деления г на д-1 и положим ' д — 1, если остаток равен 0,
?о = ‘ если остаток равен 1, (5)
, остатку, если он ^ 2,
Лемма 2. Среди кодов с минимальной избыточностью существует код, кодовое дерево которого является насыщенным.
Доказательство. Рассмотрим два преобразования кодовых деревьев указанного ниже типа, которые не увеличивают среднюю длину.
1. Удаление ребра в последнем ярусе. Если в некотором пучке последнего яруса кодового дерева содержится ровно, одно ребро, то с ним связан эле-
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
251
меитарный код В = В'Ъ с вероятностью р, причем слово В' не является префиксом никакого другого элементарного кода. Удаляя данное ребро и перенося вероятность р в вершину, из которой исходило это ребро, получим новое кодовое дерево. Этому преобразованию соответствует переход от схемы 2 к схеме 2', если заменить в 2 элементарный код В на В'. Очевидно,
/ср = ^ср Р ^ ^ср*
2, Перемещение ребер из последнего яруса в вершину кодового дерева, которая не является насыщенной. Пусть кодовое дерево в последнем 1-ы ярусе содержит не мепее двух ребер. Значит, существует ребро, концевой вершине которого приписана вероятность р(р>0), и некоторый элементарный код В, Пусть, далее, имеется вершина, расположенная в V-м ярусе (Г < / — 1) и не являющаяся насыщенной. Обозначим через В0 слово, соответствующее этой вершине. Из ненасыщевности вершины следует, что существует СИМВОЛ Ь), ДЛЯ которого В°Ъ) не является префиксом никакого элементарного кода. В этом случае можно упомянутое ребро последнего яруса перенести в данную ненасыщенную вершину по направлению /. Таким образом, заменяя элементарный код В на ВпЬ1г мы получаем из схемы 2 схему I':
^ср = ^ср — р1 -р р (I (5°) -р 1) ^ 1Ср.
Преобразования 1 и 2 позволяют любой префиксный код из рассматриваемого класса, в том числе н код с минимальной избыточностью, привести к коду, дерево которого является^ насыщенным, не увеличивая при этом среднюю длину. Лемма доказана.
Пример 11. Используя преобразования 1 и 2, кодовое дерево, изображенное на рис. 41, можно преобразовать в дерево, которое является насыщенным (рис. 14).
Найдем величину /ср для этого кода:
?сР = .0,22 + 0,20 + 2(0,14 -р 0,11 -р 0,10 + 0,09 4 -р 0,08 + 0,06) = 0,42 + 2-0,58 = 1,58.
Средняя длина данного кода мепьше исходного.
Замечание. Рассмотрим код с минимальной избыточностью, кодовое дерево которого насыщено. Возьмем пучок ребер последнего пруса, идущих из исключи-
Ч. IV. ГШ^йЛ ЛиДШг'и15АИ1'1И
тельной вершины (см. определение на с. 279). Если такой вершины нет, то возьмем произвольный пучок в последнем ярусе. Пусть д0 — число ребер во взятом пучке, 2 < д0 ^ Я. В силу следствия вершинам из последнего яруса приписаны вероятности Рт-тп+и • ••» Рт, где тп > до, либо равные им вероятности (это ВОЗМОЖНО при рг-,п — рг-т+О . Поэтому путем перестановки элементарных кодов максимальной длины и элементарных кодов, соответствующих одинаковым вероятностям (равным Рг-т+1), можно добиться того** чтобы концевым вершинам взятого пучка были приписаны вероятности
Рг-др-Ь 1» • • •} Рт.
Полученный код будем называть приведенным.
Таким образом, имеет место
Теорема 7. Среди кодов с минимальной избыточностью существует приведенный код, причем определяется в соответствии с (5).
Данное утверждение позволяет явно указать набор из #0 вероятностей рг~Яо+1, ..Рп соответствующий одному из пучков ребер последнего яруса кодового дерева для некоторого кода с минимальной избыточностью. Так, для примера 10 при г = 8, <7 = 4 находим
8 = 3? + Уо
и, пользуясь (5), получаем ( = <д> = 2. Значит, выделенному пучку приписаны вероятности р7 и
Рассмотрим кодовое дерево произвольного префиксного кода и в нем произвольную концевую вершину. Обозначим приписанную ей вероятность через р. Заменим эту концевую вершину пучком из 5 ребер ($<д), приписав НОВЫМ концевым вершинам вероятности Ргх, . . ., так, чтобы выполнялось равенство
Р = Р'ч + • * * + Р V (б)
Иными словами, вместо элементарного кода В, соответствующего рассматриваемой вершине, мы включим в код в элементарных кодов ВЪ^, ...,ВЬ^. Будем говорить в этом случае, что исходный префиксный код преобразуется
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ 283
в другой префиксный код путем замены концевой вершины пучком ребер. Легко видеть, что средняя длина /ср первого из этих кодов связана со средней длиной/Ср второго кода равенством
lev ~ lev + Р' (7)
Теорема 8 (редукция). Пусть один префиксный
код преобразуется в другой путем замены в кодовом дереве концевой вершины пучком из s ребер. Далее, пусть концевым вершинам кодового дерева второго кода приписаны вероятности
