Главная > Математика > Теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.5. Усиленные оценки для оптимального декодирования

1. В предыдущем изложении декодирование производилось по принципу максимальной функции правдоподобия (7.1.6) или, что то же самое, минимального расстояния (7.1.8). Представляет интерес исследовать, чему будет равна оценка вероятности ошибки, если декодирование производить на основе «расстояния» определенного как-нибудь по-другому. В настоящем параграфе мы будем считать «расстояние» некоторой произвольно

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

Теорема 7.4. Пусть (как в теореме 7.1) имеется канал , являющийся степенью канала Пусть декодирование проводится по принципу минимального расстояния

где заданная функция.

Количество передаваемой информации растет с увеличением по закону

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

Здесь один из корней системы уравнений:

следующие функции:

Кроме того

Предполагается, что уравнения (7.5.4) имеют корни, лежащие в области определения и дифференцируемости функций (7.5.5), (7.5.6), причем

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

Запишем для средней ошибки равенства, аналогичные (7.2.4), но с произвольно заданным расстоянием Будем теперь производить усреднение по в последнюю очередь:

где

и

Подставляя (7.5.9) в (7.5.8) по аналогии с (7.2,5)-(7.2.8), будем иметь

Здесь неравенство нестрогое.

Включив все те случаи, когда обозначим

Тогда из (7.5.10), используя (7.2.11), получаем

