6.1. Двоичные сверточные коды со скоростью 1/2

Сверточный кодер с кодовым ограничением k представляет собой регистр сдвига с k ячейками, в котором символы кодовой последовательности формируются суммированием по модулю 2 символов с выходов некоторых ячеек. Простой пример сверточного кодера со скоростью 1/2 показан на рис. 6.1. Информационные символы на схеме поступают слева, и для каждого информационного символа на выходах двух сумматоров по модулю 2 образуются два выходных символа. Связь между ячейками регистра сдвига и

Рис. 6.1. Кодер для сверточного кода со скоростью 1/2 и с кодовым ограничением 3

сумматорами удобно описывать порождающими многочленами: верхний и нижний сумматоры представляются соответственно многочленами (степени растут слева направо, так что самая левая ячейка соответствует свободному члену). Информационную последовательность можно также представить в виде степенного ряда где информационный символ (равный 0 или 1). При таком представлении символы на выходе сверточного кодера могут быть получены путем умножения входной последовательности на порождающие многочлены кода. Например, последовательность символов на выходе сумматора, изображенного в верхней части рис. 6.1, может быть представлена в виде где умножение многочленов производится над полем

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

Название метода кодирования позволяет также предположить, что последовательность на выходе кодера можно рассматривать как свертку импульсной характеристики кодера с входной последовательностью. Если, например, в кодер, схема которого приведена на рис. 6.1, поступает один символ 1, за которым следуют символы соответствующая выходная последовательность имеет вид Читатель может убедиться, что выходная последовательность, соответствующая произвольной выходной последовательности, получается сложением по модулю 2 сдвигов указанной последовательности. Поэтому порождающая матрица может быть представлена в виде

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

Таким образом, выходная последовательность, соответствующая получается сложением строк 1, 2 и 3 матрицы что дает

Другой удобный способ описывать связь между входными и выходными последовательностями состоит в использовании кодового дерева, аналогичного изображенному на рис. 6.2. Каждое ребро этого дерева соответствует некоторому входному символу. При этом входной символ 0 соответствует верхнему ребру, а 1 - нижнему.

Рис. 6.2. (см. скан) Дерево для сверточного кода с кодовым ограничением 3. В каждой паре верхняя ветвь соответствует входному символу 0, нижняя 1

Таким образом, каждая входная последовательность задает некоторый путь на дереве. В частности, входная последовательность 10 110 задает выходную последовательность 1 10 10 0 10 10. Соответствующий путь показан на рис. 6.2. Ясно, что при росте длины входной последовательности число возможных путей растет экспоненциально, так что роль такой диаграммы сводится лишь к облегчению понимания.

К счастью, экспоненциальный рост объема можно ограничить, если заметить, что структура сверточного кода является периодической. На рис. 6.2 каждая вершина кодового дерева помечена числом от 0 до 3 в соответствии с содержимым двух левых ячеек кодового регистра в данной вершине дерева (младший разряд записывается левее). Это число называется состоянием кодера. Заметим, что ребра, выходящие из любых двух вершин, характезируемых одинаковым состоянием, полностью тождественны. Например, верхнее и нижнее поддеревья на уровне 3 рассматриваемого дерева являются одинаковыми. Поэтому их можно отождествить. Аналогично на уровне 4 имеется четыре множества по четыре вершины в каждом, которые можно отождествлять. Такая возможность отождествлять пути, приводящие к одному и тому же состоянию, лежит в основе алгоритма Витерби.