5.2. Представление сверточных кодов

Известно несколько способов представления сверточных кодов: представление с помощью оператора задержки, использованное Месси [2], представление с помощью матриц, использованное Вайнером и Эшем [6], представление с помощью дерева, обычно используемое при последовательном декодировании и др. Ответить на вопрос о том, какое из этих представлений является самым удобным, нельзя, поскольку все зависит от решаемой задачи. В данном разделе будут рассмотрены представление сверточных кодов с помощью оператора задержки и представление с помощью матриц, а также будет установлена связь между ними. Представление с помощью дерева будет описано в главе, посвященной последовательному декодированию.

5.2.1. Представление с помощью операторов задержки

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

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

Удобный способ представления временных последовательностей предложен Хаффменом [31]; он основан на использовании оператора задержки При этом входных последовательностей информационных символов представляются в виде многочленов

где — информационный символ, поступивший на вход кодера в момент .

Фиг. 5.1. Сверточный кодер.

Аналогично выходных последовательностей представляются в виде многочленов

где символ, появляющийся на выходе кодера в момент и.

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

степени или меньше с коэффициентами из поля Эта связь выражается равенством

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

Пример 5.1. Рассмотрим показанный на фиг. 5.2 кодер сверточного кода со скоростью имеющий один вход и два выхода. Если входная последовательность

задана, то две выходные последовательности

определяются порождающими многочленами

следующим образом:

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

Фиг. 5.2. Кодер сверточного кода со скоростью

За это время кодер выдаст всего символов, а поэтому говорят, что кодовое ограничение этого кода составляет символов.

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

Остальные выходных последовательностей, которые можно рассматривать как проверочные последовательности, являются линейными комбинациями входных последовательностей, т. е.

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

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

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

где — шумовой символ, оказавшийся в момент и в принятой последовательности. При этом

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

будем называть синдромами. Заметим, что синдромы являются последовательностями проверочных сумм, которые могут быть вычислены при приеме. Синдромами будем также иногда называть и сами многочлены (5.10). Подставляя выражения (5.6) и (5.9) в (5.10), получаем

Если синдромы представить в виде

где проверочная сумма последовательности вычисляемая в момент и, то с учетом формулы (5.10) имеем

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

5.2.2. Представление с помощью матриц

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

Следовательно, вектор-строка из символов передаваемых последовательностей

где

и вектор-строка из символов информационных последовательностей

где

связаны между собой следующим матричным равенством

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

и имеет следующий вид:

(Обозначенные символом 0 области матрицы состоят полностью из нулей.) Матрица называется порождающей матрицей сверточного кода.

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

(здесь — соответственно единичная и нулевая матрицы размера и имеет следующий вид:

Пример 5.2. Порождающая матрица кода, рассмотренного в примере 5.1, имеет вид

В случае систематических кодов символы синдромов задаются равенством (5.13), которое можно записать в виде

Если ввести вектор-столбцы

где символ транспонирования, то равенство (5.20) можно записать в матричных обозначениях следующим образом:

где полубесконечная матрица, которая задается матрицей

и имеет следующий вид:

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

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

где матрица, получающаяся из матрицы В удалением нижних строк Заметим, что для

усеченной передаваемой последовательности имеет место равенство

так что при приеме, умножая усеченную принимаемую последовательность

на матрицу Н, можно вычислить укороченный синдром поскольку

В некоторых случаях удобнее пользоваться векторами

При этом

где полубесконечная единичная матрица,

Матрицы обычно называют проверочными треугольниками.

Пример 5.3. Двоичный систематический сверточный код со скоростью и кодовым ограничением задаваемый порождающими многочленами

имеет порождающую матрицу

В этом случае

и

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

Пример 5.4. Если код, задаваемый в интервале времени от О до 3 йроверочным треугольником

рассматривать в интервале времени от —3 до 3, то проверочная матрица будет иметь следующий вид:

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

Пример 5.5. Следуя указанному выше способу, матрицу В из примера 5.3 можно просто задать следующим образом:

Это представление особенно удобно для матриц больших размеров.