Полиномы кодовых слов циклического кода делятся без остатка на свой порождающий полином g(x)

Выбор g(x) для построения циклического кода длины n.

Любой полином, который является делителем полинома (xⁿ+1) можно использовать в качестве порождающего. С ростом n число возможных циклических кодов растет. На практике при построении циклических кодов пользуются таблицами разложения полиномов (xⁿ+1) на неприводимые полиномы. Любой неприводимый полином, входящий в разложение, или произведение нескольких неприводимых полиномов можно выбрать в качестве порождающего полинома, который дает соответствующий циклический код.

Пример.

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

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

Можно построить следующие ЦК:

1. (7,6) с g(x)=x+1

2. (7,1) с g(x)= (x³+x²+1)(x³+x+1)=x⁶+x⁴+x³+x⁵+x³+x²+x³+x+1=

=x⁶+x⁵+x⁴+x³+x²+x+1

3. (7,4) c g(x)= x³+x²+1

4. (7,4) c g(x)= x³+x+1

5. (7,3) c g(x)= (x+1)(x³+x²+1)=x⁴+x³+x+x³+x²+1=x⁴+x²+x+1

6. (7,3) c g(x)= (x+1)(x³+x+1)=x⁴+x²+x+x³+x+1=x⁴+ x³+x²+1

Процедура кодирования циклическим кодом

Процедура кодирования записывается следующим образом:

V(x)=U(x)*x^n-k+R(x)

R(x)= U(x)*x^n-k mod g(x)

В этом случае первые k разрядов кодового слова являются информационными, а последние r=n-k - проверочными.

Пример

Закодировать информационную последовательность U=0110 циклическим кодом (7,4) с порождающим полиномом g(x)= x³+x+1.

U(x)= x²+x, r=n-k=3, U(x)*x³= x⁵+x⁴

R(x)=(x⁵+x⁴) mod (x³+x+1)

R(x)=1

V=0110001 ® V(x)= x⁵+x⁴+1

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

Деление можно выполнять в двоичном виде.

U(x)*x³= x⁵+x⁴ ® 0110000

g(x) ® 1011

R=001®V=0110001