3.6. МАРКОВСКИЕ ИСТОЧНИКИ

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

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

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

Случайная последовательность состояний, для которой выполнены (3.6.1) и (3.6.2), называется конечной однородной цепью Маркова.

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

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

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

Рис. 3.6.1. Марковский источник; на ребрах указаны выход а и вероятность

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

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

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

Вот отрывок из этого последнего примера:

The head and in frontal attack on an english writer that the character of this point is therefore another method

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

Приведем здесь без доказательств некоторые свойства конечных однородных цепей Маркова. Состояние называется невозвратным, если существует некоторое состояние, которое может быть достигнуто из за один или более переходов, но из которого невозможно никогда возвратиться в Например, на рис. 3.6.1 состояние 1 является невозвратным. Множество состояний называется неразложимым, если никакое состояние вне множества не может быть достигнуто ни из какого состояния, входящего в множество, и каждое состояние множества может быть достигнуто за один или более переходов. Так, например, состояния 2 и 3 образуют неразложимое множество, так же как и состояния 4 и 5.

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

Число переходов, начиная из некоторого состояния неразложимого множества, требующееся для первого возвращения в является случайной величиной, которая называется временем возвращения в Периодом неразложимого множества состояний называется наибольшее целое число такое, что все возможные времена возвращений для состояний этого множества являются кратными Например, период множества состояний 1 и 3 на рис. 3.6.1 равен 1, так как время возвращения для любого состояния может быть любым положительным целым числом. Период состояний 4 и 5 равен 2, так как время возвращения равно 2 для каждого состояния. Если неразложимое множество имеет период то оно называется периодическим. Если то множество называется эргодическим.

Эргодическое множество состояний имеет ассоциированное с ним множество стационарных вероятностей задаваемых как решения уравнений

Более того, для любых из

где сходимость к пределу экспоненциальна по

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

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

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

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

Затем найдем энтропию выхода источника при условии, что задано некоторое частное состояние в некоторый момент в прошлом и заданы промежуточные выходы источника.

Лемма.

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

где является состоянием, определяемым Так как и, зависит только от [см. (3.6.4)], то отсюда получаем

Логарифмируя обе части равенства (3.6.11) и усредняя по будем иметь

Суммируя правую часть равенства по получаем (3.6.10).

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

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

Для стационарного эргодического марковского источника не зависит от и из (3.6.8) имеем

Рассмотрим теперь энтропию на букву последовательности букв источника при условии, что задано начальное состояние

Отсюда согласно (3.6.12) имеем

где

Отсюда видно, что в точности равна средней по времени вероятности пребывания в состоянии Для стационарного эргодического марковского источника совпадают с как показывают (3.6.5) и (3.6.6), и поэтому

В пределе при определим

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

Рассмотрим далее безусловную энтропию на букву последовательности источника. Имеем

Средняя взаимная информация в правой части приведенного выше выражения ограничена и, следовательно,

Обозначая левую часть (3.6.20) через получаем в силу (3.6.19), что

Следующая теорема подытоживает полученные результаты.

Теорема 3.6.1. Энтропия на букву марковского источника задается равенством (3.6.21), где задается (3.6.18), а задается (3.6.9). Если цепь Маркова имеет не больше одного неразложимого множества состояний, то не зависит от распределения вероятностей дляхь и если это неразложимое множество является эргодическим, то где задается (3.6.5) и (3.6.6).

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

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

Так же как и в теореме 3.3.1, эти длины удовлетворяют неравенству Крафта для каждого начального состояния, и средняя длина кодового слова для данного начального состояния удовлетворяет неравенствам

Усредняя по состояниям, деля на и используя (3.6.17), полученное неравенство можно свести к (3.6.21 а).

ИТОГИ И ВЫВОДЫ

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

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

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

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

Следует помнить, что для болыпинства реальных источников центральные проблемы не являются теоретико-информационными проблемами представления источника, а состоят в более субъективных проблемах определения, что имеется ценного на выходе источника.

ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ И ССЫЛКИ

Другое рассмотрение затронутых здесь вопросов (в особенности, содержащихся в первых четырех параграфах) можно найти у Эбрамсона (1963), Фано (1961), Эша (1965) и Шеннона (1948). Теорема кодирования для источника (теорема 3.1.1) была получена Шенноном (1948), который развил большинство концепций этой главы. Шеннон также установил теорему для случая, когда буквы источника имеют неравные длительности и когда источник является марковским. Как указано в тексте, процедура построения оптимального кода, изложенная в § 2.4, принадлежит Хаффману (1952). Кодирование для источника, обладающее свойством синхронизации, было изучено Голомбом, Гордоном и Велчем (1958), Кендаллом и Ридом (1962), Истманом (1965), Шольцем (1966) и другими.

Теорема 3.5.3 была получена Макмилланом (1953) и часто называется АЕР-свойством эргодических источников. Макмиллан доказал -сходимость, которая несколько сильнее, чем сходимость, установленная здесь, но его теорема относится только к источникам с конечным алфавитом и его доказательство намного сложнее приведенного здесь. Брейман (1957) позднее доказал сходимость по вероятности для эргодического источника с конечным алфавитом. Отт (1962) разработал процедуру кодирования для марковского источника более общего типа по сравнению с рассмотренным здесь; в его источнике состояние источника не обязательно однозначно определяется предыдущим состоянием и предыдущей буквой источника.