книги из ГПНТБ / Бовбель, Е. И. Элементы теории информации

сообщением, чтобы на входе линии связи кодовые симво­ лы встречались одинаково часто.

Р е ш е н и е. По формуле

70

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

L = 2 Ѵ-і Р(хі)> ■

/=1

где \}<і — длина кодового слова, сопоставляемая .ѵ/ сооб­ щению.

Общие положения теории информации позволяют ука­ зать оптимальные границы для средней длины L кодовых слов, которые ни при каком кодировании не могут быть уменьшены. Установим эти оптимальные границы для L из следующих соображений. Во-первых, количество ин­ формации, несомое кодовым словом, не должно быть меньше количества информации, содержащегося в соот­ ветствующем сообщешіи, иначе при кодировании будут происходить потери в передаваемой информации. Во-вто­ рых, кодирование будет тем более экономичным, чем большее количество информации будет содержать в себе каждый кодовый символ; это количество информации максимально, когда все кодовые символы равновероят­ ны, и равно logm. При этом і-е кодовое слово будет нести

Так как правая часть неравенства (3.22), как правило, не является целым числом, для достижения знака равенст-. ва в нем (с учетом экономности кода) необходимо, чтобы

72

где квадратными скобками обозначена целая часть числа, стоящего в них. Усредняя (3.23), получаем

- щ х у

LШІП< log т

Таким образом,

Осталось, однако, невыясненным, будут ли кодовые слова, удовлетворяющие неравенствам (3.24), неперекрываемы. Поэтому докажем последнее неравенствострого. _

ходимым и достаточным условием существования иеперекрываемых кодовых слов с заданными-длинами является выполнение неравенства

./г</7гг — lxmr 1 — l2mr 2 — ... — /г_і/7г.

Эти условия являются необходимыми и достаточными для неперекрываемости кодовых слов. Разделив послед­ нее неравенство на тг, получим

ется доказать, что всегда можно найти кодовые слова с длинами [аь которые неперекрываемы.

Легко перейти от неравенства (3.29) к неравенству (3.27). Фиксируя в (3.27) верхний предел суммы /*= 1, по­

Ілт~{ + 12т~2< 1

или

U К гіі2 — l\tn = т(т — /і).

Аналогично получим остальные неравенства (3.26), кото­ рые указывают на неперекрываемость заданных кодовых слов.

условии отсутствия шумов, средняя длина кодового сло­ ва не может быть меньше, чем Н(X)/log т, где Н(Х) — энтропия сообщений. Если вероятности сообщений не яв­ ляются целочисленными отрицательными степенями числа т, точное достижение указанной границы невозможно, но при кодировании достаточно длинными группами к этой границе можно сколь угодно приблизиться.

74

Д о к а з а т е л ь с т в о . Так как для любых двух рас­ пределений вероятностей р(хк ) и q(xk) выполняется не­ равенство

(3.30)

k=i

то, взяв в качестве

У=і В правой части последнего равенства под знаком лога­

рифма стоит сумма, которая на основании (3.25) меньше единицы. Поэтому

H(X)^L log in

или

Н( X)

log т ’

Если вероятности появления сообщений являются цело-. численными отрицательными степенями числа т, т. е.

75

Наконец, предположим, что условие (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