Полиномиальные коды

Представление кодового слова (n,k)-кода в виде последовательности U = (U0, U1, ..., Un-1) длиной n символов или их задание с помощью системы проверочных уравнений и порождающей матрицы не является единственно возможным. Еще один удобный и широко используемый способ представления того же кодового слова состоит в том, что элементы U0, U1, ..., Un-1 являются коэффициентами многочлена от X, то есть

U(х) = f(х) = U0 +U1× Х + U2×Х2

+...+Un- 1×Хn-1 . (1.51)

Используя это представление, можно определить полиномиальный код как множество всех многочленов степени, не большей n -1, содержащих в качестве общего множителя некоторый фиксированный многочлен g(x).

Многочлен g(x)

называется порождающим многочленом кода.

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

Определим действия над полиномами в поле двоичных символов GF(2).

Суммой двух полиномов f(x)

и g(x) из GF(2) называется полином из GF(2),

определяемый следующим образом:

f(x) + g(x) =

. (1.52)

Другими словами, сложению двоичных полиномов соответствует сложение по mod2 коэффициентов при одинаковых степенях х.

+ X3+X2+0×X+1

X+1

Х3 + Х2 + Х+ 0 = Х3 + Х2 + X , (1.53)

Например:

X3 + X2 + 0×X + 1

X2 + X + 1

X3 + 0 + X + 0 = X3 + X. (1.54)

Произведением двух полиномов из GF(2) называется полином из GF(2), определяемый следующим образом :

f(x)× g(x)=

, (1.55)

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

     X3 + X2 + 0 + 1

                    X + 1

    X3 +   X2   + 0 + 1

                        X4 + X3 + 0   + X

                X4 + 0 +   X2 + X + 1 = X4 + X2

+ X +1 ,           (1.56)

Например:

X 3 + X2 + 0 + 1

                                  X2 + X

                X4 + X3 + 0 +   X

       X5 + X 4 + 0    + X2

       X5 + 0   + X3 + X2 + X = X5 + X3 + X2 + X .               (1.57)

Наконец, можно сформулировать теорему о делении полиномов: для каждой пары полиномов С(х) и d(x), d(x) ¹ 0 существует единственная пара полиномов q(x) — частное и r(х) — остаток, такие, что

С(х) = q(x)× d(x) + r(х) , (1.58)

где степень остатка r(х)

меньше степени делителя d(x).

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

         X3 + X2 + X+ 1

         X3 + X2

                        X + 1

                        X + 1

         0 ¬¾ остаток r(x).                  (1.59

Например:

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

Содержание раздела