Мы опустили здесь номер поскольку выражения в (7.5.10), (7.5.12) оказываются не зависящими от него. Выбирая некоторое граничное значение (не зависящее от и пользуясь неравенством

из (7.5.12) имеем

Усредняя это неравенство по получаем для средней вероятности ошибки оценку

где

(в последнем выражении учтено

Функцию распределения (7.5.16) оценим при помощи теоремы 4.7. В предположении, что имеем

где

— функция (7.5.5).

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

Чтобы получить для нее аналогичную оценку, нужно воспользоваться многомерным обобщением теоремы 4.6 или 4.7, т. е. формулой (4.4.13). Это дает

где — корни уравнений

двумерный характеристический потенциал пер

[см. (7.5.6)]. Предполагается, что

Подставим (7.5.18), (7.5.21) в (7.5.15) и заменим М на Пользуясь свободой выбора постоянной распорядимся ею так, чтобы оценки для обоих членов в правой части формулы

равнялись друг другу. Это даст уравнение

которое вместе с другими уравнениями, вытекающими из (7.5.19), (7.5.22), составляет систему уравнений (7.5.4). Неравенство (7.5.24) при этом перейдет в (7.5.3). Доказательство закончено.

2. Остановимся отдельно на том частном случае, когда настолько далеко от что корень уравнения (7.5.4)] становится положительным. Тогда в неравенстве (7.5.13) в качестве целесообразно выбрать после чего оно примет вид

Вместо будем иметь

[см. (7.5.20); одномерная функция распределения разности

Чтобы применить к неравенству (7.5.25) теорему 4.6, нужно взять характеристический потенциал

который равен в силу (7.5.23). По теореме 4.6 (при усиливающей неравенство замене М на имеем

Здесь отрицательный корень уравнения

Обратимся к уравнениям (7.5.4). Обозначим через такое значение при котором корень равен 0.

Соответствующие этому значению другие корни обозначим через Второе уравнение из (7.5.4) примет вид

Сравнивая (7.5.28) с (7.5.27), видим, что Третье уравнение из (7.5.4) при этом запишется так:

Вследствие этого неравенство (7.5.26) можно записать

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

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

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

функции (7.5.5), (7.5.6) в этом случае можно записать

Далее входящие в (7.5.4) производные приобретают вид

Второе уравнение (7.5.4) будет удовлетворено, если положить

в частности так как при этом каждый член последней суммы обратится в нуль. Согласно (7.5.35), (7.5.36) первое уравнение (7.5.4) в этом случае примет вид

Чтобы удовлетворить этому уравнению, положим

т. е. выберем конкретный вид функции

Тогда суммы в левой и правой частях (7.5.39) отождествятся, и это уравнение сведется к уравнению

Но это уравнение удовлетворяется в силу тех же самых соотношений (7.5.38), (7.5.40), (7.5.42), в чем легко убедиться подстановкой их в (7.5.34).

Итак, удовлетворены два уравнения системы (7.5.4). Оставшееся уравнение вследствие (7.5.38), (7.5.40), (7.5.43) приводится к виду

причем в силу (7.5.34), (7.5.42)

Дифференцируя это выражение или учитывая (7.5.35), получим, что уравнение (7.5.44) можно записать

Остается проверить знаки корней Полагая из (7.5.46) находим граничное значение

которое совпадает с информацией Действительно, вследствие (7.5.33), поскольку

имеем

Анализируя выражение (7.5.46), можно получить, что если Прочие корни вследствие (7.5.38), (7.5.40) равны

Они, очевидно, отрицательны, если т. е., если достаточно близко к Если же корень превосходит 1/2, так что в силу первого равенства (7.5.48) становится положительным,

то следует, вместо (7.5.3) использовать формулу (7.5.30), как об этом говорилось в предыдущем пункте. Значения получаемые из условия согласно (7.5.48) оказываются такими:

«Критическое» же значение получается из уравнения (7.5.46) подстановкой т. е. оказывается равным

или

здесь учтены (7.9.35), (7.5.42)).

Полученные выше результаты можно сформулировать в виде следующей теоремы.

Теорема 7.5. В условиях теорем .7.1, 7.3 существует последовательность кодов такая, что вероятность ошибки декодирования удовлетворяет неравенству

где

— корень уравнения (7.5.46), значение (7.5.49).

Коэффициент в экспоненте (7.5.50) получен подстановкой равенства (7.5.44) в выражение

стоящее в показателе формул (7.5.3), (7.5.30), (7.5.31).

4. Исследуем поведение выражений, приведенных в теореме 7.5, при значениях близких к предельному значению Это исследование позволит сравнить указанные результаты с результатами теоремы 7.3.

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

причем

в силу (7.5.47), (7.5.47а).

Подставляя (7.5.52) в (7.5.51), получаем

Чтобы выразить через подставим (7.5.52) в уравнение (7.5.44), что дает

Учитывая (7.5.53), отсюда имеем

и, разрешая относительно

Подстановка этого выражения в (7.5.54) позволяет найти величину с точностью порядка (

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

который связан с функцией (7.5.33) очевидным соотношением

Производные от (7.5.57) имеют смысл условных семиинвариантов от

[см. формулу (4.1.12)].

Подстановка (7.5.58) в (7.5.45) дает

Стоящее в экспоненте выражение, учитывая (7.5.59), представляем в форме

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

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

Отсюда

Если в выражении (7.5.60) положить то оно в силу (7.5.57) обратится в характеристический потенциал

совпадающий с (7.4.3). Поэтому члены с в (7.5.61) заведомо пропорциональны полным семиинвариантам

где обозначает третий кумулянт.

В дополнение к данным соотношениям из (7.5.61) имеем

Вследствие этого соотношение (7.5.56) принимает вид

Подставим это равенство в формулу (7.5.54), принимающую вид

В результате получим

Здесь мы учли, что согласно третьему равенству (7.5.59)

Сравним этот результат с формулой (7.4.24), которая справедлива в том же приближении. При этом учтем, что

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

В (7.5.63) присутствуют добавочные положительные члены по сравнению с (7.4.24), благодаря которым Следовательно, неравенство (7.5.50) является более сильным, чем неравенство (7.4.2) (по крайней мере, при значениях достаточно близких к Таким образом, теорема 7.5 более сильная, чем теорема 7.3.

Ряд других результатов, дающих усиленную оценку поведения вероятности ошибки декодирования, приведены в книге Фано [1].

<< Предыдущий параграф Следующий параграф >>
Оглавление