Лекции по теории информации. Фурсов В.А. - 103 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

103
Операция умножения реализуется в следующей последовательности. Мно-
гочлены перемножаются как обычно с последующим приведением коэффици-
ентов по модулю 2. Если в результате умножения получается многочлен степе-
ни
n
и выше, то осуществляется его деление на заданный многочлен степени
n
, а результатом умножения считают остаток от деления. Ясно, что старшая
степень этого остатка не будет превышать величины
1
n
, а полученный оста-
ток будет соответствовать некоторой
n
-разрядной кодовой комбинации, т.е.
обеспечивается замкнутость.
Для реализации циклического сдвига с использованием описанной опера-
ции умножения необходимо после умножения на
x
выполнить деление на дву-
член
1
n
. Эта операция называется взятием остатка или приведением по
модулю
1
n
, а сам остаток называют вычетом:
1 2 1 2
1 2
( ... 1) ...
1
1
1
0 ... 1
n n n n
n
n
n
x x x x x x x x
x
x
x x x
.
Нетрудно заметить, что в данном случае остаток (вычет) формируется путем
сложения по модулю 2 двучлена
1
n
с результатом умножения на
x
.
12.3 Построение циклического кода на кольце многочленов
Выделим в кольце подмножество всех многочленов, кратных некоторому
многочлену
g x
. Ясно, что это подмножество будет идеалом, а многочлен
g x
– порождающим или образующим многочленом идеала. Если
0
g x
, то
весь идеал состоит из одного этого многочлена. Если
1
g x
, то в идеал вой-
дут все многочлены кольца.
В кольце 2
n
всех возможных многочленов степени n-1 над полем GF(2) не-
приводимый многочлен
g x
степени
m n k
порождает
2
k
элементов идеа-
ла. Следовательно, можно определить циклический двоичный код как идеал,
каждому многочлену которого ставится в соответствие
n
-разрядная разрешен-

Страницы