5.4. Нижняя граница для вероятности ошибки

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

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

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

где

Из (5.4.1) — (5.4.5) следует:

Здесь берем достаточно большим, так чтобы параметр X мог быть любым рациональным числом; возникающие при этом неточности могут быть учтены в членах порядка Для того чтобы минимизировать показатель экспоненты, необходимо взять нижнюю огибающую по X функции которая определяется, параметрически (5.4.4). Покажем, что эта функция выпукла следовательно, минимум можно найти, приравняв производную нулю. Из (5.4.4а) имеем

так как из (5.4.46) следует, что

Дифференцируя (5.4.7) и используя (5.4.8) и (3.2.5), получаем

Таким образом, можно положить (5.4.7) равным нулю и найти абсолютный минимум как функцию Имеем

Комбинируя (5.4.10) и (5.4.46), находим

При этом из (5.4.6), (5.4.11) и (5.4.12) получаем

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

Теорема 5.4.1. Нижняя граница для сверточного кодирование (Витерби [1967а]). Вероятность ошибки на бит для произвольного сверточного кода и любого алгоритма декодирования ограничена снизу неравенством

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

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

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

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

где задается формулой (3.3.27) (см. также § 5.3). Этот результат можно также сформулировать следующим образом:

Следствие 5.4.1. Нижняя граница при малых скоростях. При более точной границей для вероятности ошибки на бит, чем та, что дается теоремой 5.4.1, является граница

где скорость, при которой

График показателя экспоненты этой границы для типичного симметричного по выходу канала с двоичным входом приведен на рис. 5.5, где для сравнения приведен также график показателя экспоненты верхней границы для малых скоростей; последняя граница справедлива только для этого класса каналов. Заметим, что можно было бы воспользоваться также нижней границей для малых скоростей, приведенной в § 3.8 (Витерби [1967]), но это

привело бы к тому же результату, что и использование границы (5.4.17).

В заключение остановимся кратко на возможности получения границ, которые были бы асимптотически точными при всех скоростях. Рассуждения, приведенные в § 3.9 для блочных кодов, с тем же успехом могут быть применены и к сверточным кодам. Если граница Гилберта точна [предположение (3.9.4)], то получающаяся в результате нижняя граница [см. (3.9.5)] может быть использована вместо границы (5.4.4), что при малых скоростях приведет к нижней границе, которая для симметричных по выходу каналов с двоичным входом будет везде совпадать с верхней границей (5.3.13). Таким образом, показатели экспоненты блочного кодирования со всех точек зрения ведут себя точно так же, как показатели экспоненты сверточного кодирования, которые, однако, значительно больше первых во всем диапазоне скоростей передачи