5.7. ВЕРОЯТНОСТЬ ОШИБКИ ДЛЯ АНСАМБЛЯ КОДОВ С ВЫБРАСЫВАНИЕМ

В § 5.5 было показано (см. рис. 5.5.1), что средняя по ансамблю двух случайно выбранных кодовых слов вероятность ошибки сильно отличается от вероятности ошибки для двух типичных кодовых слов. Причина этого состоит в том, что хотя плохие коды в ансамбле являются маловероятными, они имеют такую большую вероятность ошибки, что определяют среднюю вероятность ошибки. То же самое явление оказывает неблагоприятное влияние на показатель экспоненты случайного кодирования при малых скоростях. Наиболее ясно это можно увидеть в двоичном симметричном канале, для которого согласно (5.6.45) при 0 верхняя граница вероятности ошибки стремится к Это дает приближенное выражение для вероятности того, что при заданном переданном кодовом слове некоторое другое кодовое слово будет выбрано и отождествлено с ним.

В этом параграфе граница случайного кодирования будет усилена при малых скоростях с помощью выбрасывания плохих кодовых слов

из кодов, принадлежащих ансамблю. Этот подход аналогичен рассмотренному в следствии, устанавливающем границу (5.6.20). Вначале рассмотрим ансамбль, состоящий из кодов, каждый из которых содержит кодовых слов. Затем покажем, что по крайней мере в одном коде из ансамбля, имеются не меньше чем слов, для которых удовлетворяет заданной границе. Эта граница будет выражена через произвольный параметр который в дальнейшем может быть оптимизирован. На ансамбле кодов вероятность при каждом является случайной величиной. Применяя к этой случайной величине неравенство Чебышева (5.4.6), получаем

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

Доказательство. Пусть при каждом является случайной величиной на ансамбле кодов. Пусть для кодов, для которых справедливо (5.7.2) и пусть во всех остальных случаях. Согласно (5.7.1) вероятность того, что (5.7.2) будет справедливо, не меньше 1/2 и, следовательно, 1/2. Число кодовых слов в случайно выбранном коде, которые удовлетворяют (5.7.2), является случайной величиной

Математическое ожидание числа слов, которые удовлетворяют (5.7.2), равно, следовательно,

Отсюда вытекает, что существует по крайней мере один код, для которого и для такого кода

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

Для того чтобы показать справедливость (5.7.3), заметим, что согласно (5.3.4) для заданного кода

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

Рассмотрим теперь из интервала Используя известное неравенство (см. задачу будем иметь

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

В силу того, что является глухим переменным суммирования в (5.7.5), слагаемое в фигурных скобках не зависит от и мы имеем одинаковых слагаемых. Подставляя упростившееся таким образом выражение (5.7.5) в (5.7.2), получаем

Эта граница по своему виду подобна границе, установленной в теореме 5.6.1. Это сходство может быть выявлено, если положить Так как является произвольным параметром то является произвольным параметром, Имеем

Неравенство (5.7.7) справедливо для любого дискретного канала как с памятью, так и без памяти, для которого можно определить Применим теперь эту границу к дискретному каналу без памяти, для которого

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

После подстановки этого произведения в (5.7.7) и после преобразований, которые аналогичны проведенным при переходе от (5.5.6) к (5.5.10), получим

имеются кодовых слов, поэтому (5.7.8) приводится к виду

Полученные результаты можно подытожить следующей теоремой.

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

где функция задается равенствами

и максимум в (5.7.11) берется по всем распределениям вероятностей для букв на входе канала.

Исследование свойств функции которая называется показателем экспоненты для процедуры с выбрасыванием, проводится почти так же, как для показателя экспоненты случайного кодирования. Ее свойства зависят от таким же образом, как свойства зависели от

Теорема 5.7.2. Пусть распределение вероятности на входе дискретного канала без памяти с переходными вероятностями будем считать, что [см. (5.6.23)]. Тогда при любом является строго возрастающей и выпуклой функцией Выпуклость будет строгой, за исключением случая, когда канал является каналом без шума, в том смысле, что для любой пары используемых входов (т. е. таких входов, для которых справедливо либо для всех либо для всех

Эта теорема доказана в приложении Заметим, что согласно можно понимать как верхнюю грань значений множества линейных функций

с наклоном при каждом Это изображено на рис. 5.7.1. Заметим, что при можно изменить порядок суммирования по с суммированием по в определении и после этого можно заметить, что показывает связь между проиллюстрированную на рис. 5.7.1. Поскольку строго возрастающая функция то указанная геометрическая интерпретация доказывает, что (в общем случае) для достаточно малых Однако в пределе при переходе к каналу с очень большим шумом это различие становится сколь угодно малым (см. задачу 5.31).

Рис. 5.7.1. Сравнение

Заметим, что в любой области, где имеем и поэтому

что в точности совпадает с равномерной границей для заданной (5.6.20). Граница для процедуры с выбрасыванием (5.7.10), таким образом, строго точнее, чем граница случайного кодирования в области, где строго меньше, чем наименьшая для которой

Может случиться, что для достаточно малой R функция принимает бесконечные значения. Для того чтобы исследовать этот случай, заметим, что координата точки пересечения оси R линейной функцией — равна При функция имеет вертикальную асимптоту

принимает бесконечные значения при

(Другими словами, для таких R функция стремится к при Раскрывая этот предел по правилу Лопиталя, получаем

Пусть обозначает максимальное значение (5.7.14) по Q, т. е.

Из сказанного следует, что при

Из (5.7.14) можно увидеть, что если при всех в других случаях. Если для некоторых то эти два входа не будут никогда перепутаны на приемном конце и по крайней мере один бит информации можно передать при одном использовании канала без каких-либо ошибок, используя лишь эти два входа.

Рис. 5.7.2. Функция для каналов с

Если положить для этой пары входов, то правая часть (5.7.14) будет равна Отсюда следует, что если то должна быть по крайней мере равной Шеннон (1956) определил пропускную способность канала с нулевой ошибкой как наибольшую скорость, с которой данные могут быть переданы по каналу с нулевой вероятностью ошибки (в противоположность к сколь угодно малой вероятности ошибки). Так как при то получаем, что является нижней границей для пропускной способности канала с нулевой ошибкой. На рис. 5.7.2 изображено поведение для двух каналов с В задаче 5.25 выведено простое выражение для

Нахождение максимума по в значительной мере похоже на аналогичную процедуру для показателя экспоненты случайного кодирования. Если ввести обозначение

то получим параметрические соотношения

справедливые при

При больших скоростях R эта граница эквивалента прямолинейному участку границы случайного кодирования, которая была рассмотрена ранее. Для типичного канала как показано в задаче 5.24, имеем

В настоящее время сравнительно немного известно о методах отыскания максимума этой границы по Функция не является выпуклой по и может иметь несколько локальных максимумов по что более удивительно, если попытаться оптимизировать выражение (5.7.7) для по не ограничиваясь произведением распределений, то иногда могут возникнуть случаи, в которых произведение распределений не оптимизирует границу (см. задачу 5.26). Джелинек (1968), однако, показал, что в случае произвольного дискретного канала с двоичным входом произведение распределений всегда оптимизирует границу и, на самом деле, оптимальное значение равно (см. задачи 5.29 и 5.30).