5.3. ВЕРОЯТНОСТЬ ОШИБКИ ДЛЯ ДВУХ КОДОВЫХ СЛОВ

Пусть два кодовых слова длины N и предположим, что используется декодирование по максимуму правдоподобия, т. е. декодируется сообщение 1, если в противном случае декодируется сообщение 2. Согласно (5.2.6) вероятность ошибки при посылке сообщения 1 равна

При любом можно оценить сверху следующим образом:

Граница (5.3.1) следует из того, что при следовательно, Граница (5.3.1) справедлива также при но это здесь не будет использовано. Подставляя (5.3.1) в (5.2.6) и строя границу сверху с помощью суммирования по всем у, будем иметь

Оценивая аналогичным образом, получаем

Если подставить вместо в (5.3.3), то можно заметить, что мы получили одинаковые границы для Это не приводит к потере общности, так как все еще остается произвольным,

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

Расписывая произведение, получаем

Сумма по в (5.3.6) имеет фундаментальное значение для последующего изложения и ей будет дана дополнительная интерпретация в следующем параграфе. Обозначим ее через

При этом (5.3.6) можно переписать в виде

Функция изображена для ряда каналов на рис. 5.3.1. Во всех случаях обозначает вход канала вход канала 1. Для каналов, подобных тому, который представлен на рис. 5.3.1, б и в котором некоторые переходные вероятности равны нулю, могут быть не определены.

Рис. 5.3.1. (см. скан) Функция

Для этих случаев определим равенствами

Можно заметить, что всегда меньше или равны 1. Отсюда также следует, если взять вторую производную, что выпукла при Следовательно, при задаче показано, что при если не имеет места одновременно для всех выходов

Используя определения (5.3.9) и (5.3.10), находим, что неравенство (5.3.8) справедливо для всех Очевидно, можно получить наилучшую границу, если провести минимизацию по

Пример. Рассмотрим дюичный симметричный канал, изображенный на рис. 5.3.1, а. Пусть — последовательность N нулей, а последовательность N единиц. Тогда

Это выражение минимизируется при что дает

Для этого простого примера можно точно подсчитать. будет больше или равна если принятая последовательность содержит или более единиц. Вероятность этого, когда сообщение 1 было передано (в предположении, что N четно), равна

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

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

экспоненциальная зависимость согласуется с той, которая представлена границей (5.3.13).

Так как, по условию, декодируется сообщение 2, если то получаем

В задаче показано также, что экспоненциальная зависимость от N является той же самой, что и для и что та же самая экспоненциальная зависимость имеет место, если N нечетно.

Для более сложных каналов получение хорошей аппроксимации для много труднее. Однако оказывается, что (5.3.11) всегда дает правильную экспоненциальную зависимость от N (см. Шеннон, Галлагер и Берлекэмп 1 (1967), § 3). Это будет рассмотрено более детально в конце настоящей главы.