V. Оценка вероятности ошибки

Ошибкой при последовательном декодировании мы будем называть наступление по меньшей мере одного из следующих двух событий:

1) пара где переданная, принятая последовательности, не удовлетворяет некоторому, скажем, критерию;

2) среди последовательностей нашлась по крайней мере одна, которая вместе с принятой последовательностью образует пару, удовлетворяющую критерию.

Вероятность первого события, осредненная по ансамблю кодов, не превосходит величины Вероятность того, что случайно выбранная последовательность "неправильного" подмножества вместе с образует пару, удовлетворяющую критерию, равна Так как в подмножестве не более элементов, а вероятность суммы событий не превосходит суммы вероятностей слагаемых, то вероятность того, что хотя бы одна из последовательностей образует с пару, удовлетворяющую критерию, не превосходит

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

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

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

В разд. III мы положили величину равной где Оценка принимает различные формы в случае и в случае Мы рассмотрим только первый случай, как наиболее важный. Предположим, что и выберем номер из условия 2)

Функция монотонно возрастает с увеличением поэтому из условия 1) следует, что и, наоборот, 1, если — 1). Так как то для найдется такое что действительно, для этого достаточно положить Отсюда следует, что

где Так как то и оценка (44) для может быть переписана в следующем виде:

В силу условия величина меньше единицы и потому

Производная функции по равна

следовательно, при любом

В силу условия (30)

откуда, согласно предыдущему неравенству,

Неравенство (46) указывает на то, что при больших значениях длина интервала (45), в котором заключена скорость передачи стремится к нулю. Отсюда следует приблизительная оценка для вероятности ощибки:

верная при любых значениях меньших пропускной способности канала С. Эта оценка экспоненциально эквивалентна оценке, полученной Шенноном для блоковых кодов; согласно Шеннону,

Неравенство (47) получается из (44в) заменой коэффициента на коэффициент 2.

Аналогичные рассуждения в случае приводят к результату

Для каналов, симметричных по выходу и с равномерным распределением на входе, автором были проведены более подробные исследования вероятности ошибки, в результате чего получились оценки, имеющие приблизительно следующую форму:

где

Экспоненциально оценка эквивалентна хорошо известным оценкам сверху для вероятности ошибки, которые приведены в книге Фано [8]. Оценка (48а) имеет то же экспоненциальное поведение, что и оценка снизу для и является поэтому оптимальной.

Рис. 3. Зависимость экспоненты от скорости передачи сообщений по каналу, симметричному по выходу и с равномерным распределением на входе.

На рис. 3 представлен график зависимости показателя в оценках от скорости передачи по каналу, симметричному по выходу и с равномерным распределением на входе.

При выводе оценки для в разд. IV мы предположили, что число используемых критериев пропорционально Справедливость этого предположения следует из границ для в частности из неравенства Обозначим величину удовлетворяющую условию (45), через ; тогда

откуда следует, что

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

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