С.В. Яблонский - Введение в дискретную математику (1060464), страница 41
Текст из файла (страница 41)
44 (равным р„,с), можно добиться того, чтобы концевым вершинам взятого пучка были приписаны вероятности Р~ -вв+и ° ° ° ~ Р ° Полученный код будем называть приведенным. Таким образом, имеет место Теорема 7. Среди кодов с минимальной избыточностью существует приведенный код, причем д, определяется в соответствии с (5). Данное утверждение позволяет явно указать набор из д, вероятностей р, в,+„ ..., р„ соответствующий одному из пучков ребер последнего яруса кодового дерева для некоторого кода с минимальной избыточностью. Так, для примера 10 при г = 8, с7 4 находим 8-32+ ус и, пользуясь (5), получаем !=д, 2.
Значит, выделенному пучку приписаны вероятности р, и р,. Рассмотрим кодовое дерево произвольного префвксного кода и в нем произвольную концевую вершину. Обозначим приписанную ей вероятность через р. Заменим зту концевую вершину пучком из е ребер (2 ~ у), приписав новым концевым вершинам вероятности р;,, ..., р;, так, чтобы выполнялось равенство р-р;,+" + р;.
(6) Иными словами, вместо элементарного кода В, соответствующего рассматриваемой вершине, мы включим в код в элементарных кодов Вб;,, ..., Вд;, Будем говорить в этом случае, что исходный префнкспый код преобразуется ч. »т. ТЕОР»»я кодиговятп»я 2зз в другой префпксный код путем замены концевой вершины пучком ребер. Легко видеть, что средняя длина 1„ первого пз этих кодов связана со средней длиной1ср второго кода равенством 1сг 1сг+ Р (7) Теорема 8 (редукция).
Пусть один пре4иксный код преобразуется в другой путем замены в кодовом дереве концевой вершины пучком из г ребер. Далее, пусть концевым вершинам кодового дерева егорово кода приписаны вероятности Р», ° °, Р., причем концевым вершинам указанного пучка — вероятности р;...,., Р», (1(»»(... ч" 1,(т), т. е. концевым вершинам кодового дерева первого кода — вероятности Р»1 ° ° ° » Р»;»~ Р»,г-м ° ° ° ~ Р»;». Рц+» ° ° ~ Р» Р» где р — определяется равенством (6). Тогда справедливо следующее. 1. Если второй код имеет минимальную избыточность, то первый код также имеет минимальную избыточность.
11. Если первый код имеет минимальную избыточность и при етом выполнены условия Ър г Ч0$ где о, определяется в соответствии с (5), и Р',= Р -ге+»» Рц =Р~ (Р Р-е,+»+ ° ° ° +Р1 то второй код также имеет минимальную избыточность. Доказательство. Обозначим среднюю длину первого кода через 1,г, а средню»о длину второго ч. 1т, теОРия кОдиРОВАния кода — через)ср. Для них равенство (7) принимает вид )сз = ~сз+ Р (8) 1. Предположим, что первый код не обладает минимальной избыточностью. Обозначим средню1о длину кода с минимальной избыточностью при тех же вероятно- СтяХ ЧЕРЕЗ (ср.
ПО ПрЕдПОЛОН1ЕНИЮ )ср ( )ср (9) Заменив в кодовом дереве этого кода концевую вершину, которой приписана вероятность Р, пучком из з ребер, мы получим код со средней длиной 1ср, удовлетворяющей соотношениям (см. (7), (9) н (8)): 1сэ 1сз+ Р ( 1сз + Р = )сз. 4 3 с Но это противоречит минимальной избыточности второго кода. Утверждение 1 доказано. 11. Предположим, что второй код не обладает минимальноп избыточностью. Обозначим среднюю длину кода с минимальной избыточностью прн тех же вероятностях через 1ср По предположению )сз (1,'з. (10) Можно считать, что этот код является префнкспым (следствие 2 из 1 3) и даже приведенным (теорема 7).
Но тогда в его кодовом дереве есть пучок из дс ребер, концевым вершинам которого приписаны вероятности Р, те+„..., Р,.Заменив этот пучок концевой вершиной, мы получим код со средней длиной 1ср, удовлетворяющей соотношениям (см. (7), (10) и (8)): 1сз = )сз Р()ср Р = )ср е с с Но это противоречит мннимальной избыточности первого кода. Утверждение П доказано, а с ням доказана и тео ема. тверждение 1 показывает, что при построении кода с минимальной избыточностью из более простого кода необходимо, чтобы этот код также имел минимальную избыточность. Однако этого, вообще говоря, недостаточно. Достаточные условия содержит утвер1кденне 11. ч. 1т.
теоРпя кодпРОВАппя Теорема 8 дает алгоритм построения кодов с минимальной избыточностью. В этом алгоритме сначала производится мысленное свертывание искомого приведенного кода, в процессе. которого один за другпм получаются все более простые коды, обладающие минимальной избыточностью, и в конце концов — код из однобуквенных элементарных кодов. Реально это означает преобразование списка вероятностей в соответствии с утверждением 11 до тех пор, пока не получится список вероятностей, для которого код с мини11альной избыточностью находнтся тривиально, После этого найденный код развертывается в соответствии с утверждением П в последовательность кодов с минимальной избыточностью, которая заканчивается искомым кодом. При более формальном описании алгоритм удобно разбить на 4 этапа.
(В тривиальном случае г ~ д остается только З-й этап.) 1-й этап. С помощью (5) определяется д,. 2-й этап. Первый шаг. Список вероятностей р„... .. „р, (р, ~... ~ р,) заменяется списком вероятностей р„..., р,~, р, где р рг э +, + ... + р„который после упорядочивания превращается в список р„...,р„р, Ь+ ° ° ° р - (р1 ) ° ° ° Ъ'Ю Ъ р ~грз+ Ъ ° ° ° >р~-г,) Второй и все последующие шаги 2-го этапа выполняются совершенно аналогично с той лишь особенностью, что для нпх всегда д, о (после первого шага в кодовом дереве ненасыщенных вершин не остается). Выполнение 2-го зтапа заканчивается, ко1да число вероятностей в списке становится не больше д.
З-й этап. Для списка, содержащего не более, чем д вероятностей, строится префиксный код с минимальной избыточностью. Очевидно, что таким кодом является любой код, состоящий из однобуквенных элементарных кодов. 4-й этап. Первый шаг. В соответствии с теоремой о редукции производится переход от кода с минимальной избыточностью при вероятностях из последнего списка к коду с минимальной избыточностью при вероятностях из предпоследнего списка. Остальные шаги 4-го этапа выполняются совершенно аналогично и аавершаются построением искомого кода с минимальной избыточностью. Приведем несколько примеров, ч. 1у. теогпя кодпРОВАния Пример 12. Пусть г 4, д 2 и р,=0,40, р,= 0,25, р~=0,20, р,=0,15. Возьмем 8 10, 1).
В случае двухбуквенного алфавита д,=2 и процесс построения можно представить следующим образом: -~-0,60 ~0 0,40 !1 0,40 -~ 0,40 -+- Рз '-з-0,35 !О 0,25 -~. 0,25 ! 1 0,20 !О 0,15 ! 1 рз Рз 0 60 — 0,35 — 0,15 — р, дает код 001. Таким образом, мы получаем следующую схему: а,— 1 а, — 0'1, а, — 000, а, — 001, что совпадает со схемой Е" на с. 276. Значит, код определяемый Х", имеет минимальную избыточность. Осуществляя редукцию, на каждом шаге производится упорядочение вероятностей по их величине. Это упорядочение оказывается не всегда однозначным, так как воаможно появление вероятностей, имеющих одинаковую величину. Пример 13. Пусть г=8, д 4 и р,-0,22, р, 0,20, В ' е= з 0~14 ' р~= 0,1 1, р~ 0,10, ра 0,09, рг 0,08, ра 0,06, озьмем 6 (О, 1, 2, ЗЕ Редукцию можно осуществить Мы имеем два шага, связанные с редукцией.
Квадратными скобками отмечены объединяемые члены. Для построении кодов нужно для каждой скобки выбрать взаимно однозначное соответствие между вероятностями и подмножеством символов из 6. В нашем случае верхнему числу сопоставим О. нижнему — 1. Затем осуществляем движение в обратном направлении к символам р„ ..., р, н, проходя скобки, выписываем соответствующий код. Например, путь Ч. 7Ч. ТЕОРИЯ КОДИРОВАНИЯ 287 едесь двумя способами: -в.
0,44 0,22 0,20 0,14 0,22 0,20 -~ 0,14 0,14 р, 0,22 р,-0,20 р, 0,14 0,11 0,10 0,09 р, - 0,11 р, - 0,10 ра 0 09 р, 0,06,Д 0,44 0,22 0,22 0,20 0,20 р, 0,22 ре 0,20 0,14 ре = 0„14 р, - 0,11 р, - 0,10 р,* 009 р,- 0,061 р,-006 ~ две схемы алфавитного кодирования скобках сверху вниа числами О, 1, 2, 3) а,— 1 а,— 2 а,— 3 (Е') а, — 01 (Е") а,— 02 а,— 03 а, — 000 аа 001 Кодовое дерево для Е' совпадает с деревом на рис.
14. Отсюда получаем (нумеруя члены в а,— 1 а,— 2 а,— 00 а,— 01 а,-02 а. — 03 а,— 30 а,— 31 0,14 -+0,14 0,11 0,10 0,09 ч. п~. твогня колш ования В заключение рассмотрим построение кодов с минимальной избыточностью для случая, когда вероятности р„..., р,— произвольны, р, >...>Р,. Если число нулевых вероятностей больше единицы, т. е. Р,,)О и Р,.ь, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
