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

В этом разделе будет найдена оценка верхней границы осредненной вероятности ошибки для случая, когда входные последовательности, сопоставляемые сообщениям, имеют одинаковую композицию и выбираются случайно с равными вероятностями из множества последовательностей, имеющих такую же композицию. Как и в разд. 9.2, обозначим через число букв в некоторой последовательности , а через — число букв в некоторой выходной последовательности Аналогично обозначим через число соответствующих пар букв в этих двух последовательностях. Очевидно, они связаны соотношениями (9.5) и (9.6). Множество целых чисел определяемых некоторой последовательностью и, назовем композицией и будем обозначать это множество с Аналогично множество целых чисел определяемых некоторой последовательностью назовем композицией последовательности а множество целых чисел связанных с парой последовательностей композицией пары последовательностей

Пусть положительная функция от у, для которой

положим

Тогда расстояние, определяемое тождеством (9.111), принимает вид

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

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

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

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

Аналогично число последовательностей для которых равно

Общее число последовательностей и, для которых с с равно

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

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

которых то, разделив выражение (9.127) на (9.129), получаем

Аналогично, разделив выражение (9.128) на (9.130), получаем

Так как правые части равенств (9.131) и (9.132) равны, то отсюда следует соотношение (9.125), указанное в лемме. Ч. Т. Д.

Теперь мы в состоянии сформулировать и доказать основной результат этого раздела.

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

и пусть, по определению, перекошенное условное распределение вероятностей

где перекошенное распределение вероятностей удовлетворяет системе уравнений

Если К — число точек во входном пространстве X, то вероятность ошибки, осредненная по ансамблю отображений, удовлетворяет неравенству

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

и

Доказательство. Верхняя граница осредненной вероятности ошибки задается с помощью теоремы, содержащей формулу (9.114), если каждый из ансамблей состоит из равновероятных последовательностей с заданной композицией. Верхнюю границу для вероятности задаваемую выражением (9.116), можно легко получить с помощью теоремы, содержащей формулу (8.69). С этой целью отождествим точки у выходного пространства с точками а пространства А теоремы, условное распределение вероятностей с распределением вероятностей целые с целыми случайную величину с пер. Тогда из выражения (8.69) с помощью выражений (8.62), (8.63), (8.71) и (8.74) получаем, что

где

и

Значение параметра определяется соотношением (9.142) для любого значения удовлетворяющего неравенству в правой части этого соотношения.

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

где множество последовательностей для которых

Тогда из леммы, содержащей формулу (9.125), следует, что

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

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

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

где множество целых чисел есть композиция пары последовательностей множество целых чисел — композиция последовательности — число точек в пространстве X на входе канала. Ясно, что поскольку канал постоянный, то

является условным распределением вероятности степени канала. Вероятность одна и та же для всех последовательностей с одинаковой композицией. Для ансамбля VV последовательностей пар расстояния определяемые равенством (9.124), суть суммы независимых случайных величин соответственно. Затем, рассуждая как в разд. 8.3, определим для каждого логарифм производящей функции моментов

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

где

и

Далее мы определим перекошенные распределения вероятностей

Перейдем теперь к вычислению оценки вероятности сверху, определяемой равенством (9.146).

Представляя условную вероятность в правой части равенства (9.146) в виде отношения соответствующей совместной вероятности к вероятности условия, получим

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

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

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

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

Это условие выполняется, когда - функция, симметричная относительно . Анализ соотношения (9.153)

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

При этих условиях имеем

где

т. е. есть произведение двух тождественных условных распределений вероятностей. Затем, подставляя в неравенство (9.157) правую часть выражения (9.160) и расширяя область суммирования до получаем

Это и есть нужная нам верхняя граница для числителя в равенстве (9.156).

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

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

Отсюда следует, что

Сумма по в этом соотношении зависит только от композиции и не зависит от того, какая именно последовательность

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

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

И наконец, подстановка правой части этого соотношения в неравенство (9.165) дает

где - какое-либо и, имеющее заданную композицию.

Теперь нам надлежит найти верхнюю границу отношения (9.156). С этой целью найдем границу отношения сумм по в выражениях (9.162) и (9.167). Это отношение можно сделать равным единице, полагая

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

Затем, подставляя правые части выражений (9.162) и (9.167) в равенство (9.156), имеем

Наконец, поскольку все последовательности принадлежащие находятся от и на расстоянии, не превосходящем то

