4.13. Краткое содержание и выводы

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

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

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

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

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

Естественные языки с их письменностью представляют собой хорошо знакомые примеры дискретных случайных источников. С этой точки зрения они изучались рядом исследователей. Особенно близки к предмету этой главы шенноновская [7] экспериментальная оценка энтропии печатного английского текста и данное Мандельбротом толкование экспериментальных результатов [8], полученных Ципфом по относительным частотам появления слов. В силу ограниченности объема эти работы, так же как и широкие области исследований по анализу речи и изображений, не могли быть рассмотрены в тексте. Критический обзор этих областей содержится в гл. 1 работы [6].

Другой важной темой, опущенной в этой книге, являются исследования Шеннона [9] по кодированию случайных источников при некоторых типах критериев точности. Эта работа близко примыкает к проблеме кодирования сообщений для передачи по каналу со случайными возмущениями, рассматриваемой в следующих главах.

4.14. Избранная литература

(см. скан)

(см. скан)