Глава 4. ДИСКРЕТНЫЕ СЛУЧАЙНЫЕ ИСТОЧНИКИ

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

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

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

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

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

Наконец, мы детально рассмотрим специальный случай марковских источников — класс случайных источников, который позволяет получить адекватные математические модели для разнообразных физических источников.