Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 77

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 71 72 73 74 75 76 < 77 > 78 79 80 81 82 83 .. 104 >> Следующая

Pu • ? Рг*
причем концевым вершинам указанного пучка — вероятности
ph,".,pis
г. е. концевым вершинам кодового дерева первого кода — вероятности
Pli • • Рц —1> Pi\+li * ‘ •> Pi$~ 1» Pis+l»' * • Pri Pt
где p — определяется равенством (6). Тогда справедливо следующее.
I. Если второй код имеет минимальную избыточность, то первый код также имеет минимальную избыточность.
II. Если первый код имеет минимальную избыточность и при этом выполнены условия
Pi>...>Pr,
s = q0,
где q0 определяется в соответствии с (5), и Pii = Pr—g0+ H
Pis = Pr
(P = Pr-q^i + ... + Pr),
то второй код также имеет минимальную избыточность.
Доказательство. Обозначим среднюю длину первого кода через J?P? а среднюю длину второго
284
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
кода — череа/ср- Для них равеиство (7) принимает вид
4 - 4 + р. (8)
I. Предположим, что первый код пе обладает минимальной избыточностью. Обозначим среднюю длину кора с минимальной избыточностью при тех же вероятностях через 4- По предположению
4<Йр- (9)
Заменив в кодовом дереве этого кода концевую вершину, которой приписана вероятность р, пучком из $ ребер, мы получим код со средней длиной 4, удовлетворяющей соотношениям (см. (7), (9) и (8)):
4— 4+ 4 Р = 4*
Но это противоречит минимальной избыточности второго кода. Утверждение I доказано.
II. Предположим, что второй код не обладает минимальной избыточностью. Обозначим среднюю длину кода с минимальной избыточностью при тех же вероятностях через 4- По предположению
йр<г?р. (10)
Можно считать, что этот код является префиксным (следствие 2 из § 3) и даже приведенным (теорема 7). Но тогда в его кодовом дереве есть пучок из дй ребер, концевым вершинам которого приписаны вероятности рг_д0_|.1г .рт. Заменив этот пучок концевой вершиной,
мы получим код со средней длиной 4і удовлетворяющей соотношениям (см. (7), (10) и (8)):
4> ~ 4 Р <-' ^ср Р = ?с-р*
Но это противоречит минимальной избыточности первого кода. Утверждение II доказано, а с ним доказана и теорема.
Утверждение I показывает, что при построении кода с минимальной избыточностью из более простого кода необходимо, чтобы этот код также имел мипимальную избыточность. Однако этого, вообще говоря, недостаточно. Достаточные условия содержит утверждение II,
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
285
Теорема 8 дает алгоритм построения кодов с мипи-малыюй избыточностью. В этом алгоритме сначала производится мысленное свертывание искомого приведенного кода, в процессе которого один за другим получаются все более простые коды, обладающие минимальной избыточностью, и в конце концов — код из одпобуквен-ных элементарных кодов. Реально это означает преобразование списка вероятностей в соответствии с утверждением II до тех пор, пока не получится список вероятностей, для которого код с минимальной избыточностью находится тривиально. После этого найденный код развертывается в соответствии с утверждением II в последовательность кодов с минимальной избыточностью, которая заканчивается искомым кодом.
При более формальном описании алгоритм удобно разбить на 4 этапа. (В тривиальном случае г < q остается только 8-й этап.)
1-й этап. С помощью (5) определяется q0.
2-й этап. Первый шаг. Список вероятностей ри ... ,.рг (р} 5=... 5* рт) заменяется списком вероятностей
Pit • • *1 Pr- V Pi где р = Рг-дслЛ + ... + Рп который
после упорядочивания превращается в список ри ..ph р,
Pj+it ? ? ч Pr—g0 (.Pi ^ ^ Pi ^ Р 7^ Pj+1 * ^Рг—д0У
Второй и все последующие шаги 2-го этапа выполняются совершенно аналогично с той лишь особенностью, что для них всегда q0 = q (после первого шага в кодовом дереве ненасыщенных вершин не остается).
Выполнение 2-го этапа заканчивается, когда число вероятностей в списке становится не больше q.
3-й этап. Для списка, содержащего не более, чем q вероятностей, строится префиксный код с минимальной избыточностью. Очевидно, что таким кодом является любой код, состоящий из однобуквенных элементарных кодов.
4-й этап. Первый шаг. В соответствии с теоремой о редукции производится переход от кода с минимальной избыточностью при вероятностях из последнего списка к коду с минимальной избыточностью при вероятностях из предпоследнего списка.
Остальные шаги 4-го этапа выполняются совершенно аналогично п завершаются построением искомого кода С минимальной избыточностью.
Приведем несколько примеров.
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
Пример 12. Пусть г = 4, # = 2 и щ = 0.40, р2 — >=0,25, />8 = 0,20, /ц = 0,15. Возьмем © = (0, 1>. В случае двухбуквенного алфавита дй ~ 2 п процесс построения можно представить следующим образом:
Рх 0., 40 - 0,40 —>
->0,35" 0
Р* 0,25 0,25, 1
РИ 0,20" 0
Рх 0,15_ т
~0,00‘
0,40
Мы имеем два шага, связанные с редукцией. Квадратными скобками отмечены объединяемые члены. Для построения кодов нужно для каждой скобки выбрать взаимно однозначное соответствие мея;ду вероятностями и подмножеством символов из 0,
В нашем случае верхнему числу сопоставим 0, нижнему — 1. Затем осуществляем движение в обратном направлении к символам ри ..., рг и, проходя скобки, выписываем соответствующий код. Например, путь
Предыдущая << 1 .. 71 72 73 74 75 76 < 77 > 78 79 80 81 82 83 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed