12.2. ОПИСАНИЕ СВЕРТОЧНЫХ КОДОВ С ПОМОЩЬЮ МНОГОЧЛЕНОВ

Сверточный -код над с длиной кодового ограничения можно генерировать с помощью наборов фильтров с конечным импульсным откликом (КИО-фильтров); каждый набор состоит из КИО-фильтров над В кодер поступает поток символов со скоростью к символов в единицу времени, а из него выходит в канал поток символов со скоростью символов в единицу времени. На рис. 12.7 показан кодер для двоичного сиерточного кода с Такой кодер состоит из серии фильтров и выходного регулирующего буфера, который необходим для согласования выходной скорости со скоростью фильтров. На рис. 12.8 приведен аналогичный кодер для двоичного сверточного кода с Для согласования входной скорости со скоростью фильтров добавлен входной буфер.

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

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

(кликните для просмотра скана)

быть объединены в матрицу размера называемую порождающей матрицей из многочленов:

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

Например, порождающие матрицы из многочленов кодеров на рис. 12.3 записываются в виде

и

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

Определение 12.2.1. Длиной кодового ограничения сверточного кода, задаваемого порождающей матрицей из многочленов называется величина

Информационной длиной кодового слова называется

кодовой длиной блока называется

Например, у сверточных кодов, кодеры которых показаны на рис. соответственно.

Будем рассматривать входной кадр как параллельно поступающих символов, а последовательность входных кадров как параллельных последовательностей символов. Они могут быть

Рис. 12.9. Кодеры для двух сверточных кодов со скоростью 2/3.

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

Аналогично выходное кодовое слово может быть представлено многочленами кодового слова или вектором этих многочленов

Коэффициенты многочленов кодового слова перемежаются в порядке их прохождения но каналу.

Теперь операцию кодирования можно компактно описать с помощью векторно-матричного произведения

или, что то же самое,

Проверочная матрица из многочленов является -матрицей, элементами которой являются многочлены и которая удовлетворяет условию

Вектор синдромных многочленов дается уравнением

Он является -мерным вектором-строкой из многочленов.

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

где — единичная матрица размера а матрица многочленов размера Для систематических

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

где I — единичная матрица размера Можно непосредственно проверить, что

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

Так как в кодовых словах, не принадлежащих систематическому коду, информация непосредственно не содержится, они должны строиться так, чтобы при отсутствии ошибок ее можно было бы легко восстановить. Упомянутое выше сужение понятия эквивалентности состоит в том, что все кодеры должны конструироваться на базе КИО-фильтров без обратной связи. Если же использовать обратную связь в цепях, выполняющих деление многочленов, то можно построить систематический кодер для любого сверточного кода. На рис. 12.10 дается систематический кодер с обратной связью, соответствующий решетке, изображенной на рис. 12.5.

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

и

Рис. 12.10. Систематический кодер с обратной связью для сверточного

Для систематического кода

Определение 12.2.2. Сверточный код, порождающие многочлены которого удовлетворяют условию

при некотором а, называется некатастрофическим сверточным кодом. В противном случае он называется катастрофическим сверточным кодом.

Без ограничения общности мы можем считать так как невыполнение этого равенства просто эквивалентно введению во все фильтры задержки, что, очевидно, бессмысленно.

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

Поэтому если многочлен поступающих данных кодируется по формуле

то можно восстановить, используя соотношение

что легко проверить подстановкой.

На рис. 12.11 приведен пример. Многочлен поступающих данных вводится слева, а выводится в неизменном виде справа. Комбинированная посимвольная скорость в точках равна удвоенной входной скорости, однако можно так скомбинировать символы, проходящие эти две точки, чтобы они образовывали передаваемое по каналу кодовое слово сверточного кода со скоростью 1/2. Вводимая избыточность используется для нахождения и исправления ошибок; чем больше ошибок, которые могут быть неправлены, тем лучше код.

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

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

Рис. 12.11. Подробная схема регистра сдвига.

Определение 12.2.3. Сверточный код с матрицей порождающих многочленов определители подматриц которой удовлетворяют условию

при некотором а, называется некатастрофическим сверточным кодом. В противном случае он называется катастрофическим сверточным кодом.

Как и в предыдущем случае, некатастрофический код может быть обращен. Иначе говоря, существует -матрица многочленов такая, что

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