Построение циклических кодов

Циклические коды являются частным случаем групповых кодов и однозначно задаются с помощью порождающего (образующего) полинома

g(x)=g_kx^k+g_k-1x^k-1+…+g₁x+g₀.

Особенности порождающего полинома:

- порождающий полином g(x) имеет наименьшую степень среди многочленов данного идеала (хⁿ+1);

- свободный член g⁰ всегда не равен нулю;

- любой многочлен циклической группы делится на g(x) без остатка;

- g(x) является делителем для двучлена (хⁿ+1).

Так как любое кодовое слово b(х) должно делиться на g(x) , то

b(х)=n(х)g(х). (4.1)

Соотношение (4.1) описывает процесс кодирования слова. n=(n_m-1,n_m-2,…,n₀) - вектор первичного (безызбыточного) кода длиной m разрядов, записанный в виде полинома

.

В результате применения соотношения (4.1) можно построить неразделимый циклический код, для которого образующая матрица имеет следующий вид:

.

Желательно циклический код представлять в виде разделимого кода, т.е. в кодовой комбинации b(х)=b_n-1x^n-1+b_n-2x^n-2+…+b₁x+b₀, коэффициенты кодового полинома при x^n-1, x^n-2,…,x^k - информационные символы, а при x^k-1,x^k-2, …,x,1 - контрольные символы.

Для получения разделимого циклического кода достаточно вычислить остатки от деления произведения x^kn_i(х), (i-0,1,…m-1) на порождающий полином g(x).

Если выбрать в качестве базисных кодовых полиномов xⁱx^k+R_i(х), то получим для разделимого кода порождающую матрицу в канонической форме G_m,n=|I_mR_m,k|. Причем,

. (4.2)

Пример. Полином g(х)=х³+х²+1 порождает циклический код (7,4). Информационные элементы кодовых комбинаций, используемые в качестве строк образующей матрицы, имеют следующую запись: n_i(х)=х⁰, n_i(х)=х¹, n_i(х)=х², n_i(х)=х³.

Тогда, R₀(х)=Rem[x^kx⁰/g(x)]=Rem[x³/(х³+х²+1)]=х²+1, R₁(х)=Rem[x⁴/(х³+х²+1)]=х²+x+1, R₂(х)=Rem[x⁵/(х³+х²+1)]=x+1, R₆(х)=Rem[x⁶/(х³+х²+1)]=x²+x.

Образующая матрица будет иметь вид

.