Р ис.2.4. Двоичное кодовое дерево для кода примера 2.19

Рис. 2.5. Троичное кодовое дерево

(2.133)

Рассмотрим вначале необходимость.. Тем не менее, мы снова докажем необходимость для префиксных кодов, поскольку доказательство является очень простым, но поучительным. Предположим, что существует кодовое дерево, концевые узлы которого имеют указанные порядки. Покажем, что при этом выполняется неравенство (2.133). Заметим, что максимальное количество узлов на ярусе j равно D^j. Пусть m=max{ т₁,…,т_M }. Рассмотрим концевой узел порядка т_i. Этот узел отстоит от яруса т на m—т_i ребер и, следовательно, исключает из этого яруса возможных узлов (см. рис. 2.4).

Так как количество узлов, исключаемых из яруса m всеми концевыми узлами порядков т₁,…,т_M не может превосходить максимального количества узлов на этом ярусе, то

(2.134)

Отсюда после деления обеих частей неравенства на D^m следует (2.133).

Докажем теперь достаточность. Для этого следует доказать, что при выполнении (2.133) дерево с концевыми узлами порядков т₁,…,т_M может быть построено. Предположим, что среди этого набора порядков число s встречается точно _S раз, s = 1, 2, ..., m. Тогда

(2.135)

Перепишем это неравенство следующим образом:

(2.136)

Тогда

(2.137)

Применим метод полной индукции. Дерево, содержащее ₁ концевых узлов порядка 1, может быть построено. Действительно, из (2.135) следует, что ₁D^1  1, т. е. ₁  D . Так как максимальное возможное количество концевых узлов порядка 1 есть D , а ₁  D, то дерево с ₁ концевыми узлами порядка 1 может быть построено.

Предположим, что дерево с _S концевыми узлами порядка s, s=1, 2, ..., i—1, может быть построено. Докажем, что к этому дереву можно добавить еще _i концевых узлов порядка i. Если верно предположение индукции, то из яруса порядка i исключаются возможных концевых узлов. Так как максимальное количество возможных концевых узлов в этом ярусе равно Dⁱ ,то Dⁱ— есть количество свободных узлов на ярусе i. Из (2.137) следует, что количество _i узлов на ярусе i, которые должны быть добавлены, не превосходит количества свободных узлов. Следовательно, к дереву с _S концевыми узлами порядка s, s = 1, 2, ..., i—1, могут быть добавлены _i концевых узлов порядка i . Теорема доказана.

2.12. Неравномерное кодирование дискретных стационарных источников

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

Пусть {Х, р(Х)}, X ={х₁,…, х_M}, — произвольный дискретный ансамбль сообщений и Н(X) — его энтропия. Обозначим: — средняя длина D-ичного кода, , слова которого сопоставляются сообщениям ансамбля X.

Т е о р е м а Для любого кода со свойством однозначного декодирования

(2.138)

Из определения средней длины кодовых слов имеем

(2.139)

Рассмотрим разность H(X) — logD:

(2.140)

В результате получим, что

(2.141)

где последнее неравенство является следствием того, что код обладает свойством однозначного декодирования. Теорема доказана.

Первое неравенство в (2.141), так же как и второе, обращается в точное равенство, если

i = 1, 2, ...,М (2.142)

Таким образом, если вероятности сообщений являются целыми отрицательными степенями числа D (2.12.5), то существует D-ичное дерево с концевыми узлами порядков т₁,…,т_M и соответствующий D-ичный код будет иметь среднюю длину

(2.143)

т. е. равную нижней границе. Коды, для которых средняя длина кодовых слов (и соответственно скорость кодирования) равна наименьшему возможному значению, называются оптимальными. Этим рассуждением мы показали, что в случае, когда вероятности сообщений есть целые отрицательные степени числа D, средняя длина оптимального D-ичного кода совпадает со своей нижней границей. Такой код сопоставляет сообщению x_i слово длины — log р ( x_i ) / log D.

Т е о р е м а Существует D-ичный код со свойством однозначного декодирования, для которого

(2.144)

Пусть — наименьшее целое число, удовлетворяющее условию , где I (x_i)=—log p(x_i) — собственная информация сообщения x_i, i = 1, 2, ..., М. Очевидно,

(2.145)