§ 1.8. Скорость создания информации дискретным источником без памяти при равномерном кодировании

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

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

Предположим, что дискретный источник без памяти выбирает сообщения из множества X с распределением вероятностей для всех и энтропия ансамбля

Теорема 1.8.1 (прямая теорема). Пусть тогда для любого положительного существует код со скоростью

Рис. 1.8.1. К доказательству обратной теоремы кодирования.

Доказательство. Согласно теореме 1.7.1 для любых положительных найдется такое, что для любого вероятность появления на выходе источника последовательности сообщений х, не принадлежащей высоковероятному множеству не превосходит Если выбрать в качестве множества однозначно кодируемых последовательностей, то вероятность ошибки декодирования не будет превышать При этом количество кодовых слов не должно быть меньше числа элементов в множестве Это условие будет удовлетворено, если

откуда следует, что Теорема доказана.

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

Теорема 1.8.2 (обратная теорема). Пусть тогда существует зависящее от положительное число такое, что для каждого кода, кодирующего дискретный источник без памяти со скоростью вероятность ошибки не меньше, чем

Кроме того, для любой последовательности кодов со скоростью

где вероятность ошибки для кода, кодирующего отрезки сообщений длины

Доказательство. Докажем сначала справедливость соотношения (1.8.2). Пусть последовательность высоковероятных множеств. Обозначим через последовательность произвольных множеств таких, что и

Для каждого множество будем рассматривать как множество однозначно кодируемых последовательностей сообщений. Поэтому (см. рис. 1.8.1)

где дополнение множества до и символ пересечения множеств. Из теоремы о высоковероятных множествах следует, что

Рассмотрим теперь вероятность Для всякой последовательности имеем так как при этом Число элементов в множестве не превосходит следовательно,

Учитывая (1.8.5) и (1.8.6), из (1.8.4) получим (1.8.2).

Докажем теперь первое утверждение теоремы. Для этого заметим, что при множество не пусто при каждом Так как для всех то каждая последовательность имеет ненулевую вероятность. Следовательно, для каждого конечного найдется такое что . С другой стороны, в силу (1.8.2) найдется такое что для всех выполняется неравенство Полагая

получим, что для любого и любого

Теорема доказана.

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

Представим себе, что источник подсоединен к некоторому устройству (кодеру источника), осуществляющему кодирование со скоростью Если кодовый алфавит содержит D символов, то в среднем на каждое сообщение источника будет появляться символов на выходе кодера. Для наилучшего кодера это количество будет весьма близким к Следовательно, энтропия источника есть наименьшее количество двоичных символов на сообщение на выходе наилучшего двоичного кодера для этого источника при условии, что сообщения источника могут быть восстановлены по выходу кодера сколь угодно точно.