Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(б) Каждый повисший суффикс, сформированный на первом этапе процедуры, должен быть суффиксом кодового слова. Каждый повисший суффикс, который сформирован далее, является либо суффиксом кодового слова, либо суффиксом некоторого ранее сформированного повисшего суффикса. С помощью индукции получаем, что каждый повисший суффикс является суффиксом кодового слова (т. е. если все повисшие суффиксы, найденные вплоть до данного момента, являются суффиксами кодового слова, то следующий повисший суффикс должен быть подобным же). Исключая тривиальный случай кодовых слов из повторений или нулевой длины, получим, что для кодового слова длины т* существует не более т,- — 1 суффиксов этого кодового слова, которые могут появляться как повисшие суффиксы. Следовательно, общее число повисших суффиксов, которые могут появиться, ограничено сверху величи-
(в) Все перечисленные коды, кроме (0, 01, 10}, являются однозначно декодируемыми.
(г) Для кода (0, 01, 11} последовательность 01111111... может быть разложена на аъа3, а3, ... или а2, а3, а3, ... Для кода {110, 11, 100, 00,10} последовательность 11000000... может быть разложена на alt а4, а4, ... или а2, а4, а4, ... Такие последовательности не могут быть построены для других однозначно декодируемых кодов.
j q 1,146 • ю10
%А< Ю1-149'1010
для пункта (б).
м
ной 2 (mi — !)• i=l
585
3.5. (а) {00, 01, 100, 101, 1100, 1101, 1110, 1111).
(б) Заметим, что для любых k > /
Qk~Qi= *2 P(°l)> P(ai)>2-ni-
I =/
Поэтому кодовые слова для aj и aj должны отличаться где-либо в первых и, позициях, и так как оба они имеют длину, по крайней мере, tip то имеет месте свойство префикса. Далее для каждого i имеем
— lOgP(dj) < п;< — log Р(аг)ф1.
Умножая на Р(aj) и суммируя по г, получаем Н (U) < п<^Н (U) +1.
3.6. Для любых k > j теперь имеем
к —1 j 1 Qh— Qj = 2 Р (ai) “Г" Р (aj)~h Р (ак) >
г=/+1 z
> Р (aj) + Р (ak) >2-nj+2-nk.
Поэтому кодовые слова должны отличаться в первых rij или щ символах в зависимости от того, какое из этих чисел меньше. Отсюда следует, что свойство префикса удовлетворяется и код является алфавитным. Так как Ш < — log Р (аг-) +2, то, усредняя по г, получаем п < Н (U) + 2.
3.7. (а) Если код является однозначно декодируемым, то при любом k первые k кодовых слов должны образовывать однозначно декодируемый код и на основании доказанных теорем
к _
2j D 1 1 при любых k•
/= 1
Так как левая сторона неравенства увеличивается с ростом k и ограничена
1, то предел существует и ограничен 1. Обратно, при заданном бесконечном множестве длин, которые удовлетворяют неравенству Крафта, можно использовать построение, выполненное в теореме 3.2.1, чтобы построить код, обладающий свойством префикса. Здесь необходимо сделать два замечания. Первое состоит в том, что так как неравенство Крафта удовлетворяется, то существует конечное множество слов каждой длины tit и поэтому длины могут быть упорядочены; второе состоит в том, что следует начинать (методически) с полного бесконечного дерева.
(б) Теорема 3.3.1 следует из теорем 3.2.1 и 3.2.2 при К = оо точно так же, как это было при конечном К¦ Заметим, однако, что если значение Н (U) бесконечно, то средняя длина кодового слова также будет бесконечной.
3.8. Пусть Р (а2) = 1 — б, Р (а2) = б. Код с этими сообщениями декодируется однозначно только тогда, когда оба слова имеют длину, по крайней мере, равную 1, так, что п > 1. Вместе с тем при 6^0 имеем Н (U) -> 0, так что для любого е > 0 и для достаточно малого б имеем п > H(U)+ 1-е.
3.9. Двоичным и троичным кодами для первого источника будут {00, 10, 010, 011, 110, 111} и {0, 10, 11, 12, 20, 21}. Средние длины равны 2,5 и 1,7. Эти коды не являются единственными, а средние длины однозначно определенными. Кодами для вторичного источника будут {00, 10, 010, 110, 111, 0110, 0111} и 10, 1, 20, 21, 220, 221, 222}. Средние длины равны 2,55 и 1,65.
3.10. (a) Nl является суммой длин L кодовых слов, соответствующих L буквам источника. Поэтому NL представляет собой сумму L независимых одинаково распределенных случайных величин, каждая из которых имеет среднее значение п = 2,5. Таким образом, на основании закона больших чисел искомый предел равен 2,5, или в более точной формулировке, для любого е > 0 имеем
586
lim Pr
L-± oo
nl — —2,5 L
> s
= 0.
(б) На основании теоремы 3.3.2 получаем
Hm Nlk iKl = H(U),
K-+°° LK
а также, используя те же рассуждения, что и в пункте (а), получаем
lim Рг
L—> оо
Nlk (*) _ nlk (К) LK
Поэтому
lim lim Pr К-*-00 J_~+oo
