§ 3.7. Дискретные стационарные каналы с аддитивным по модулю L шумом

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

Пусть Суммой по модулю называется такое число что нацело делится на Это записывается так:

(например, .

Пусть две последовательности длины элементы которых принадлежат множеству Сумма двух последовательностей определяется как

их покомпонентная сумма по модулю Так, если то

Обозначим через множество всех последовательностей длины над алфавитом Рассмотрим дискретный стационарный источник и обозначим через ансамбль последовательностей длины сообщений такого источника,

Таким образом, для каждого распределение вероятностей задается источником

Определение 3.7.1. Дискретным стационарным каналом с аддитивным по модулю шумом -каналом) называется канал, переходные вероятности которого определяются соотношением

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

Нетрудно видеть, что при каждом матрица, составленная из переходных вероятностей -канала, удовлетворяет определению 3.6.3. Следовательно,

и

где

Из свойств стационарного источника (см. § 1.5) известно, что где - энтропия на сообщение стационарного источника Поэтому правая часть (3.7.5) не убывает с ростом и информационная емкость -канала

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

Теорема 3.7.1 (обратная теорема кодирования для AL-каналов с эргодическим шумом). Пусть С — информационная емкость AL-канала с эргодическим шумом. Тогда для любого и для любой последовательности кодов

где максимальная вероятность ошибки для кода

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

где числитель есть общее число выходных последовательностей канала, а знаменатель — количество решающих областей. Из (3.7.6) и (3.7.8) вытекает, что

Определим множество следующим образом:

Если передается слово и шумовая последовательность z принадлежит то происходит правильное декодирование, в противном случае происходит ошибка. Пусть вероятность ошибки при передаче их. Тогда

причем последнее равенство следует из независимости источника шума и передаваемых сообщений.

Число элементов в множестве равно числу элементов в множестве следовательно, не превосходит правой части неравенства (3.7.9). Из обратной теоремы для случая равномерного кодирования эргодического источника (теорема 1.9.4) следует, что для любого множества с таким числом элементов вероятность события стремится к нулю, когда стремится к бесконечности. Это означает, что вероятность ошибки стремится к единице. Теорема доказана.

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

имела объем не меньший, чем объем высоковероятного множества. Тогда общее число кодовых слов могло бы быть не меньше, чем

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