1.2. Порождающая матрица сверточного кода

Из описания кодера или из формулы (1.1) непосредственно следует, что сверточный код является линейным. Это означает, что множество кодовых слов образует линейное пространство полубесконечных двоичных последовательностей. Удобной формой представления блоковых линейных кодов является описание с помощью порождающей матрицы кода, строками которой, как известно, служат базисные векторы кода.

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

Рассмотрим сначала коды со скоростью 1/n. Заметим, что информационные последовательности вида

u₀=[100…];

u₁=[010…];

…

образуют в совокупности базис линейного пространства входных последовательностей кодера, поскольку любая информационная последовательность может быть представлена в виде линейной комбинации u_i , i=1,2,…. Каждой линейной комбинации информационных последовательностей u_i соответствует кодовая последовательность, равная линейной комбинации кодовых слов, соответствующих u_i . Отсюда следует, что кодовые слова, соответствующие этим информационным последовательностям, образуют базис в пространстве кодовых слов. Из (1.1) следует, что порождающая матрица сверточного кода может быть записана в виде

(2)

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

1.3. Кодовое дерево сверточного кода и решетчатая диаграмма

Вернемся к коду (5,7), кодер которого показан на рис.2а. Считаем, что начальное состояние кодера было нулевым. Это состояние и все предыдущее мы будем отображать в виде узлов дерева. Возможные переходы из состояния в состояние соответствуют ребрам дерева. Каждому такому ребру соответствует некоторый блок из n=2 кодовых символов. Несколько начальных ярусов дерева, соответствующего коду (5,7), показано на рис. 3. Это дерево называют кодовым. В связи с такой графической интерпретацией сверточного кода параметр называют длиной ребра кода.

По кодовому дереву легко определить кодовое слово, соответствующее заданной информационной последовательности. На рис. 3 движение вверх соответствует информационному символу 0, движение вниз - символу 1. Например, информационной последовательности 010110… соответствует кодовое слово 00111000…

Обращает на себя внимание то, что число узлов дерева быстро растет от яруса к ярусу. В то же время, каждому узлу соответствует некоторое состояние кодера. Число различных состояний кода со скоростью 1/n и с длиной кодового ограничения m в точности равно 2^m . Следовательно, начиная с яруса с номером m+1 , найдутся узлы соответствующие одинаковым состояниям. Поддеревья, начинающиеся в этих узлах, полностью идентичны. Чтобы сделать графическое представление кода более компактным, имеет смысл объединить узлы, соответствующие одинаковым состояниям и отображать их в виде одного узла.

Рис. 4. Решетчатая диаграмма кода (5,7)

Рис. 5. Конечный автомат, описывающий работу кодера кода (5,7)