4.3. Кодирование стационарных источников с управляемой скоростью

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

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

где -предельное значение условной энтропии, определяемое выражением (4.16), число символов в кодовом алфавите. И обратно, невозможно закодировать события так, чтобы было справедливо неравенство

Доказательство. Разобьем последовательность событий на сообщения, каждое из которых состоит из -последовательных событий. Каждое сообщение является элементом произведения ансамблей состоящего из всевозможных последовательностей

из букв, принадлежащих множеству А. Энтропия этого ансамбля задается выражением (4.14). Тогда для множества возможных сообщений можно построить, как это было показано в разд. 3.7, множество оптимальных кодовых слов. Среднее число символов на сообщение будет удовлетворять неравенству

получаемому из выражения (3.18), если вместо ансамбля сообщений подставить ансамбль Разделив обе части неравенства на получаем для среднего числа символов на событие

где - средняя энтропия, определяемая соотношением (4.15). С другой стороны, в силу равенства (4.16), всегда но найти целое такое, что

При этих условиях будет удовлетворять неравенству (4.26). Наоборот, выражение (4.27) несовместимо с (4.29), поскольку как видно из выражения (4.25), никогда не может быть меньше . Ч. Т. Д.

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

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

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

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

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

Обсуждаемая теорема была доказана затем при помощи интерпретации совокупности последовательных событий как независимого сообщения с собственной информацией

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

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

в какой-либо момент времени вне зависимости от всех предшествующих кодовых слов.

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