6.2. Распределение числа вычислений: верхняя граница

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

Лемма 6.2.1. Неправильный путь неправильном подмножестве может быть обследован за узлом только если

Доказательство. Дальнейшее обследование пути производится в том и только в том случае, если он достигает вершины стека. Можно предположить, что узел правильного пути был достигнут, так как в противном случае неправильное подмножество для узла было бы пустым. Алгоритм гарантирует, что если то неправильный путь не может обследоваться до тех пор, пока путь х не будет обследован до узла, в котором его метрика окажется лежащей ниже следовательно, его положение в стеке окажется ниже, чем у Однако если

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

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

где компоненты принятого кодового вектора, начиная с узла пробегают все возможные значения. Введем функцию

Оценим сверху функцию (6.2.3), заметив, что если для заданного у, то по определению, по крайней мере для путей, следовательно, по крайней мере для путей,

Итак, полагая получаем следующую границу суммы, входящей в (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.3. Среднее по ансамблю распределение числа вычислений в неправильном подмножестве ограничено сверху неравенством

где

сегменты кодовых слов длины ребер соответственно.

Эта граница, очевидно, не зависит от Для того чтобы вычислить правую часть (6.2.9), необходимо рассмотреть отдельно случаи и Как показано на рис. 6.3, в первом случае

длина рассматриваемого сегмента правильного пути больше длины сегмента неправильного пути, а во втором — наоборот. Так как рассматривается канал без памяти, то из определений (6.1.1) — (6.1.3) получаем:

где

где

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

Рис. 6.3. Относительная глубина узлов для уравнения (6.2.9): а) ; б)

Таким образом, принимая во внимание равенство можно переписать в виде

Наконец, применяя неравенство Гельдера (см. приложение 3А) к каждому из слагаемых показателей экспонент и пользуясь определениями (6.2.11) — (6.2.13), находим

где - функция Галлагера, определяемая формулой (3 1.18). Таким образом,

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

Однако согласно если или

Итак, для оба условия сводятся к тому, что

Наконец, выбирая таким образом, что из (6.2.8), (6.2.18) и (6.2.19) получаем

Таким образом, можно сформулировать следующую теорему. Теорема 6.2.1. Существует меняющийся во времени сверточный код со скоростью для которого распределение числа вычислений в неправильном подмножестве (и, следовательно, числа вычислений, необходимых для того, чтобы продвинуться на одно ребро) ограничено сверху неравенством

где А — постоянная; величина, связанная со скоростью параметрическим уравнением

любая положительная константа

Распределение, задаваемое (6.2.20), называется распределением Парето. Заметим, что показатель степени в данном случае стремится к единице при и к нулю при если выбрать

Очевидно, что условие (6.2.19) задает верхнюю границу к для малых скоростей Можно взять и тогда

Однако при малых скоростях можно было бы ожидать более быстрого убывания по Действительно, если отказаться от условия линейности кода, можно получить более сильную границу. Так, для меняющихся во времени решетчатых кодов можно показать (Севидж [1966]), что

где .

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