3.12.3. Оценка средней по ансамблю кодов вероятности ошибки декодирования для дискретных каналов без памяти.

Рассмотрим дискретный канал без памяти, задаваемый переходными вероятностями

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

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

Подставляя (3.12.13) в (3.12.11), а также учитывая (3.12.12), получим

где последнее равенство получается в результате того, что распределения вероятностей от не зависят.

Обозначим через вероятностный вектор и положим

Функция называется функцией Галлагера. Пусть, кроме того,

где максимум разыскивается по всем и по всем вероятностным векторам т. е. по всем распределениям вероятностей на Учитывая, что из (3.12.14) следует, что

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

Теорема 3.12.1. Существует код со скоростью который в дискретном канале без памяти обеспечивает среднюю вероятность ошибки, удовлетворяющую неравенству (3.12.17), где длина кода, а показатель зависит только от скорости кода.

Более того, имеет место следующее утверждение.

Теорема 3.12.2. Для произвольного дискретного канала без памяти существует код со скоростью для которого средняя вероятность ошибки декодирования удовлетворяет неравенству (3.12.17), где — длина кода, а функция зависит только от матрицы переходных вероятностей канала и от скорости кода, причем при всех где — информационная емкость рассматриваемого канала.

Замечание. Функция определяемая соотношением (3.12.16), называется экспонентой случайного кодирования.

Доказательство. Так как средняя по ансамблю кодов вероятность ошибки удовлетворяет неравенству (3.12.17), то в ансамбле найдется по крайней мере один код, вероятность ошибки декодирования которого также удовлетворяет неравенству (3.12.17).

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

Обозначим выражение под знаком максимума в (3.12.16) через Тогда с учетом последнего соотношения

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

Теоремы 3.12.1 и 3.12.2 в совокупности содержат утверждение, аналогичное утверждению прямой теоремы кодирования 3.9.1 для дискретного канала без памяти. Отличие этих двух

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