1.5.1. Граница случайного кодирования

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

Теорема 1.4. (Шеннон, Галлагер). Пусть задан дискретный канал без памяти с входным алфавитом из К символов выходным алфавитом из символов переходными вероятностями Тогда для любой длины кода любого числа кодовых слов и любого распределения вероятностей на множестве этих кодовых слов существует код длины вероятность ошибки для которого в указанном выше канале оценивается сверху следующим образом:

где

произвольное число из интервала произвольный вероятностный вектор

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

Вначале рассмотрим некоторый фиксированный код, состоящий из кодовых слов. Допустим, что целым числам сопоставлены соответственно кодовые слова Предположим, что декодирование производится по максимуму правдоподобия.

А именно если принято слово V и целое число таково, что при всех

то декодер максимального правдоподобия декодирует V в Если же принято слово V, такое, что ни при каком неравенства (1.17) одновременно для всех не выпвлняюгся, то считается, что произошла ошибка декодирования. Вероятность возникновения ошибки декодирования при передаче кодового слова обозначим через Эта вероятность определяется равенством

где

Первым шагом на пути вывода верхней границы для является следующая оценка сверху для

В справедливости этого неравенства легко убедиться, если заметить, что

1) правая часть его всегда положительна, и, следовательно, оно выполняется всегда, когда

2) в случае когда одно из слагаемых в числителе правой части (1.20) больше знаменателя, а следовательно, и весь числитель больше знаменателя (при возведении числителя и знаменателя в степень по-прежнему первый остается больше второго).

Подставив (1.20) в (1.18), получим

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

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

Итак, усредняя вероятность ошибки по ансамблю кодов, из формулы (1.21) получаем

где черта сверху означает усреднение. Ограничим область значений параметра интервалом и следующим образом упростим формулу

1) Все слагаемые под чертой в формуле (1.21) являются случайными величинами. А именно каждое из слагаемых является функцией случайно выбираемых кодовых слов, принимающей действительные значения. Поскольку среднее значение суммы случайных величин равно сумме средних значений, то

2) Аналогично, поскольку среднее значение произведения независимых случайных величин равно произведению средних значений сомножителей, то из формулы получаем

3) Положим и воспользуемся тем, что при . В справедливости последнего неравенства легко убедиться, если заметить, что при всех

является выпуклой вверх функцией аргумента Тогда

4) Пользуясь опять тем, что среднее значение суммы случайных величин равно сумме средних значений слагаемых, получаем

Отсюда и из формулы следует, что

Поскольку кодовые слова в рассматриваемом ансамбле кодов выбираются с распределением то

Правая часть последнего равенства не зависит от следовательно, ее можно подставить в формулу (1.22) вместо соответствующих выражений как с индексом так и с индексом Так как сумма по в (1.22) является суммой одинаковых слагаемых, то

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

Пусть компоненты входной последовательности компоненты выходной последовательности По определению в канале без памяти для любых

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

независимо с распределением входной алфавит канала). Тогда

Подставляя формулы (1.25) и (1.26) в (1.24), получаем

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

Аналогично, вынося знак произведения в формуле (1.28) за квадратные скобки, имеем

Правую часть этой формулы можно упростить следующим образом. Совокупность К входных символов обозначим через а совокупность выходных символов через Обозначим также через переходную вероятность канала а через вероятность выбора символа в ансамбле кодов. Эти обозначения подставим в формулу (1.29) и, заметив, что все сомножители произведения в правой части (1.29) равны, получим

Пусть скорость передачи информации в натуральных единицах (натах) на один символ канала (по определению Если оценить сверху величиной то соотношение (1.30) можно представить в виде

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

Если провести минимизацию правой части формулы (1.31) по то можно получить более точную оценку для

Следствие 1.2. При выполнении условий теоремы 1.4 существует код, для которого

где максимум берется по всем из интервала и всем вероятностным векторам

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