11.5. Обобщенная теорема Шеннона

Здесь будет рассмотрено обобщение результатов § 7.3 (теоремы 7.1 и 7.2) и §8.1 (теорема 8.1) на случай произвольного критерия качества. Напомним, что в гл. 7 был взят единственный критерий качества, именно, качество информационной системы характеризовалось средней вероятностью принятия ложного сообщения. Работами Колмогорова [1], Шеннона [4], Добрушина [1] начато распространение указанных результатов на случай более общего критерия качества, характеризуемого произвольной функцией штрафов с Соответствующую теорему, сформулированную для произвольной функции с и превращающуюся для частного вида функции

дискретные величины) в указанные обычные результаты, естественно называть обобщенной теоремой Шеннона.

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

немедленно вытекает из обычной теоремы Шеннона и результатов § 11.2 и не потребует, следовательно, нового доказательства.

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

представляют собой цепь Маркова с указанными переходными вероятностями. Применяя формулу (6.3.7), имеем

В то же время по той же формуле можно получить

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

Приравнивая между собой (11.5.4), (11.5.3) и учитывая (11.5.5), имеем

Но информации (как и всякое шенноновское количество информации) неотрицательны. Поэтому из (11.5.6) получаем неравенство

если учесть определение пропускной способности (см. (8.1.3)). Отсюда видно, что распределение может копировать исходное распределение только при том необходимом условии, что

В противном случае не существует таких способов кодирования и декодирования [т. е. таких чтобы совпадало с

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

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

которое говорит о том, что качество распределения асимптотически не хуже, чем Основное утверждение формулируется для последовательности схем (11.5.2), зависящих, скажем, от

Теорема 11.3. Пусть: 1) последовательность пар случайных величин является информационно устойчивой (см. § 7.3);

2) имеет место сходимость

по вероятности

3) последовательность функций штрафа удовлетворяет условию ограниченности

[ср. (11.2.32); К не зависит от ];

4) последовательность каналов является информационно устойчивой (т. е. при экстремальном распределении являются информационно устойчивыми);

5) выполняется условие (11.5.9).

Тогда существуют способы кодирования и декодирования, обеспечивающие асимптотическую равнокачественность в смысле сходимости (11.5.10).

Доказательство использует полученные ранее результаты и указывает способы кодирования и декодирования, т. е. конструктивно определяет

Условия теоремы позволяют доказать неравенство

совершенно тем же способом, как и в § 11.2 были доказаны соотношения (11.2.33а) на основе условий информационной устойчивости и условий (11.2.31), (11.2.32) (см. также вывод (11.2.30)). В (11.5.13) - сколь угодно малые, не зависящие от положительные величины, средние штрафы:

соответствующие некоторому разбиению пространства значений на областей. Эти области могут быть построены при помощи случайных кодовых точек выбрасываемых с вероятностями (см. § 11.1, 11.2).

Из (11.5.14) следует, что существуют такие точки что

( сколь угодно мало) и в силу (11.5.13)

Будем передавать по каналу сообщение о том, какой кодовой области принадлежит значение

Вследствие (11.5.9) можно выбрать такое чтобы выполнялось неравенство начиная с некоторого Поскольку это означает выполнение неравенства т. е. условия (8.1.5). Последнее вместе с требованием 4) теоремы 11.3 обеспечивает применение теоремы 8.1 (обобщенной по типу теоремы 7.2), согласно которой вероятность ошибки при приеме сообщения по каналу с увеличением может быть сделана сколь угодно малой:

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

Совместное распределение имеет вид

где вероятность принять сообщение если было передано сообщение

Распределению (11.5.17) соответствуют средние штрафы

Мажорируем последнюю сумму, используя (11.5.12). Это дает

Усредняя по ансамблю случайных кодов и учитывая (11.5.16), имеем

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

и поэтому в силу (11.5.18)

Комбинируя это неравенство с (11.5.15), получаем

Поскольку могут быть взяты сколь угодно малыми, отсюда следует (11.5.10). Доказательство закончено.

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

В этом последнем случае доказывается сходимость

условие (11.5.9) заменяется на

условие (11.5.12) — на (11.2.39), а условия 1), 2) теоремы 113 нужно заменить требованиями информационной устойчивости бейесовской системы (§ 11.2, п. 4), чтобы можно было применить теорему

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

При этом, очевидно,

так что условие выполняется, если Далее при следовательно, второе условие Б информационной устойчивости § 7.3 тривиальным образом выполняется. Требование 1) теоремы 11.3 поэтому выполняется, если Выбирая функцию штрафов (11.5.1), убеждаемся, что выполняются также требования 2), 3). Неравенство (11.5.9) согласно (11.5.20) принимает вид что эквивалентно соотношению (8.1.5). При функции штрафов (11.5.1) имеем и соотношение (11.5.10) принимает вид

но

есть не что иное, как средняя вероятность ошибки (7.1.11), так что сходимость (11.5.21) совпадает с (7.3.7). Итак, мы получили, что в данном частном случае теорема 11.3 действительно дублирует теорему 7.2.