5.8.2. Способы задания сверточного кода

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

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

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

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

где    , , ... , – известные двоичные коэффициенты; суммирование проводится по модулю 2.

2. Последовательность проверочных символов  находится с помощью порождающего многочлена

по формуле

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

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

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

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

4. Для сверточного кода могут быть построены порождающая и проверочная матрицы. По сравнению с теми же матрицами блочного кода эти матрицы (как кодируемая и принятая последовательности) полубесконечны.

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

1. Проверочный символ определяется через информационные линейным рекуррентным соотношением

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

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

Используя (5.39), получим  , что соответствует , , , , .

3. Графические способы задания поясним по схеме кодера, для построения которого следует пользоваться заданием сверточного кода с помощью соотношения (5.41) или порождающего многочлена .

Схема кодирующего устройства приведена на рис. 5.8. Кодер представляет собой линейную систему (со сложением по модулю 2), отклик которой на входную единицу равен (11), что соответствует коэффициентам многочлена . При подаче на вход информационной последовательности выходная последовательность образуется в соответствии с (5.41). Слово систематического сверточного кода формируется с помощью электронного ключа , который поочередно подключает шины информационных и проверочных символов к выходу. Такт работы ключа в два раза меньше такта поступления и сдвига информационных символов.

Схема на рис. 5.8 позволяет пояснить задание сверточного кода с помощью решетки. Решеткой называется граф, узлы которого находятся в полубесконечной прямоугольной координатной сетке и связаны ребрами. Число узлов в каждом столбце конечно, а конфигурация ребер, соединяющих узлы каждого столбца с узлами следующего столбца, одинакова для всех столбцов. Каждый столбец отображает набор возможных состояний кодера. Поэтому ребра показывают изменение состояния кодера при подаче на вход новою информационного символа. Маркировка ребер соответствует последовательности кодовых символов, передаваемых в канал связи, т.е. комбинации элементарного блока из  символов.

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

Решетка описывает код в том смысле, что каждой последовательности информационных символов соответствует свой путь по решетке, а маркировка ребер, составляющих этот путь, дает кодовое слово. Так, ранее рассмотренной последовательности 01011 соответствует путь и кодовое слово 00 11 01 11 10, в котором последовательность проверочных символов совпадает с получаемой согласно (5.40).

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

Пример 5.16. Пусть дан несистематический сверточный код с параметрами , , скоростью , кодовым ограничением . Он задается многочленами  и .

Схема кодера приведена на рис.5.10. В отличие от примера 5.14 кодовое слово состоит из элементарных блоков, не содержащих информационные символы. Первые символы каждого блока  являются сверткой информационной последовательности и многочлена , а вторые  - сверткой той же последовательности и многочлена . Заметим, что если один из многочленов приравнять 1, то получим систематический сверточный код.

Кодовая решетка, построенная по правилам примера 5.14, показана на рис. 5.11.

Кодер имеет 2-разрядный сдвигающий регистр с четырьмя состояниями, следовательно, столбцы решетки содержат по четыре узла, помеченных содержимым регистра. Поэтому левый символ в обозначении узла равен последнему информационному символу, поступившему в регистр. Порядок обозначения узлов выбран так, что при  регистр переходит в следующее состояние по верхнему ребру, а при  – по нижнему. Маркировка ребер совпадает с комбинацией элементарного блока, посылаемого в канал. По-прежнему информационной последовательности соответствует путь на кодовой решетке и кодовое слово. Если входные символы 0 1 1 0 , то по решетке находим кодовое слово 00 11 01 01.