6.3. Верхняя граница вероятности ошибки

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

то неправильный путь даже не будет сравниваться с правильным путем в этой точке. Это утверждение можно сформулировать в той же форме, что и лемму 6.2.1.

Лемма 6.3.1. Выбор неправильного пути ответвляющегося от правильного пути в узле и сливающегося с ним вновь в узле приводит к ошибке, только если

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

С этого момента большая часть вывода в значительной степени совпадает с соответствующими выкладками предыдущего параграфа. Имеется, однако, одно существенное различие. Так, если в § 6.2 через обозначался любой путь из неправильного подмножества, то здесь так обозначен лишь путь, который сливается с правильным в узле Таким образом, выкладки доказательства леммы 6.2.2 по существу сохраняются, как и сама лемма, но множество должно быть заменено на объединение подмножеств где подмножество, включающее в себя все пути из которые сливаются с правильным путем в узле Отсюда следует лемма.

Лемма 6.3.2. Вероятность ошибки на узел в узле ограничена сверху неравенством

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

X

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

где, как и в (6.2.3),

Таким образом, если для заданного у, то

для некоторого Следовательно, для этого у

Если то доказательство справедливости неравенства правого и левого выражений (6.3.5) тривиально. При этом можно оценить сверху точно так же, как и ранее, с помощью (6.2.5). Подставляя оценку (6.3.5) для и (6.2.5) для из 6.3.4) получаем

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

Из (6.3.6) и (6.3.7) следует (6.3.2). Для того чтобы найти среднее число двоичных ошибок, порождаемых ошибкой в узле, как и в § 5.1, воспользуемся тем, что число двоичных ошибок, порождаемых неправильным путем, не совпадающим с правильным на протяжении ребер, не может быть больше, чем [так как последние ребер или символов неправильного пути должны быть такими же, как и у пра вильного]. Следовательно,

Из (6.3.6) и (6.3.8) следует (6.3.3); это завершает доказательство лемм

Если усреднить (6.3.3) по тому же ансамблю кодов, что и в § 6.2, ограничить область изменения параметра единичным интервалом и воспользоваться неравенством Иенсена, то получим

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

И, наконец, так как в силу (5.1.32) то, полагая приходим к следующей лемме.

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

где

Функция идентична функции, введенной в § 6.2, и, как там уже показано, для всех

где

Итак, полагая получаем следующую границу суммы, входящей в (6.3.10):

При как обычно, полагаем Таким образом, используя обозначения § 5.1 [см. (5.1.34)]

и полагая получаем следующую теорему.

Теорема 6.3.1. Вероятность ошибки при последовательном декодировании (Юдкин [1964]). Средняя по ансамблю вероятность ошибки на бит при последовательном декодировании меняющегося во времени сверточного кода со скоростью ограничена сверху неравенством

где определяется выражением (5.1.34) и

Показатель экспоненты правой части (6.3.12) имеет тот же вид, что и показатель экспоненты (5.1.32) верхней границы для декодера Витерби при больших скоростях (если не считать того, что число связано здесь с в то время как в (5.1.32) оно могло быть произвольным положительным). В то же время при малых скоростях показатель экспоненты уменьшается со значения до единицы. Этот показатель можно было бы увеличить точно так же, как и в (6.2.22), путем выбора другого значения смещения заменяется на в выражении для метрики (6.1.2), однако при этом ухудшается распределение числа операций при больших скоростях (см. задачу 6.2).

Есть еще один вопрос, который должен быть решен. Хотя в §6.2 доказано существование кода, для которого а из теоремы 6.3.1 следует, что существует код, для которого вероятность ограничена сверху с помощью (6.3.12). Вообще говоря, остается неясным, могут ли обе эти границы выполняться одновременно для одного и того же кода. Решить эту дилемму можно рассуждая так же, как в § 3.2. Предположим на время,

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

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

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