Файл: Бовбель, Е. И. Элементы теории информации.pdf

Наконец, предположим, что условие (3.31) не выполняет­ ся. В этом случае для достижения нижней границы (3.32) кодовое слово необходимо сопоставлять не каждому со­ общению, а группе сообщений.

где P ( y k) — вероятность осуществления /е-й группы сооб­ щений из пк возможных групп, удовлетворяют теореме Крафта, то группам уи. можно сопоставить кодовые слова длиной (і£. Умножив обе части неравенств (3.33) на P(tjk) и просуммировав по всем k от 1 до /г*, получим

где Lk—: средняя длина кодовых слов, сопоставляемых группам сообщений уь; H(Y)— энтропия множества групп Ук‘ Разделив (3.34) на k с учетом того, что H(Y)=kH(X). получим:

При достаточно большом k из последнего неравенства средняя длина кодового слова L = Lkjk, приходящегося на одно сообщение Xk,

что и требовалось доказать.

Только что доказанная теорема не дает явных рецеп­ тов для нахождения кодовых слов со средней длиной H(X)/\ogm. Поэтому она является теоремой существо­ вания.

Важность этой теоремы состоит в том, что она опреде­ ляет предельно возможную экономность кода, позволя­ ет оценить, насколько тот или иной конкретный код бли­ зок к самому экономному, и, наконец, придает прямой физический смыслодному из основных понятий теории информации — энтропии множества сообщений как мини­ мальному числу двоичных символов (см. 3.35, т = 2), приходящихся в среднем на одно сообщение.

76

Хотя теорема о кодировании не указывает конкретный способ построения оптимальныхкодов, однако из нее вы­ текает, что для достижения минимальной средней длины кодового слова необходимо стремиться к тому, чтобы ко­ довые символы были равновероятными и статистически независимыми друг от друга. Приведем два известных способа построения кодов, которые позволяют прибли­ зиться к равновероятности и независимости кодовых сим­ волов.

1. Код Шеннона — Фано. Для составления этого кода все сообщения х t (i = 1,2, ..., п) выписываются в порядке убывания их вероятностей (табл. 13).

Записанные так сообщения затем разбиваются на две по возможности равновероятные подгруппы. Всем сообще­ ниям, входящим в первую подгруппу, приписывают циф­ ру 1 в качестве первого кодового символа, а сообщениям, входящим во вторую подгруппу,— цифру 0. Аналогичное деление на подгруппы продолжается до тех пор, пока в каждую подгруппу не попадет по одному сообщению.

Убедимся, что таким образом найденный код весьма

близок к оптимальному. В самом деле, энтропия сообще- 6

ний Н(Х) = —'2lP(xi)\ogP(xi)^2J5, а средняя длина ко- /«1

77

стей. Две наименьшие вероятности объединяют скобкой (табл. 14) и одной из них приписывают кодовый символ 1, а другой 0. Затем эти вероятности складывают, ре­ зультат записывают в промежутке между ближайшими вероятностями. Процесс объединения двух сообщений с наименьшими вероятностями продолжают до тех пор, пока суммарная вероятность двух оставшихся сообщении не станет раиной единице. Код для каждого сообщения строится при записи двоичного числа справа налево путем

Каждому сообщению xt: поставим в соответствие чис­ ло Qi, определяемое следующим образом:

Qi < 1 .

Представим эти числа в виде двоичной дроби. Так как

Qi < 1, то

Qi = <7—L2 1 + (J_2 2 2 + <7_з 2—3 + ...

7.8

Разложение каждого Qt продолжается до тех пор, пока число членов разложения \ц не окажется в пределах

Iog Р(хі) ^ w ^ 1 + 1о§ Р{Хі) *

Остальные члены разложения отбрасываются. Таким об­ разом, каждому сообщению xt сопоставляется двоичное число (код) у 1г содержащее ^ членов: Qi~q__x<7_2?_3 ...

q = уі, где Рі определяется выражением (*).

Поясним процедуру коди розап ия на предложейиом выше примере. Результаты расчетов сведем в табл. 15.

Задача 1. Независимые сообщения Х\, х% ,ѵ3, Х\ появ­ ляются соответственно с вероятностями 1/2, 1/4, 1/8, 1/8 и кодируются по методу Шеннона — Фано: 0,10, ПО, 111. Показать, что в получающейся последовательности кодо­ вых слов символы «0» и «1» встречаются с равными ве­ роятностями.

Р е ш е н и е . Вероятность символа «0» определим как отношение среднего числа сим-волов «0» в кодовых словах к средней длине кодового слова:

£ «оР(хі)

Аналогично Р (1)'=1/2, что и требовалось-показать. Задача 2. Источник независимо друг от друга выраба­

тывает два различных сообщения Х\ и х<і с вероятностями

80