1) Процедуры на основе g(X).

Кодовая комбинация циклического кода f(x):

а) Процедура кодирования.

Есть комбинация k(x), а хотим сделать f(x). Для этого размещаем комбинацию k(x) на месте информационных элементов, а потом находим избыточные элементы. Таким образом получаем f(x).

k(x)= x⁰ … x ^k-1 , а нам надо

k(x)= x ^{n – k} … x ^{n -1}

Для этого k(x)*x ^{n - k} -первый шаг кодирования.

Таким образом, разместили k(x). Теперь находим избыточные элементы.

Любая кодовая комбинация циклического кода должна делиться на порождающий многочлен:

(k(x) * x ^{n - k} ) / g(x)= q(x) (частное от деления) + r (x) / g(x) (остаток от деления) -второй шаг кодирования.

k(x) * x ^{n - k} = q(x) * g(x) + r (x)

r (x) + k(x) * x ^{n - k} = q(x) * g(x) -третий шаг кодирования.

В качестве избыточных элементов берётся остаток от деления r (x).

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

f (x) =k(x) / g(x) по mod (x ⁿ +1)

В этом случае получаем неразделимый код.

б) Процедура декодирования.

В основе процедуры декодирования лежит вычисление синдрома S(x). Есть 3 способа вычисления синдрома:

1. S (x) = f (x) * H^T

2. S (x) = остаток от деления f (x) на g(x)

3. S (x) = f (x= a ⁱ), где a ⁱ -корни g(x)

Если код используется в режиме обнаружения ошибок, то синдром даёт основание решать: есть ошибки в принятой комбинации или нет.

Если S(x) = 0, то ошибок нет или они не обнаруживаются кодом

Если S(x) 0, то в принятой комбинации есть ошибки.

При исправлении ошибок поступают также как и в групповых кодах. По S(x) находят e(x) и тогда:

f '(x)+e(x) = f(x), где f '(x) -принятая комбинация.

хх^n-k-1 х ^n-k х ^n-1

Избыток

Информация

n-k k

1.Кодирование

g(х)

2.Декодирование. Вычисление синдрома.

1.

2. =остаток от деления

3. для всех корней g(x)

Пример

Рассмотреть процедуру кодирования и декодирования для кода БЧХ (7,4) с g(x)=1+х+х³

Числа, соответствующие кодовой комбинации:

Элемент кодовой комбина ции	Частное от деления	r(x)	Двоичная посл-ть остатка
хº	q(x)g(x)=0*g(x)	xº=1		100
х¹	0*g(x)	x α¹		010
х²	0*g(x)	x²α²		001
х³	1*g(x)	1+x		110
х^4	x*g(x)	x+x² α^4		011
х^5	(x²+1)g(x)	1+x+x²		111
х^6	(x³+x+1)g(x)	1+x²		101

^{случайно элементы поля GF(2³)}

каноническая форма порождающей матрицы G(7,4)

Декодирование:

1.Сумма строк H^T соответствующих f(x)

2.Сумма строк H^T соответствующих f(x)

3. Сумма строк H^T соответствующих f(x)

Теорема:

Справедливо рав-во (a+b)^p=a ^p+b ^p,если GF(p ^m ) (a+b+c)^p=a ^p+b ^p +c ^p