Полиномиальные коды
Представление кодового слова (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 коэффициентов при одинаковых степенях х.
|
Х3 + Х2 + Х+ 0 = Х3 + Х2 + X , (1.53) |
Например:
|
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) |
С(х) = 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 совпадают.