5.4 ВЕРОЯТНОСТНОЕ МАЖОРИТАРНОЕ ДЕКОДИРОВАНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ

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

Вероятностное мажоритарное декодирование реализуемо, если внешние коды являются мажоритарными. Это декодирование называется и состоит из независимых шагов Возможно применение на последовательных шагах различных алгоритмов Будем рассматривать применительно только к CKKI, так как в случае может нарушиться независимость символов, входящих в одну проверку. Это не исключает возможности использования с алгоритмом Чмаж, но требует специального подбора кодов При описании общего алгоритма на шаге для простоты рассмотрим СКК на основе ОК кода 1-го порядка [6]. Результаты можно без труда сообщить на случай произвольных и шага декодирования.

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

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

где вектор жестких проверок. Алгоритм по максимому правдоподобия должен выносить решение если для всех (здесь под GF(Q) понимаем произвольный алфавит внешнего кода).

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

Обозначим через вероятность того, что ошибка проверки относительно символа примет значение . В дальнейшем рассмотрим -ичный симметричный канал (по определению, данному в разд. 2.1 для внешнего кода). Алгоритм для несимметричного канала возможен, но требует некоторого формального усложнения описания алгоритма. В случае -ичного симметричного канала для внешнего кода вероятности не зависят от значения декодируемого символа, т. е.

Следовательно, алгоритм по максимуму правдоподобия Чмаж должен выносить решение если для всех

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

Для каналов с равновероятными ошибками вероятности принимают одинаковые значения для всех

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

Легко видеть, что в двоичном канале получаем (3.11).

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

где Более удобным является следующее рекуррентное уравнение:

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

С учетом рассматриваемой модели канала каждая из вероятностей в формулах (5.17), (5.18) может быть найдена из соотношения

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

Утверждение 5.2. Пусть в -ичном симметричном канале для внешнего кода ошибки равновероятны и вероятность того, что символ проверки ошибочен, т. е. Тогда

где число символов, участвующих в проверке системы (3.7). Доказательству утверждения предпошлем следующую лемму [6].

Лемма 5.1. Для произвольных чисел справедливо тождество

Доказательство. Подставим (5.15) в (5.21). В результате получим

Применяя рекуррентное соотношение (5.22) многократно, окончательно получаем

Теперь воспользуемся леммой 5.1, в которой положим . В результате получится первое соотношение в (5.21), соответствующее Второе соотношение в (5.21) вытекает из первого и соотношения (3.15). Утверждение доказано.

Утверждение 5.3. Вероятность ошибки декодирования в симметричном по выходу канале без памяти удовлетворяет следующему неравенству:

Доказательство. Рассмотрим -ичный симметричный канал внешнего кода с входным множеством выходным множеством и переходными вероятностями

Используя стандартные рассуждения [24], можно получать следующую оценку условной вероятности ошибки при передаче символа

Учитывая независимость результатов проверок при данном значении декодируемого символа, а также соотношения (5.13), получаем утверждение.

Следствие 5.2. Для -ичного симметричного канала без памяти с равновероятными ошибками вероятность ошибочного декодирования удовлетворяет следующему неравенству:

где

Доказательство. С учетом соотношения (5.15), можно записать

Оптимальное значение параметра минимизирующее правую часть последнего соотношения, равно 1/2. Поэтому

откуда и вытекает доказываемое утверждение.

Для каналов с равновероятными ошибками имеет место следующий результат.

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

Доказательство опирается на следующее общее утверждение, сформулированное в виде леммы [6].

Лемма 5.2. Для произвольных чисел каждое из которых принадлежит отрезку [0, 1], имеет место неравенство

Доказательство. Обозначим

Тогда Учитывая, что из (5.26) и (5.29) получаем неравенство

Воспользуемся теперь леммой 5.2 и оценим величину с учетом (5.29). В результате получим неравенство (5.27). Утверждение доказано.

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

Следствие 5.3. Вероятность ошибки декодирования в -ичном симметричном стационарном канале без памяти с равновероятными ошибками для внешнего кода удовлетворяет неравенству

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

Утверждение 5.5. Средняя вероятность ошибки и средний корень из вероятности ошибки при принятии решений по методу максимального правдоподобия удовлетворяют следующим соотношениям:

Доказательство. Рассмотрим условные средние при значении передаваемого символа, равном

Воспользуемся теперь наличием симметрии канала по выходу. Из соотношения (2.16) следует, что для каждого можно найти отображение при котором область переходит в

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

В силу независимости от получаем соотношение (5.32). Аналогичная замена переменных в интегралах дает

что, очевидно, эквивалентно соотношениям (5.32). Заметим, что все рассуждения остаются верными, если заменить на с условием, конечно, что под знаком соответствующих сумм. Аналогично можно получить нижние оценки вероятности ошибочного декодирования [6].

Утверждение 5.6. Вероятность ошибки декодирования в симметричном по выходу канале для внешнего кода удовлетворяет неравенству

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

Следствие 5.4. Вероятность ошибки декодирования в симметричном по выходу канале для внешнего кода с равновероятными ошибками удовлетворяет неравенству

Пример 5.3. Рассмотрим каиал с аддитивным белым гауссовским шумом и ансамблем из ортогональных сигналов, демодулируемых по критерию максимального правдоподобия. Выходное множество X такого ансамбля сигналов можно рассматривать как -мерное евклидово пространство, т. е. где случайные величины являются выходами

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

где

Правила получения решающих областей и вычисления вероятности ошибки приводятся в примере 2.8.

Верхняя оценка для получается из соотношений (5.32):

Нетрудно получить, что

Представляет интерес сопоставление декодирования при двух видах решений (жестком и мягком) для одних и тех же кода и числа ортогональных сигналов. Это сопоставление в аналитической форме можно сделать, если предположить, что отношение сигнал-шум велико. показано, что при достаточно большом переход к мягким решениям при мажоритарном декодировании, как и в двоичном канале [47], обеспечивает дополнительный энергетический выигрыш 3 дБ.

В (86] рассмотрена возможность использования на каждом шаге алгоритма квантованного решения на W зон.