Порождающий многочлен циклического кода

Полиномиальный код является циклическим тогда и только тогда, когда полином g(x) является делителем многочлена хⁿ-1. В этом случае многочлен g(x) называется порождающим многочленом циклического кода.

Многочлен хⁿ-1 можно разложить на множители

xⁿ-1=(х-1) ∙ (х^n-1+х^n-2+…+1),

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

Число циклических n-разрядных кодов равно числу делителей многочлена xⁿ-1. Для построения циклических кодов разработана таблица разложения многочленов xⁿ-1 на неприводимые многочлены, т.е. такие, которые делятся только на единицу и на самого себя. Неприводимые многочлены дают наибольшее число остатков при делении. Это свойство используется для обнаружения ошибки при депозировании.

Рассмотрим, например, какие коды можно построить на основе многочлена х⁷+1 над полем GF(2).

x⁷+1=(х+1)(х³+х²+1)(х³+х+1).

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

Код (n, k) определяется значениями n и k, где k=n- , а – степень многочлена g(x) – делителя х⁴-1, определяющего код.

g₁(x)=x+1, =1, k=6, код (7, 6)(1 разряд проверочный на четность)

g₂(x)=x³+x²+1, =3, k=4, код (7, 4)

g₃(x)=x³+x+1, =3, k=4, код (7, 4)

g₄(x)=(x+1)(x³+x²+1), =4, k=3, код (7, 3)

g₅(x)=(x+1)(x³+x+1), =4, k=3, код (7, 3)

g₆(x)=(x³+x²+1)(x³+x+1), =6, k=1, код (7, 1)

При осуществлении операции циклической перестановки мы принимаем хⁿ-1. Учитывая, что кодовые комбинации складываются по mod2, то хⁿ+1=0 и хⁿ-1=0, т.е. х 1=0 или хⁿ+1=хⁿ-1. С другой стороны, с учетом того, что порождающий полином делит полином хⁿ-1, получим

x⁴+1=g(x) ∙ h(x), и, соответственно

g(x) ∙ h(x)=0.

Полином h(x) называется проверочным полиномом. Произведение проверочного и порождающего полиномов равно h(x) ∙ g(x)=0. Это соотношение положено в основу декодирования циклических кодов.