Глава 3. АНАЛИЗ ХАРАКТЕРИСТИК АНСАМБЛЯ БЛОЧНЫХ КОДОВ

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

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

границы; аддитивную Бхаттачария (2.3.16) и Галлагера (2.4.8). Такие границы применимы к любому набору сигналов. Вычисление этих границ для конкретных наборов сигналов, отличных от тех немногих, которые перечислены в § 2.11, все же оказывается чрезвычайно трудным, особенно если речь идет о больших объемах наборов сигналов и больших размерностях Следовательно, безнадежно искать оптимум при фиксированных коль скоро мы столкнулись с трудностями при анализе конкретных наборов сигналов. Выход из создавшейся ситуации фактически был указан Шенноном [1948]. Он первым воспользовался центральным методом теории информации, который теперь не совсем обоснованно называют случайным кодированием. Основа метода очень проста: если подсчет вероятностей ошибок для конкретного набора сигнальных (или кодовых) векторов размерности N неосуществим, то рассматривается средняя вероятность ошибки по ансамблю всех возможных наборов из сигналов размерности Вычислить хорошую верхнюю границу для такого среднего по всему ансамблю очень легко. Очевидно, что по крайней мере для одного из наборов сигналов вероятность ошибки не превышает среднего по ансамблю. Следовательно, среднее по ансамблю служит верхней границей для вероятности ошибки оптимального набора сигналов (или кода) размерности Но для большинства скоростей эта граница асимптотически точна, что мы и продемонстрируем, вычислив нижнюю границу в последней части этой главы.

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

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

возможным наборам сигналов. Тогда среднее по ансамблю получим, разделив сумму на число наборов.

С целью дальнейших обобщений перепишем (3.1.1) в виде

где конкретное распределение на будет выбрано ниже.

Рассмотрим формулу (3.1.1), которая соответствует равномерному взвешиванию, т. е. распределению

в § 2.4 получена верхняя граница для конкретного набора сигналов, а именно граница

Эта граница Галлагера обобщает аддитивную границу Бхатта-чария (см. § 2.3) и сводится к последней при Для простоты преобразований ограничимся случаем, когда Подставив затем (3.1.4) в (3.1.2) и поменяв порядок суммирования, получим в качестве верхней границы вероятности ошибки в ансамбле при условии, что передано сообщение 1, следующее неравенство

Далее ограничим произвольный параметр единичным интервалом Сконцентрировав внимание на члене в скобках в неравенстве (3.1.5), введем функцию

Из неравенства Иенсена приложение имеем

поскольку при выпуклая функция при всех х. Здесь

Теперь, воспользовавшись (3.1.6), можем вычислить правую часть неравенства (3.1.7), что приводит к равенствам

Последнее равенство следует из того, что суммирование по каждому из векторов ведется в одном и том же пространстве Комбинируя неравенства (3.1.5) и (3.1.7) с равенством (3.1.9) и замечая, что множители слагаемых в неравенстве (3.1.5) неотрицательны и что, оценив сверху любой из них, мы оценим сверху и сумму, получим

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

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

ортогональных сигналов, используемых в АБГШ канале (см. § 2.5). Эта аналогия станет еще более явной в следующем параграфе.

Для канала без памяти вероятность ошибки запишется

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

[что справедливо для частного случая (3.1.3), где то, подставив (3.1.12) и (3.1.13) в (3.1.11), для канала без памяти получим

где вероятность перехода для символа (плотность). [В частном случае для всех

Прежде чем перейти к выводу следствий из простого и изящного неравенства (3.1.14), несколько обобщим его. Мы начали с равенств (3.1.1) и (3.1.2), выбрав при усреднении по ансамблю всех возможных кодовых наборов сигналов равномерное распределение. Ясно, однако, что для некоторых каналов и некоторых наборов сигналов один выбор может оказаться лучше другого. При вычислении среднего, когда конечная цель состоит в оценке качества лучшего члена ансамбля, будет логичным, если, основываясь на некоторой информации извне или интуиции, мы захотим приписать больший вес некоторым сигнальным векторам (или некоторым множествам сигнальных векторов, или определенным символам, или компонентам сигнальных векторов). Подходящий, хотя и банальный пример: средняя успеваемость группы студентов как нижняя граница успеваемости лучшего студента. Если, однако, опыт преподавателя подсказывает ему, что у рыжих зеленоглазых студентов оценки обычно оказываются выше средних, а у красноглазых студентов с зелеными волосами, как правило, хуже, он может вычислить взвешенное среднее, приписав оценкам студентов из первой группы, большие, из второй группы — меньше, остальным студентам — промежуточные веса. Единственное

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

Такой априорный перекос в (3.1.2) можно легко получить, допустив, что любое распределение на множестве возможных сигнальных векторов. Можно, следовательно, рассматривать (3.1.2) как взвешенное среднее по ансамблю, причем взвешивание наборов сигналов — членов ансамбля — задается произведением мер То же можно сказать и обо всех остальных усреднениях по ансамблю, используемых при выводе неравенства (3.1.11). Для каналов без памяти, определенных (3.1.12), выбор весов мы ограничим формулой (3.1.13), что соответствует независимому взвешиванию каждой компоненты каждого кодового слова в соответствии с Для многих классов каналов, включая все симметричные по выходу с двоичным входом, неравномерное взвешивание не уменьшает границу средней по ансамблю вероятности ошибки. Для таких каналов, как -канал (см. задачу 3.1), при некоторых скоростях передачи данных достигается существенное улучшение границы. Ясно, что если, используя неравномерное взвешивание, удалось снизить среднее, то и лучший набор сигналов должен быть лучше нового среднего. Преимущества неравномерного взвешивания проявляются, как правило, при наличии перекоса в канале.

Можно также выразить границу (3.1.14) через скорость передачи данных, приходящихся на одно измерение

которая, очевидно, связана со скоростью в натах в секунду (см. § 2.5) соотношением

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

где

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

обладающий свойствами для всех и

Заметим, наконец, что поскольку неравенство (3.1.17) — граница для вероятности ошибки при передаче любого сообщения, то, следовательно, она должна быть оценкой и для полной вероятности ошибки Независимо от априорных вероятностей сообщений, если только используется решающее правило по максимуму правдоподобия. Можно, учитывая произвольность выбора в единичном интервале и произвольность выбора как вектора распределения, подчиняющегося ограничениям (3.1.19), оптимизировать границу по этим параметрам и получить наиболее точную оценку. Это достигается с помощью максимизации взятого со знаком минус показателя экспоненты в правой части (3.1.17). В результате получим, что средняя вероятность ошибки по ансамблю всех возможных наборов сигналов для канала без памяти с входами ограничена неравенством

где

определена соотношением (3.1.18), вектор распределения, удовлетворяющий ограничениям (3.1.19). Очевидное следствие состоит в том, что по крайней мере один набор сигналов в ансамбле имеет вероятность не превосходящую границу среднего по ансамблю.

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