3.3. Средняя вероятность ошибки по ансамблю с выбрасыванием: верхняя граница при малых скоростях

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

При выводе границы с выбрасыванием удобно работать не со средней по ансамблю вероятностью а со средней по ансамблю вероятностью, возведенной в дробную степень при Граница формулируется в виде леммы.

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

где

Сумма всех таких средних по ансамблю, следовательно, ограничена неравенством

Доказательство. Вывод неравенства (3.3.1) основан на соображениях, использованных в § 3.1. Прежде всего, коль скоро нас интересуют главным образом малые скорости, мы ограничимся применением аддитивной границы Бхаттачария, совпадающей с более тонкой границей Галлагера при Из (3.1.4) имеем

Но, ограничившись значениями из единичного интервала, мы можем воспользоваться неравенством

которое следует из неравенства Гельдера (см. приложение 3А), что дает нам границу

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

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

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

Лемма 3.3.2. Хотя бы в одном коде ансамбля всех кодов с векторами, состоящими из N символов, неравенство

выполняется по крайней мере для его кодовых векторов где В определено в лемме 3.3.1 при значении

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

Отсюда следует, что сумма по всем кодовым векторам от моментов, усредненных по ансамблю, ограничена снизу неравенством

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

что противоречит неравенству (3.3.2) леммы 3.3.1 при Это противоречие доказывает лемму

Из последней леммы вытекает, что, выбросив М кодовых векторов с наибольшими вероятностями ошибки из кода, удовлетворяющего условию (3.3.7) леммы 3.3.2, приходим к коду, в котором всего кодовых векторов размерности таких, что

где невыброшенные векторы обозначены через . Справедливость (3.3.9) следует из того, что у невыброшенных векторов вероятность ошибки, хотя и изменится при выбрасывании, но может стать только меньше, поскольку выбрасывание каких-либо кодовых векторов может привести только к расширению оптимальных областей декодирования. Комбинируя (3.3.9) с (3.3.1), получим явное выражение границы с выбрасыванием. Если еще подставить где то выражение станет удивительно похожим по форме на теорему кодирования (см. § 3.2). Действительно, для каждого сообщения после выбрасывания будем иметь

Если теперь наложить на канал условие отсутствия памяти (3.1.12)

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

то, следуя выводу (3.1.14), получим

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

Теорема 3.3.1. Теорема кодирования с выбрасыванием (Галлагер [1965]). Для канала без памяти с дискретным входом существует по крайней мере один код с кодовыми векторами размерности в котором для каждого сообщения вероятность ошибки при использовании декодирования по максимуму правдоподобия ограничена неравенством

где

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

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

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

Равенство (3.3.15) следует непосредственно из соотношений (3.3.14) и (3.2.1), поскольку

Оставшаяся часть теоремы, касающаяся неравенств, совпадающих по форме с неравенствами для доказана в приложении 3А.

Заметим также, что функции служат границами друг для друга на непересекающихся интервалах, кроме точки где обе функции совпадают. На рис. 3.5 приведены

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

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

Рис. 3.5. Функции для типичного канала

Рис. 3.6. Составная функция показателя экспоненты

В рассматриваемой области, следовательно, показатель экспоненты в правой части (3.3.12) при фиксированном задается параметрическими соотношекиями

Кроме того, проделав те же преобразования, что и при получении (3.2.9) и (3.2.10), имеем

так что показатель экспоненты является выпуклой 11 функцией с отрицательным наклоном, по модулю равным в области, заданной (3.3.20). Кроме того, в точке

прямая линия

является касательной к показателю экспоненты, рассматриваемому как функция

Функция, составленная из функций и для типичного канала) приведена на рис. 3.6. Для всех физических каналов ограничена при всех скоростях так, как это показано, например, на рис. 3.6. Однако для некоторых каналов, не имеющих физического смысла, но все же интересных (см. пример на рис. 3.7), функция) становится неограниченной при достаточно малых, но положительных скоростях.

Рис. 3.7. Составная функция показателя экспоненты для канала

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

Поведение обоих классов каналов при малых скоростях можно определить, исследуя и ее первую производную в пределе при Отметим, что (3.3.21) справедливо только для скоростей, больших предельного значения ее производной. Эту величину легко получить из определения (3.3.14), воспользовавшись правилом Лопиталя:

где

Следовательно,

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

для некоторой пары входных символов такой, что В последнем случае мы видим также, что поскольку в соответствии с (3.3.22) наклон стремится к при функция стремится к бесконечности при стремлении справа к следовательно, остается бесконечной и при всех меньших скоростях. Пример такого показателя экспоненты и соответствующего ему канала, который представляет собой пару непересекающихся ДСК, показан на рис. 3.7 (см. задачу 3.9). Интуитивное объяснение этому физйчески бессмысленному результату заключается в том, что если у канала есть такие два входных символа и хотя бы один выходной символ, который может появиться на выходе канала при передаче одного из входных, но не может появиться при передаче другого, то, пользуясь только этими входными символами, мы можем добиться безошибочной связи даже без кодирования.

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

Применив правило Лопиталя, имеем

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

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

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

Далее, при из (3.3.27) получим для (1/2, 1/2), что

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