Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
аг ВГг
обладающих свопстеом взаимной однозначности. В частности, всегда можно взять в качестве кодов Ви .,Д, различные слова в алфавите 33 одинаковой длины I, где
I = ]1ояД
Для каждой схемы 2 можно ввести среднюю длину /ср, определяемую как математическое ожидание длины элементарного кода, т. е.
/ср = 2 Р/гI Ц = I (^г)-
Очевидпо, что величина /ср (/ср 3» 1) показывает, во сколько раз увеличивается средняя длина слова при кодировании со схемой 2.
Пример 9. Пусть г = 4, д = 2 и р1 = 0,40, рг — 0,25, Ръ => 0,20, р4 = 0,15.
Рассмотрим две схемы алфавитного кодирования:
04 00, а( 1,
0-2 01, /У'Ч 01, /пв\'
03-10, йз-000, & )
а* —И, 04 — 001.
Они, очевидно, обладают свойством взаимной однозначности. Найдем их средние длины
/сР - 2, СР - 0,40 + 2 ? 0,25 + 3 • 0,35 = 1,95,
Ч. IV, ТЕОРИЯ КОДИРОВАНИЯ
277
Таким образом, средняя длина может изменяться при переходе от одной схемы алфавитного кодирования к другой, Ввиду этого для данного источника сообщений можно ввести величину /*, где
= ^ср*
X
(Здесь нижняя грапь берется по всем схемам 2, обеспечивающим свойство взаимной однозначности.)
Легко видеть, что
1 < h < ] bg,.r [
(верхнюю оценку дает равномерное кодирование). Отсюда видно, что для построения кодов, у которых величина ?ср близка к I*, можно не учитывать коды с /ср большим, чем ]loggr[. Значит, для таких схем
рМ < ]logs r[.
Поскольку при вычислении 1Ср члены с р = 0 не играют роли, то, положив р* — min pi]t имеем
I
p*
ДЛЯ всех I, ДЛЯ которых Pi^O, и, значит, имеется конечное число вариантов значений lcpt для которых ^/ср ^ ]log4r[. Следовательно, величина достигается на некотором 2 н может быть определена как
min Icp. х
Определение. Коды, определяемые схемой 2 с hy называются кодами с минимальной из бы точностью, или кодами Хафмана [41].
Очевидно, что коды с минимальной избыточностью дают в среднем минимальное увеличение длин слов при соответствующем кодировании. Ввиду этого представляет интерес задача о построении кодов с минимальной избыточностью.
Замечание. В силу следствия 2 из § 3 существует алфавитное кодирование со свойством префикса, дающее коды с минимальной избыточностью. Ввиду этого при построении кодов с. минимальной избыточностью
278
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
можно ограничиться рассмотрением кодов, обладающих свойством префикса.
Теперь перейдем к вопросу о построении кодов с минимальной избыточностью. Каждому алфавитному кодированию со свойством префикса можно сопоставить кодовое дерево. На примере покажем, каким образом это делается.
Пример 10. Пусть задана схема 2 следующего ви-да (г = 8, ^ = 4):
щ - ЬуЬз р1 = 0,22
а2 — Ь3 Рг = 0,20
а3 ЪхЬ\ Рз = 0,14
щ - ь,ь2 Рь = 0,11
«5 - ЬиЬ2Ь3 Рь = 0,10
св — Ь,Ь 4 Ръ = 0,09
С7 — ь^ь± Р-1 = 0,08
Се Ъ^Ь2Ь^ Ръ = 0,06.
Очевидно, данная схема определяет код со свойством префикса и
гср - 0,20 + 2(0,22 + 0,14 + 0,11 + 0,09 + 0,08) + + 3 (0,10 + 0,06) = 0,20 + 2 • 0,64 + 3 - 0,16 = *= 0,20 +1,28 + 0,48 = 1,96.
Элементарные коды определяют дерево (см. рис. 11). Концевым вершинам этого дерева соответствуют элементарные коды, определяемые путем (ветвью), идущим из корня, и им приписаны вероятности появления элементарных кодов. Легко видеть, что кодовое дерево, у которого концевым вершинам приписаны вероятности, задает схему алфавитного кодирования со свойством префикса.
Сначала рассмотрим частный случай задачи, именно, когда среди чисел ри ..рг имеется не более одного, равного нулю. Без ограничения общности можно считать, что
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
Лемма 1. Для кода с минимальной избыточностью из условия рз < рг следует, что I, > и.
Доказательство. Предположим противное, т. е. Р}< Ри а Ь < и. Тогда, если в схеме для кода с минимальной избыточностью:
• • ?
— Ви
. . - (2):
а} - Вь
поменять местами элементарные коды 5* и Ви мы получим схему
(к — Вь
. . • (П
й^ — Ви • * *
имеющую меньшую среднюю длину /срг чем для схемы 2. В самом деле,
/ср - /ср = СРгЬ + Р&) — (Р& + М) =•
— (а - а) & - Ч > °<
Последнее противоречит минимальной избыточности
2. Лемма доказана.
Следствие. В кодовом дереве для кода с минимальной избыточностью вероятности, приписанные концевым вершинам из 1'-ео яруса, не меньше, чем вероятности, приписанные концевым вершинам из I"-го яруса, если I" > V,
Далее будем рассматривать конечные деревья с максимальным порядком ветвления (числом исходящих из вершин ребер) ц.
Определение. Неконцевая вершина дерева называется насыщенной, если ее порядок ветвления равен ?. Конечное дерево называется насыщенным, если в нем насыщены все неконцевые вершины, за исключением, быть может, одной, лежащей в предпоследнем ярусе, и порядок ветвления этой исключительной вершины равен у0, где 2 < д0 < у.
В случае, когда в насыщенном дереве нет исключительной вершины, будем считать, ЧТО Уй~ у (роль ис-
280
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
ключительной вершины в этом случае может играть любая пеконцевая вершина пз предпоследнего яруса).
Покажем, что по числам г яд число определяется однозначно. С этой целью заданное насыщенное дерево будет преобразовано в другое насыщенное дерево, имеющее определенную структуру и связанное с исходным деревом только тем, что у него то же число концевых и то же число внутренних вершин. Один шаг преобразования
