Представление кодовых комбинаций в полиномиальном виде

При изложении теории циклических кодов любая кодовая комбинация A=((a_n-1, a_n-2,…,a₀),a_i=0,1) отождествляется с многочленом F(x) степени <= (n-1), определяемым следующим образом:

F(x)= a_n-1 x ^n-1 +a_n-2 x^n-2 +…+ a₁x+ a₀

Например, последовательность 10110 в полиномиальном виде запишется следующим образом:

F(x)= 1 x ⁴ +0 x³ +1 x²+ 1x+ 0=x ⁴ + x²+x

Запись кодовой комбинации в виде многочлена не всегда определяет длину кодовой комбинации. Например, при n=5 многочлену x²+1 соответствует кодовая комбинация 00101, поэтому при переходе к записи в виде кодовой комбинации необходимо дописывать нулевые старшие разряды.

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

Для двоичных кодов действия над кодовыми комбинациями производятся в поле Галуа GF(2). Таблицы сложения и умножения для поля GF(2) приведены ниже:

+	0 1
	0 1
	1 0

х	0 1
	0 0
	0 1

Рассмотрим примеры арифметических действий над кодовыми комбинациями F₁(x) и F₂(x)

F₁(x)= x ³ + x+1-> 1011

F₂(x)= x ² + x+1-> 0111

F₁(x)+ F₂(x)= x ³ + x²+(1+1)x+(1+1)= x ³ + x² -> 1100

F₁(x)x F₂(x)=(x ³ + x+1)x(x ² + x+1)= x ⁵ +x ⁴ + x³+ x³+ x ² + x+ x ² + x+1= x ⁵ +x ⁴+1 -> 110001

x ³ + x+1 | x+1____

x ³ + x² | x ² + x

------------

x ² + x+1

x ² + x

-------------

1 – остаток

Эти же операции можно проделать с двоичными числами.

Для обеспечения свойства замкнутости умножение полиномов производится по модулю P_r(x). Это означает, что в качестве результата умножения принимается остаток от деления обычного произведения полиномов на полином P_r(x).

Умножение по модулю m сводится к тому, что обычное произведение этих чисел делится на m и записывается остаток. Например, 2х4=3 (мод.5), т.е. 2х4=8, 8:5 имеет в остатке 3. Это число и является результатом умножения по модулю 5.

Указанная операция над многочленами не приводит к появлению полинома с большей степенью, чем заданная длина кода.

Рассмотрим код с n=5. Возьмем P₁(x)= x ⁴ + x+1 и P₂(x)= x ⁴ . Произведем обычное умножение полиномов:

P₃(x)= P₁(x) P₂(x)= (x ⁴ + x+1) x ⁴ = x ⁸ + x⁵+x⁴

Полином P₃(x), имея степень n=8, не принадлежит коду с n=5.

Рассмотрим умножение по модулю P_r(x).При этом полином P_r(x) должен иметь степень r<n. Выберем P_r(x)= x ³ + x²+1. Находим

P₁(x) P₂(x) [mod P_r(x)]= P₁(x) P₂(x)/ P_r(x), т.е. x ⁸ + x⁵+x⁴/ (x ³ + x²+1)= x⁵+x⁴+ x ³ + x²+x

R(x)= x²+x

Полученный остаток R(x) и является результатом произведения полиномов P₁(x), P₂(x) по модулю P_r(x). Он именуется вычетом по многочлену P_r(x).