3.6. Источники статистически независимых сообщений

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

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

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

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

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

Докажем теперь следующую теорему.

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

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

Доказательство. Эта теорема немедленно вытекает из основной теоремы разд. 3.5. Подставляя вместо вместо в выражение (3.18) и используя равенство (3.30), получаем

а после деления на

Из этого соотношения следует неравенство (3.32), если положить

И наоборот, неравенство (3.38) несовместимо с неравенством (3.35). Ч. Т. Д.

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