Описание сверточных кодов с помощью многочленов и матриц

Сверточный ((m+1)n₀, (m+1)k₀) -код над GF(q) с длиной кодового огра­ничения v=mk₀ можно генерировать с помощью наборов фильтров с конечной импульсной характеристикой (КИХ-фильтров); каждый набор состоит из k₀ КИХ-фильтров над GF(q). Поэтому последовательность на выходе кодера можно рассматривать как свертку импульсной характеристики кодера с входной последовательностью. Импульсная переходная характеристика фильтра (ИПХ) (а кодер сверточного кода, по сути дела, является фильтром) есть реакция на единичное воздействие вида = (10000). Рассмотрим примеры кодирования последовательностей с использованием импульсной характеристики эквивалентного фильтра.

На рис. 7.3. показан кодер для двоичного сверточного кода с n₀=5 и k₀=1. В кодер поступает поток символов со скоростью k₀ символов в единицу времени, а из него выходит в канал поток символов со скоростью n₀ символов в единицу времени.

Такой кодер состоит из серии фильтров и выходного регулирующего буфера, который необходим для согласования выходной скорости со скоро­стью фильтров.

Каждый КИХ-фильтр может быть представлен многочленом степени не выше m. Если входной поток записать как многочлен (быть может, бесконеч­ной длины), то работа фильтра может быть описана как умножение много­членов. В этом случае кодер сверточного кода может быть представлен мно­жеством многочленов; поэтому и сам код может быть представлен посредст­вом того же множества многочленов. Иначе говоря, код является множест­вом кодовых слов, которое порождается данным множеством многочленов. Эти многочлены называются порождающими многочленами кода. Наиболь­шая степень порождающих многочленов равна m.

В отличие от блоковых кодов, которые описываются единственным по­рождающим многочленом, сверточный код требует для своего описания не­скольких порождающих многочленов - в общем случае k₀n₀ многочленов. Сверточный код состоит из бесконечного числа кодовых слов бесконечной длины. Он линеен и может быть описан бесконечной порождающей кодовой матрицей. Для описания каждого может быть использовано огромное коли­чество порождающих матриц, но удобно оперировать только некоторыми из них. Даже в лучшем случае порождающая матрица сверточного кода более громоздка, чем порождающая матрица блокового кода. Пусть (х) - множе­ство порождающих многочленов, i= 1,.... k₀, j= 1,..., n₀. Они могут быть объ­единены в матрицу размера k₀ х n₀, называемую порождающей матрицей из многочленов:

G(x)=[g_ij (x)].

При k₀, большем единицы, некоторые порождающие многочлены могут равняться нулю. Порождающая матрица сверточного кода, усеченного до блокового кода длины n, записывается в виде:

где символом 0 обозначена (к₀ х n₀) -матрица, целиком состоящая их нулей. Порождающей матрицей сверточного кода является матрица

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