Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Nlk (К)
LK
LK
-H(U)
>8
>e
= 0.
= 0.
3.11. Двумя такими кодами будут {00, 01, 02, 10, 11, 12} и {00, 01, 02, 10, 11, 120, 121}. Общее правило состоит в том, чтобы вначале сгруппировать два наиболее вероятных сообщения, если алфавит источника имеет нечетное число букв, и сгруппировать три наиболее вероятных сообщения, если число букв четное. Затем используется процедура Хаффмана с D = 3 до тех пор, пока приведенный ансамбль не будет иметь только два сообщения, и в этом месте используется процедура Хаффмана с D = 2. Этот алгоритм можно обосновать точно так же, как обосновывается обычная процедура Хаффмана; единственное отличие состоит в том, что полное дерево с самой низкой двоичной точкой ветвления концов ребер и последующими троичными точками ветвления имеет четное число концевых узлов.
3.12. Заметим, что если кодовое слово в коде, обладающем свойством префикса, инвертируется (т. е. слово х= х1х2х3х1 заменяется на х^хъх2х-^), то результирующий код удовлетворяет свойству суффикса. Код, удовлетворяющий свойству суффикса, должен быть однозначно декодируемым, так как если бы это было не так, то две последовательности кодовых слов с одними и теми же кодовыми буквами можно было бы инвертировать и получить неоднозначно декодируемую последовательность для соответствующего кода, обладающего свойством префикса. Код, обладающий свойством суффикса и имеющий минимальную среднюю длину, может быть построен с помощью отыскания кода Хаффмана на первом этапе и последующей инверсией кодовых слов (эта последняя операция не меняет среднюю длину).
3.13. Двумя такими кодами будут {00, 01, 02, 10, 11, 12, 20, 21} и {0,20, 21,.10, 11, 12, 220, 221}. Оба они имеют среднюю длину 2, но дисперсия длины для первого кода равна 0, а для второго — равна 0,4. Очевидным преимуществом первого кода является то, что при его использовании не возникает проблема ждущей очереди.
3.14. (а) Из (3.3.5) и (3.3,6) следует, что Н (U) = п log2 3 тогда и только тогда, когда неравенство
log
Р (ak)
(loge)
— 1
Р(Ч)
удовлетворяется при всех k. Это, в свою очередь, происходит лишь тогда, когда 3-** = Р (ak).
(б) Если Р (а*) = 3—для всех k, то неравенство Крафта удовлетворяется с равенством. Вместе с тем, если число сообщений является четным, то кодовое дерево не является полным и при этом еще одно кодовое слово могло бы быть добавлено без нарушения неравенства Крафта. Поэтому число сообщений должно быть нечетным.
587
3.15. (а) Существуют, по крайней мере, два кодовых слова самой большой длины. Если бы длина самого короткого слова отличалась от этой наибольшей длины больше'чем на'1, то можно было бы уменьшить длину двух длинных слов на 1 и увеличить длину самого короткого слова на 1 без нарушения неравенства Крафта. Это бы привело к коду, средняя длина которого была бы меньше, чем для первоначального кода, и это противоречит предположению, что первоначальный код был кодом Хаффмана. Таким образом, наибольшая и наименьшая длины отличаются не более чем на 1 и согласно неравенству Крафта длины должны быть равны / и / + 1.
(б) Пусть L является числом слов с длиной /. Согласно неравенству Крафта, которое должно удовлетворяться с равенством для двоичного кода Хаффмана, имеем
(в)
L2~;-\-(x2/—L) 2~j~1= 1, L = (2 —x)2i. L . x2j— L . , . 2(x — 1)
n~ о;/ H- 0; (/¦$•!)—/ +
x2J x2J x
3.16. Пусть и ак будут объединены в ансамбле U, что даст редуци-
рованный ансамбль U'. Тогда
Н (U)-H (U')= —Р(ак__ j) log Р(ак_{)—Р(ак) log Р(ак) +
+ [P(“/<-l) + P(aK)] IoS [P(a/<-l)+ Р(ак)] =
1 1 9 log— + (1 — д) log-
где q
= [Р )+РК)] ¦Р (аК)
ч
1— q
р (ак-\)+р{ак)
В предположении, что логарифмы берутся по основанию 2, энтропия, которая была выписана выше, не больше чем 1, поэтому
Н (U) - H(U') < Р (ак_ j) ¦+.Р (ак).
Так как оптимальный код для U может быть построен из оптимального кода для V с помощью добавления концевых 0 и 1 к последнему кодовому слову, то
п-п=Р(ак_1) + Р(ак).
Объединяя эти результаты, получаем п—Н (U) > nf—Н (Uf).
3.17. (а) Префиксный код может быть использован на последнем этапе кодирования, и если это так, то все этапы, очевидно, являются однозначно декодируемыми и, следовательно, весь код целиком является однозначно декодируемым.
(б) Указанные последовательности источника имеют вероятности 0,1; (0,9)-(ОД); (0,9)40,1); (0,9)7 - (0,1); (0,9)8. Поэтому
8
т= 2 г (0,1) (0,9У-гЧ-8 (0,9)8 = 5,6953.
; = 1
(в) й^ = (0,9)8 + 4 (1 —0,98) = 2,7086-
(г) Пусть N (/) является числом символов источника, порождающих первые г промежуточных символов. Для любого г > 0 имеем
