Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

2.1. Классы вычетов многочленов

Каждому двоичному набору длины n можно поставить в соответствие многочлен степени меньше n с коэффициентами из простого поля Галуа GF(2) = {0,1}. Мы договоримся, что коэффициенты многочлена записываются как двоичный набор, начиная со старших разрядов, т. е. самый левый разряд двоичного набора соответствует коэффициенту при xn-1, а самый правый разряд - свободному члену многочлена. Например, при описании многочленов степени не больше 4 многочлену x3 + x + 1 соответствует двоичный набор 01011 длины 5. Таким образом, между многочленами степени меньше n (с коэффициентами 0 и 1) и двоичными наборами длины n можно установить взаимно однозначное соответствие.

Наборы длины n будут рассматриваться как представители классов вычетов многочленов по модулю многочлена f(x) степени n. Напомним, что класс вычетов по модулю многочлена f(x) содержит все многочлены с коэффициентами из поля {0, 1}, которые имеют один и тот же остаток при делении на многочлен f(x). В алгебре показывается, что каждый класс вычетов по модулю многочлена f(x) обязательно содержит многочлен степени меньше n, который обычно и выбирается представителем класса, а вектор коэффициентов такого многочлена выбирается для обозначения класса. На классах вычетов вводятся операции умножения и сложения. Результатом операции является класс, которому принадлежит результат операции над представителями классов.

Таким образом, каждому двоичному набору (rn-1, rn-2, ... , r0) длины n соответствует многочлен r(x) = rn-1xn-1+rn-2xn-2+...+r0, представляющий множество всех многочленов с коэффициентами из поля {0, 1} (класс вычетов), остаток от деления которых на многочлен f(x) равен r(x). Этот класс, который мы будем обозначать [r(x)], и соответствующий вектор (rn-1, rn-2, ..., r0) из n компонент будем рассматривать просто как различные способы представления соответствующего класса вычетов по модулю многочлена f(x).

Еще раз отметим, что при рассмотрении циклических кодов все действия над наборами длины n из скаляров поля Галуа выполняются как над многочленами с соответствующими коэффициентами. Результатом операции является вектор коэффициентов полученного многочлена.


Пример: Рассмотрим многочлен f(x) = x3+1 и построим классы вычетов по модулю этого многочлена. Число различных многочленов степени меньше 3 с коэффициентами 0 и 1 равно 8, и каждый из них определяет свой класс вычетов. Таким образом, получим следующие классы вычетов [0] (000), [1] (001), [x] (010),  [x+1] (011), [x2] (100), [x2+1] (101), [x2+x] (110), [x2+x+1] (111).

При сложении двух классов вычетов соответствующие булевы векторы складываются (по модулю 2). Таким образом, [x2] + [x2+1] соответствует сложению векторов 100 и 101, т. е. [x2] + [x2+1] = [1].

Умножение классов вычетов осуществляется на основе соответствующих многочленов и нахождении остатка от деления на многочлен f(x); в нашем примере f(x) = x3+1. Поэтому [x2] × [x2+1] = [x4+x2]. После деления многочлена x4+x2 на многочлен x3+1 получается остаток x2+x, т. е. [x2] × [x2+1] = [x2+x] или (100) × (101) = 110.

Таким образом, мы получаем следующую таблицу умножения классов.


000

001

010

011

100

101

110

111

000

000

000

000

000

000

000

000

000

001

000

001

010

011

100

101

110

111

010

000

010

010

110

001

011

101

111

011

000

011

110

101

101

110

011

000

100

000

100

001

101

010

110

011

111

101

000

101

011

110

110

011

101

000

110

000

110

101

011

011

101

110

000

111

000

111

111

000

111

000

000

111


Покажем, что для классов вычетов по модулю многочлена f(x) = xn+1 циклический сдвиг вектора коэффициентов соответствует умножению соответствующего класса на класс [x].

Теорема 2.1. Пусть [r(x)], где r(x) = rn-1xn-1+rn-2xn-2+...+r0, - класс вычетов по модулю многочлена f(x) = xn+1. Тогда [xr(x)] = [rn-2xn-1+...+r0 x+rn-1].

Действительно, xr(x) = rn-1xn+rn-2xn-1+...+r0x . Так  как [xn+1] = [0], то [xn] = [1], и, следовательно, [xr(x)] = [rn-1+rn-2xn-1+...+r0 x].