Оценка вероятности ошибки в терминах производящей функции моментов

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

состоит из последовательности букв то есть Если V состоит из букв то

Отсюда

где через обозначена взаимная информация между буквами слов

Различные в последней формуле являются одинаково распределенными независимыми случайными величинами. Величина равна сумме одинаково распределенных независимых случайных величин. Следовательно, возникает ситуация, в которой можно применить центральную предельную теорему. Представляется возможным оценить с помощью каких-либо неравенств, известных для функции распределения подобной суммы. В частности, можно воспользоваться неравенством, которое получил в 1952 г. Чернов [1] для «хвоста» такого распределения. С помощью простых вычислений, использующих обобщенное неравенство Чебышева, он показал, что распределение таких сумм можно оценить при помощи - производящей функции моментов, относящейся к какой-либо одной случайной величине. Итак, положим

Для наших целей более удобным будет использование логарифма производящей функции (эту величину иногда называют производящей функцией семиинвариантов). Записанный в наших обозначениях результат Чернова имеет вид

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

выражений, равные соответственно существуют; кроме того, используя неравенство Шварца, легко показать, что положительна.

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

Тогда существуют код и система декодирования длины скорость создания информации и вероятность ошибки удовлетворяющие неравенствам

Если

Доказательство. Согласно теореме 1, имеем

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

т. е.

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

Это соотношение справедливо для всех отрицательных и составляет первый результат теоремы.

Однако в некоторых случаях величина при стремится к положительному пределу. Действительно, а показатель степени в оценке стремится к Для меньших значений предельные величины показателей степени не могут быть приравнены друг к другу ни при каком выборе Однако можно подобрать 0 так, чтобы было строго меньше, чем скажем, было равно . В силу того что вероятность ошибки теперь оценивается неравенством Это справедливо при любом значит, можно составлять коды, для которых оценка имеет место при Итак

для Заметим, что при стремлении к своему предельному значению в первой оценке (т. е. к величине показатели степени в обеих оценках сходятся к одной и той же величине Однако коэффициент при степенной функции уменьшается: вместо 2 он становится равным 1.

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

Иначе говоря, первоначальная вероятность величины увеличивается или уменьшается в раз и образованные величины нормируются так, чтобы дать в сумме единицу. Для больших положительных значений 5 эта отклоненная совокупность вероятностей увеличивает вероятности для положительных и уменьшает их для отрицательных. Если то При отрицательном вероятности отрицательных значений увеличиваются за счет вероятностей положительных величин I. Если то , кроме того случая, когда при этом Здесь величина это наибольшее значение имеющее положительную вероятность существует, так как множество пар конечно). Эти отклоненные вероятности удобны для оценки «хвостов» распределения, которые являются свертками других

распределений. В терминах мы можем написать

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

Рис. 1.

Коэффициент Е при для первой оценки в рассматриваемой теореме представляет собой кривую, которая касается оси в точке С (где ), кончается, когда (т. е. при ) и обращена своей выпуклостью вниз. Второй оценке в теореме соответствует кривая Е, которая представляет собой прямую линию с тангенсом угла наклона, равным —1. Она проходит через точку и пересекает оси в точках . В окрестности точки кривая ведет себя как

где дисперсия I. Все перечисленные свойства вытекают непосредственно из формул для этих кривых.

Предельный показатель степени (при имеет вид Мы получаем

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

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

Однако при использовании соответствующих оценка, выведенная в теореме, справедлива для любой совокупности вероятностей Для того чтобы получить более сильный результат, оценку нужно сделать оптимальной для каждого значения с помощью вариации вероятностей То же самое относится и к прямой линии, где требуется максимизировать Если проделать это, то получится некоторая кривая, которая будет служить огибающей всех возможных кривых этого типа с различными величинами Так как каждая отдельная кривая выпукла вниз, то то же самое верно для огибающей. Уравнение для огибающей может быть получено решением по методу Лагранжа задачи о максимуме выражения Нужно, конечно, иметь в виду, что должны быть неотрицательными. Эта задача похожа на ту, которая возникает при отыскании пропускной способности канала. Уравнения для огибающей будут иметь вид

для всех , кроме тех, для которых причем

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

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