Как и прежде, для минимизации правой части неравенства (9.171) приравниваем нулю частную производную по Получаем

Мы видели, с другой стороны, что Уже полагалась равной в выражении (9.142). Отсюда следует, что а это в свою очередь означает, что

Это условие имеет место, если

что в свою очередь, как видно из рассмотрения выражений (9.144) и (9.161), удовлетворяется, если

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

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

Наконец, подстановка правой части равенства (9.177) в показатель в выражении (9.171) с учетом равенства (9.172) дает

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

второй задается соотношением (9.143). Пусть далее

есть скорость передачи на событие. Подставляя правые части выражений (9.141) и (9.178) в неравенство (9.114), получаем

Это соотношение справедливо для всех значений в указанной области. Следовательно, мы можем выбрать для каждой скорости значение минимизирующее правую часть неравенства (9.181). С другой стороны, поскольку определяются точно так же, как в выражениях (9.20) и (9.21), то из соотношения (9.68) имеем

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

Следовательно, коэффициенты в двух показателях в неравенстве (9.181) монотонно изменяются с в противоположных направлениях. При этих условиях, в силу равенства (9.179), правая часть неравенства (9.181) приближенно минимизируется, если положить х

откуда получаем

где

Последние два выражения совпадают соответственно с верхней частью неравенства (9.136) и с неравенством (9.137) в утверждении теоремы.

Важно заметить, что равенство (9.185) определяет значение параметра как функции и тем самым устанавливает

связь между скоростью передачи и коэффициентом а в показателе, задаваемым выражением (9.187). С другой стороны, равенство (9.185) справедливо только для следовательно, для скоростей передачи где критическая скорость, определяемая равенством (9.139) и соответствующая коэффициенту в показателе, также определяемом равенством (9.139).

Далее мы видим, что правая часть (9.184) обращается в нуль для так что максимальное значение, принимаемое коэффициентом при в показателе в неравенстве (9.178). Кроме того, соответствует в неравенстве (9.171), а следовательно, в выражении (9.172). Таким образом, для мы можем в выражении (9.155) заменить на V без существенного ослабления верхней границы. Это равносильно предположению, что так что выражения для и задаваемые соотношениями (9.115) и (9.116), сводятся к

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

что совпадает с нижней частью неравенства (9.136) в утверждении теоремы.

Наконец, из соотношений (9.182) и (9.183) вытекает, что монотонно убывает, а а монотонно возрастает с возрастанием Из выражений (9.53) и (9.54) видно, что как так и а неотрицательны. Ч. Т. Д.

Верхняя граница средней вероятности ошибки зависит главным образом от коэффициента при в показателе. Точнее,

где

и

Сравнение соотношений (9.191) и (9.192) с соотношениями (9.29) и (9,28) показывает, что при выражения для и совпадают с выражениями для определяющими асимптотики нижней границы вероятности ошибки для кодов с фиксированной композицией.

Рис. 9.4. Соотношение для фиксированной композиции (сплошная линия) и оптимальной композиции (пунктирная линия).

Следовательно, верхняя часть равенства (9.191) в сочетании с равенством (9.192) дает точную асимптотику наименьшей вероятности ошибки, которая может быть достигнута при заданной скорости и заданной композиции входной последовательности. Однако при асимптотика зерхней границы отличается от асимптотики нижней границы.

Характер зависимости а и от для входных последовательностей с фиксированной композицией показан на рис. 9.4 сплошной кривой. Как видно из нижней части неравенства (9.191), участок кривой, соответствующий есть прямая с наклоном, равным —1. Так как для эта кривая

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

Таким образом, и при т. е. при этот наклон меняется непрерывно.

Рассмотрим далее оптимизацию композиции входной последовательности, т. е. найдем композицию определяющую наибольшее значение для любой заданной скорости При и отождествлении с величиной задаваемой выражением (9.28), коэффициент а и Для верхней границы совпадает с задаваемым выражением (9.29) коэффициентом в выражении для нижней границы. Поэтому для такой области значений оптимальная композиция входной последовательности определяется теоремой, содержащей формулу (9.86). Кроме того, поскольку наклон прямолинейного участка кривой зависимости от не зависит от оптимальная композиция для меньших значений определяется той же теоремой для

Из выражений (9.96) и (9.97) получаем для

и

откуда в свою очередь вытекает, что

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

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

в которой наклон становится равной —1. Для оптимальное соотношение определяется прямой с наклоном —1. Итак, доказана следующая фундаментальная теорема.

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