21

Применение циклических кодов в каналах с независимыми ошибками

1. Кодирование при помощи порождающего полинома g(X)

1.1. Общие принципы кодирования

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

(1.1)

где c_j – коэффициенты полинома избыточной части ; u_i – коэффициенты исходного полинома информационной части

Полином информационной части u(x) сдвинут в сторону старших разрядов на k символов, что эквивалентно умножению информационного полинома на x^k. Представим полином циклического кода в виде

(1.2)

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

(1.3)

где g(x) – порождающий полином; q(x) – частное от деления полинома u(x)x^k на порождающий полином g(x); r(x) – остаток от деления полинома u(x)x^k на порождающий полином g(x).

Таким образом, для определения избыточной части r(x) полинома циклического систематического кода V(x) необходимо определить остаток от деления полинома u(x)x^k на порождающий полином g(x). Указанный способ достаточно прост и эффективно алгоритмизируется, поэтому нашел наибольшее применение на практике.

Пример 1.1. Для циклического кода (7,4,3), заданного порождающим полиномом g(x) = 1  x²  x³, и информационного полинома u(x) = 1 рассчитать избыточные символы.

Определим остаток от деления полинома u(x)x^k = 1x³ = x³ на порождающий полином g(x) = 1  x²  x³.

Рассчитанную избыточную часть представим в виде полинома r(x) = 1x². Полином V(x) может быть представлен в виде V(x) = 1x²x³. Вектор V может быть представлен в виде V = (1011000).

Кодирование при помощи порождающего полинома g(x) для кодов с четным минимальным кодовым расстоянием проводится по указанному алгоритму, за исключением одного нюанса. Он связан с видом порождающего полинома, который, как известно, получается путем умножения порождающего полинома g(x) кода с нечетным минимальным кодовым расстоянием на полином (1x). Все остальные вычисления с применением полученного порождающего полинома проводятся аналогично.

Пример 1.2. Для циклического кода (7,3,4), заданного порождающим полиномом g(x) = 1  x²  x³, и информационного полинома u(x) = 1 рассчитать избыточные символы.

Построим порождающий полином для заданного кода

g(x) = (1  x²  x³)·(1  x) = 1 x²  x³  x  x³  x⁴ = 1  x  x²  x⁴.

Определим остаток от деления полинома u(x)x^k = 1x⁴ = x⁴ на порождающий полином g(x) = 1  x  x²  x⁴:

Рассчитанную избыточную часть представим в виде полинома r(x) = = 1  x  x². Полином V(x) может быть представлен как V(x) = 1  x  x²   x⁴. Вектор V может быть представлен в виде V = (1110100).

Кодирование при помощи порождающего полинома g(x) для укороченных циклических кодов не имеет принципиальных отличий. Это объясняется тем, что количество избыточных символов для неукороченного и полученного от него укороченного циклического кода, как известно, совпадает. Укорочению подвергается информационная часть, что не влияет на алгоритм кодирования.