4.3. Дистанционные свойства сверточных кодов для каналов с двоичным входом

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

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

(кодер, решетка и диаграмма состояний которого приведены соответственно на рис. 4.2а, 4.4 — и 4.5). Вначале перерисуем решетку, как это показано на рис. 4.8, помечая ребра в соответствии с их расстояниями от нулевого пути.

Рассмотрим все пути, которые впервые сливаются с нулевым путем в узле который выберем произвольно. Из диаграммы видно, что среди этих путей найдется только один, который будет находиться на расстоянии 5 от нулевого пути и что этот путь ответвляется от нулевого пути в узле, отстоящем от выделенного узла на три ребра назад. Аналогично, имеются два пути на расстоянии 6 от нулевого пути; один из них ответвляется от нулевого пути в узле, отстоящем от выделенного узла на четыре ребра, а другой — в узле, отстоящем на шесть ребер назад, и т. д. Заметим также, что информационными символами упомянутого пути с расстоянием 5 являются как видим, они отличаются от информационных символов нулевого пути (естественно, что все они являются нулевыми) лишь в одной позиции. Информационными символами двух путей с расстоянием 6 являются соответственно последовательности которые отличаются от информационных символов нулевого пути в двух входных двоичных символах. Таким образом, минимальное расстояние между всеми путями решетки, называемое иногда свободным расстоянием кода, в данном случае равно 5. Это означает, что любая пара ошибок в ДСК может быть исправлена, так как при любых двух и меньше ошибках принятая последовательность будет находиться на расстоянии самое большее 2 от переданной (правильной) последовательности и на расстоянии самое меньшее 3 от любой другой кодовой последовательности. Представляется, что при наличия терпения с помощью решетчатой диаграммы можно определить расстояние от любого пути до нулевого.

Рис. 4.8 Решетчатая диаграмма (на ребрах указано расстояние до нулевого пути)

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

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

Рис. 4.9. Диаграмма состояний (на ребрах указано расстояние до нулевого пути)

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

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

где вспомогательные переменные для неполных путей в промежуточные узлы; входной символ узла а равен единице, а выходной — это искомая порождающая функция Решая систему уравнений (4.3.1) относительно находим

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

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

Рис. 4.10. Диаграмма состояний (на ребрах указано расстояние до нулевого пути, длина и число символов I во входном блоке)

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

Отсюда следует, в частности, что из двух путей на расстоянии 6 от нулевой последовательности один имеет длину 4, другой — длину 5 и оба отличаются в двух .входных символах от нулевой входной последовательности. Следовательно, если правильным был нулевой путь и из-за шума приходится выбрать один из двух упомянутых путей, то в результате будут сделаны две ошибки. Аналогично, среди путей, находящихся на расстоянии 7 от нулевой последовательности, один имеет длину 5, два — длину 6 и один — длину 7; все эти пути соответствуют входным последовательностям с тремя единицами. Если мы интересуемся уровнем, то ясно что необходимо учесть приведенный выше ряд таким образом, чтобы он не содержал членов со степенями, большими, чем

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

же техника применима к любому двоичному коду с произвольной длиной кодового ограничения и с произвольной скоростью Однако в случае каждое уравнение состояния типа (4 3 1) связывает не более переменных . В общем случае получим переменных и столько же уравнений (Другие примеры рассматриваются в задачах следующих двух параграфах будет показано, каким образом порождающая функция может быть использована непосредственной оценки вероятности ошибки декодера Витербн, работающего с произвольным сверточным кодом в канате без памяти с двоичным входом