Полиноминальное представление циклических кодов.

При описании циклических кодов удобно кодовые комбинации представлять в форме полиномов степени n-1 фиктивной переменной x.

V(x)=a₀ x⁰+a₁ x¹+a₂ x²+…+a_n-1 x^n-1, где a_{i .}

Так для кодовой комбинации 1010111 может быть записан полином

V(x)=1∙ x⁰+0∙ x¹+1∙ x²+0∙ x³+1∙ x⁴+1∙ x⁵+1∙ x⁶=1+x²+x⁴+x⁵+x⁶.

Представление в виде полиномов позволяет свести действия над комбинациями к действию над полиномами. При этом при приведении подобных членов коэффициенты при равных степенях складываются по mod2.

Например, x⁴+x⁴+x⁴=x⁴; x³+x³=0; x³+x³+x³=x³ и т.д.

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

Так, если V(x) = a₀+a₁ x+a₂ x²+…+a_n-1 x^n-1, то x∙ V(x)= a₀ x+a₁ x²+a₂ x³+…+a_n-1 xⁿ, заменяем xⁿ на 1, тогда V₁(x) = a_n-1+ a₀ x+a₁ x²+a₂ x³+…+a_n-2 x^n-1.

При этом V₁(x) = V(x) ∙ x-a_n-1xⁿ+a_n-1=V(x) ∙ x-a_n-1(xⁿ-1).

Теория циклических кодов базируется на теории полей, теории полей – ветвей современной алгебры, теории конечных полей (Галуа), n-мерном представлении арифметического пространства над полем Галуа GF(2), в котором каждому кодовому вектору a₀ a₁ a₂ ….a_n-1 GF(2) однозначно сопоставляется полином

P(x)= a₀+a₁ x+a₂ x²+…+a_n-1 x^n-1 c коэффициентами из GF(2).

Если в этом пространстве выбрать некоторый полином g(x), то множество всех полиномов, которые делятся на g(x) без остатка, образуют подпространство, на котором определяется циклический код. Код V(x) является циклическим.

Таким образом, чтобы код V₁(x) был циклическим, полином V₁(x) должен делиться на g(x).

V₁(x) = V(x) ∙ x-a_n-1(xⁿ-1).

Поскольку V(x)*x из условия цикличности V(x) делится на g(x), то многочлен хⁿ-1 тоже должен делиться на g(x).