4.7. Кодирование эргодических источников с фиксированной скоростью

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

среднее арифметическое значение собственной информации сообщений последовательности, т. е.

Обобщение рассмотренного в предыдущем пункте метода кодирования на эргодические источники основано на следующей теореме.

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

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

где выражено в двоичных единицах.

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

Отсюда следует, что

Верхняя граница числа последовательностей в задаваемая неравенством (4.79), следует из определений множества и собственной информации Из равенства (4.76) мы имеем

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

где выражено в двоичных единицах. Отсюда следует, что

где множество всех последовательностей из последовательных сообщений, т. е. всевозможных последовательностей из букв, а множество всех возможных последовательностей из букв. Искомая верхняя граница для немедленно следует из соотношения (4.84). Ч. Т. Д,

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

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

можно закодировать так, чтобы число символов на событие и вероятность неоднозначного кодирования удовлетворяли неравенствам

где число символов в кодовом алфавите.

Доказательство. При использовании приведенного выше метода кодирования длина каждого из различных кодовых слов удовлетворяет неравенству

так что требуемое число символов на выходное событие ограничено сверху

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

Далее выражения (4.15) и (4.16) показывают, что для любого положительного можно добиться, чтобы при достаточно большом энтропия удовлетворяла неравенству

Подставляя неравенство (4.88) вместо в правую часть неравенства (4.90), получаем

Наконец, если выбрано так, чтобы

то неравенство (4.91) приводит к неравенству (4.85). Ч. Т. Д.

Из этой теоремы мы можем заключить, что последовательность на выходе эргодического источника с фиксированной

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

Теорема. Вероятность неоднозначного кодирования для эргодического источника с фиксированной скоростью удовлетворяет неравенству

где - энтропия на событие; число символов на событие; число букв в алфавите источника; число символов в кодовом алфавите.

Доказательство. Обозначим через -ансамбль кодовых слов, а через ансамбль последовательностей из букв, представленных этими кодовыми словами. Среднее значение количества информации, содержащейся в кодовых словам о последовательностях, можно записать в виде

С другой стороны, поскольку является нижней границей энтропии на событие, то

так что

Кроме того,

где число символов в каждом кодовом слове. Отсюда следует, что

По аналогии с неравенством (4.74), легко получить следующее неравенство:

где вероятность неоднозначного кодирования, число символов в алфавите источника. Тогда, подставляя в неравенство (4.98) вместо правую часть неравенства (4.99), имеем

откуда с помощью равенства

легко получается неравенство (4.93). Ч. Т. Д.