Циклические коды, основные свойства и способы построения

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

Название кодов произошло от их свойства, заключающегося в том, что каждая кодовая комбинация может быть получена путем циклической перестановки символов комбинации, принадлежащей к этому же коду. Это значит, что если, например, комбинация a₀ a₁ a₂ ...a_m-1 является разрешенной комбинацией циклического кода, то комбинация a_m-1 a₀ a₁ a₂ ...a_m-2 также принадлежит этому коду.

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

где a_i – цифры данной системы счисления (в двоичной системе 0 и 1). Так, например, двоичное семиразрядное число 1010101 может быть записано в виде полинома

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

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

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

то новая комбинация за счет циклического сдвига будет

Однако в последнем члене необходимо заменить х^m на 1. Следовательно, новая комбинация будет

Например, циклический сдвиг кодовой комбинации 1010101 может быть получен путем умножения полинома (2.17) на х

Заменив х⁷ на 1, получим полином

соответствующий кодовой комбинации 0101011.

Согласно определению циклического кода для построения производящей матрицы M_m,k достаточно выбрать только одну исходную m-разрядную комбинацию V₁(х). Циклическим сдвигом можно получить (m – 1) различных комбинаций, из которых любые k комбинаций могут быть взяты в качестве исходных. Суммируя строки производящей матрицы во всех возможных комбинациях, можно получить остальные кодовые комбинации. Можно показать, что кодовые комбинации, получаемые из некоторой комбинации V₁(х) циклическим сдвигом, удовлетворяют условиям, предъявляемым к совокупности исходных комбинаций.

Циклический сдвиг комбинации с единицей в старшем m-м разряде равносилен умножению соответствующего многочлена на х с одновременным вычитанием из результата многочлена (х^m – 1) или (х^m + 1), так как операции осуществляются по модулю два. Следовательно, если в качестве исходного взять некоторый полином Р(х), то процесс получения базовых полиномов можно представить в следующем виде:

где C₂, С₃, ..., С_m – коэффициенты, принимающие значение 1 при
Р(х) × х ⁱ ³ (х^m – 1) и значение 0 при Р(х) × х ⁱ < (х^m – 1).

При таком способе построения базовых полиномов полином Р(х) называют образующим.

Если принять условие, что полином Р(х) является делителем двучлена
(х^m + 1), то базовые комбинации, а вместе с ними и все разрешенные комбинации кода, приобретают свойство делимости на Р(х). Из этого следует, что принадлежность кодовой комбинации к группе разрешенных можно легко проверить делением ее полинома на образующий полином Р(х). Если остаток от деления равен нулю, то комбинация является разрешенной.

Это свойство циклического кода используется для обнаружения или исправления ошибок. Действительно, если под воздействием помех разрешенная кодовая комбинация трансформируется в запрещенную, то ошибка может быть обнаружена по наличию остатка при делении комбинации на образующий полином Р (х), т.е. образующий полином Р(х) должен быть делителем двучлена (х^m + 1). Выбор Р(х) однозначно определяет циклический код и его корректирующие свойства.

Циклический (m,k)-код может быть получен путем умножения простого k-значного кода, выраженного в виде полинома степени (k – 1), на некоторый образующий полином Р(х) степени (m – k).

Возможна и другая процедура получения циклического кода. Для этого кодовая комбинация простого k-значного кода G(х) умножается на одночлен х^m-k, а затем делится на образующий полином Р(х) степени (m – k). В результате умножения G(х) на х^m-k степень каждого одночлена, входящего в G(х), повысится на (m – k). При делении произведения х^m-kG(х) на образующий полином Р(х) получится частное Q(х) такой же степени, как и G(х).

Результат умножения и деления можно представить в следующем виде:

х^m-kG(х) / Р(х) = Q(х) + R(x) / P(х), (2.19)

где R(х) – остаток от деления х^m-kG(х) на Р(х).

Так как частное Q(х) имеет такую же степень, как и кодовая комбинация G(х), то Q(х) также является комбинацией простого k-значного кода.

Умножая обе части равенства (2.19) на Р(х) и произведя перестановки, получим

F(х) = Q(х) Р(х) = х^m-kG(х) + R(х). (2.20)

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

Таким образом, кодовая комбинация циклического (m,k)-кода может быть получена двумя способами:

1) путем умножения простой кодовой комбинации степени (k – 1) на одночлен х^m-k и добавления к этому произведению остатка, полученного от деления полученного произведения на образующий полином Р(х) степени
(m – k);

2) путем умножения простой кодовой комбинации степени (k – 1) на образующий полином Р(х) степени (m – k).

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

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

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