Циклические коды

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

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

Запишем, например, образующую (производящую) матрицу G, получающуюся при циклическом сдвиге комбинации 0 0 1 0 1 1:

(2.26)

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

При описании циклических кодов n-разрядные кодовые комбинации представляются в виде многочленов фиктивной переменной x, в которых коэффициентами при переменной x являются цифры 0 и 1, составляющие КВ. Например, КВ в виде многочлена представляется так:

Члены с нулевыми коэффициентами при записи опускаются, т.е. имеет вид:

В общем случае, если число элементов КВ равно n, соответствующий ему многочлен имеет вид:

, (2.27)

где , ,…, – – коэффициенты, принимающие значения 0 и 1.

Наибольшая степень x в слагаемом с ненулевым коэффициентом называется степенью многочлена.

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

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

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

Операция символического умножения задается так:

- многочлены перемножаются по обычным правилам, но с приведением подобных членов по модулю 2;

- если старшая степень произведения не превышает , то оно и является результатом символического умножения;

- если старшая степень произведения больше или равна n, то многочлен произведения делится на многочлен (сам остаток в этом случае называется вычетом).

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

Циклический сдвиг КВ с нулем в старшем разряде (слева) равносилен умножению многочлена, отображающего этот КВ, на x.

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

Пусть исходным является вектор матрицы (2.26). Тогда, согласно сформулированному правилу,

(знак перед 1 заменен с «–» на «+» потому, что «–» здесь не имеет смысла). .

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

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

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

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