7.3. Асимптотическая безошибочность декодирования. Теорема Шеннона (вторая асимптотическая теорема)

Важным и далеко не тривиальным фактом является то, что средняя ошибка декодирования может быть сделана подходящим выбором кода сколь угодно малой при увеличении числа символов без уменьшения уровня помех в канале и без уменьшения количества передаваемой информации, рассчитанного на один символ. Этот результат получен Шенноном в 1948 г. [1] и (будучи формулируем в терминах пропускной способности) обычно носит название теоремы Шеннона.

Теорема 7. 1. Пусть (как в § 7.1) имеется канал и канал [(см. (7.1.1), (7.1.2)], являющийся степенью первого. Пусть далее при количество передаваемой информации растет по закону

(скобки обозначают целую часть), где не зависящая от величина, удовлетворяющая неравенству

Тогда существует последовательность кодов таких, что

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

одинаково распределенных независимых случайных величин Каждая из них имеет конечное математическое ожидание

Применяя к (7.3.4) закон больших чисел (теорему Хинчина, см., например Гнеденко [1]), получаем, что

и, следовательно,

каково бы ни было

Рассмотрим среднюю вероятность ошибки по ансамблю случайных кодов, описанных в § 7.2. Положим так что Очевидно, что в силу (7.3.2). Поскольку

то из формулы (7.2.12) имеем

Рассмотрим первый член, стоящий в правой части. Из неравенства следует, что

Поэтому

и в силу (7.3.1)

Это выражение стремится к нулю при Второй член в правой части (7.3.6) стремится к нулю в силу (7.3.5). Следовательно,

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

вероятность

Из (7.3.7), (7.3.8) вытекает, что для последовательности таких кодов

Этим заканчивается доказательство теоремы.

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

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

Б. Отношение пп сходится при по вероятности к 1.

Соответствующее обобщение теоремы 7.1 можно сформулировать так.

Теорема 7. 2. (Общий вид второй асимптотической теоремы). Пусть имеется последовательность информационно устойчивых случайных величин Пусть далее количество передаваемой информации растет при по закону

где не зависит от Тогда существует последовательность кодов таких, что при

Доказательство. Непосредственно из определения информационной устойчивости (свойство Б) имеем

при любом Положим

Вследствие неравенства

из формулы (7.2.12) находим

Второй член в правой части стремится к нулю при в силу (7.3.10), а первый член, используя (7.3.9), можно оценить так:

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