§ 3.12. Верхняя граница вероятности ошибки декодирования для дискретных каналов без памяти

3.12.1. Метод случайного кодирования.

Рассмотрим множество всех кодов длины и объема где скорость кода. Обозначим это множество через и будем допускать, что сюда входят даже заведомо плохие коды, например, содержащие совпадающие слова. Множество как нетрудно видеть, содержит кодов, где через обозначен объем входного алфавита канала. Предположим, что на множестве задано некоторое распределение вероятностей, т. е. каждому коду приписана вероятность Распределение вероятностей на можно вводить многими способами. Часто удобным оказывается способ задания распределения посредством указания некоторого случайного правила выбора Л! кодовых слов. Ниже мы более подробно остановимся на описании ансамбля кодов а пока будем предполагать, что такой ансамбль определен.

Пусть при использовании кода обеспечивается средняя вероятность ошибки Если возможно оценить среднюю по ансамблю кодов вероятность ошибки

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

3.12.2. Оценка средней по ансамблю кодов вероятности ошибки декодирования для произвольного дискретного канала.

Рассмотрим некоторый код где решающие области, соответствующие декодированию по максимуму правдоподобия. Введем в рассмотрение среднюю вероятность ошибки этого кода

где дополнение множества

Пусть

индикатор ошибки декодирования при передаче слова и получении на выходе канала последовательности у. Функцию можно оценить сверху следующим образом:

Справедливость этого неравенства устанавливается очевидным образом. Если то неравенство тривиально, так как правая часть всегда неотрицательна. Если то для одного из слагаемых в числителе именно для того, для которого соответствует номеру области содержащей у: Поэтому правая часть (3.12.4) не меньше единицы для любого Объяснить, почему используется именно такая оценка, довольно трудно. Тем не менее она дает хорошие результаты.

Подставляя (3.12.4) в (3.12.2), получим при

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

Теперь введем в рассмотрение вероятностный ансамбль кодов и применим метод случайного кодирования. Предположим, что некоторое распределение вероятностей на последовательностях Будем считать, что распределение вероятностей на множестве О всех кодов длины словами задается посредством распределения Если это код, состоящий из слов то положим

Последнее означает, что кодовые слова для кода выбираются из множества независимо в соответствии с распределением

Средняя по ансамблю кодов вероятность ошибки Я может быть вычислена по формуле

Оценивая с помощью неравенства (3.12.5) и обозначая операцию взятия математического ожидания по ансамблю кодов чертой сверху, получим при

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

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

при

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

Если вероятности значений случайной величины X, то левая часть (3.12.9) — это математическое ожидание случайной величины а правая — это Таким образом, для выпуклых вверх функций справедливо неравенство (см. также задачу 2.5.7)

Легко видеть, что выпуклая вверх функция при с 1. Поэтому

Ограничивая величину сверху единицей, из (3.12.8) получим

Заметим далее, что величина

не зависит от так как -переменная суммирования. Используя это замечание и обозначая переменную суммирования через х вместо из неравенства (3.12.10) получим

Неравенство (3.12.11) представляет собой среднюю по ансамблю кодов оценку вероятности ошибочного декодирования, справедливую для произвольного дискретного канала. Ниже эта оценка будет упрощена для каналов без памяти.