Файл: Кодирования.pdf

5.1. Операции с полиномами
5.1.1. Сумма полиномов
При суммировании полиномов складываются коэффициенты одночле- нов одноименной степени.
f
(x) = a
0
+ a
1
x
+ a
2
x
2
+ . . . + a n
x n
,
g
(x) = b
0
+ b
1
x
+ b
2
x
2
+ . . . + b m
x m
,
m
> n,
h
(x) = f (x) + g(x) = (a
0
+ b
0
) + (a
1
+ b
1
)x + (a
2
+ b
2
)x
2
+ . . . +
+(a n
+ b n
)x n
+ . . . + (a m
+ b m
)x m
При рассмотрении полиномов с коэффициентами 0 и 1, принадлежащи- ми простому полю GF(2) необходимо учитывать, что сложение в этом случае производится по модулю 2. Таким образом, при сложении двух одночленов одной степени с коэффициентом 1, результирующий одночлен будет иметь коэффициент 0:
(1 + x + x
2
+ x
4
) + (x + x
3
+ x
4
+ x
5
) = 1 + x
2
+ x
3
+ x
5
То есть, происходит сокращение пар одночленов одинаковой степени.
5.1.2. Произведение полиномов
Умножение полиномов выполняется по следующему принципу f
(x) = a
0
+ a
1
x
+ a
2
x
2
+ . . . + a n
x n
,
g
(x) = b
0
+ b
1
x
+ b
2
x
2
+ . . . + b m
x m
,
h
(x) = f (x)g(x) = f (x)b
0
+ f (x)b
1
x
+ f (x)b
2
x
2
+ . . . + f (x)b m
x m
=
= (b
0
a
0
+ b
0
a
1
x
+ . . . + b
0
a n
x n
) + (b
1
a
0
x
+ b
1
a
1
x
2
+ . . . + b
1
a n
x n
+1
) + . . . +
+(b m
a
0
x m
+ b m
a
1
x
1+m
+ . . . + b m
a n
x n
+m
).
Далее полученные полиномы складываются по обычному правилу. Та- ким образом, в результате произведения полинома степени n на полином сте- пени m получается полином степени n + m.
Умножение полиномов с коэффициентами из простого поля GF(2) про- изводится аналогично с учетом того, что операция сложения осуществляется по модулю 2:
(1 + x
2
+ x
3
)(x + x
2
) = x + x
2
+ x
3
+ x
4
+ x
4
+ x
5
= x + x
2
+ x
3
+ x
5 5.1.3. Деление полиномов
Для деления полиномов удобно использовать процедуру деления в столбик:
34

−
4x
3
+10x
2
+6x+1 2x
2
+4x+1 4x
3
+ 8x
2
+ 2x
2x+1 2x
2
+ 4x+1 0
Таким образом
4x
3
+ 10x
2
+ 6x + 1 2x
2
+ 4x + 1
= 2x + 1.
Аналогично производится деление полиномов с коэффициентами из простого поля GF(2). Вместо операции вычитания используется сложение по модулю 2:
⊕
x
5
+x
4
+x
3
+x+1 x
2
+ 1
x
5
+x
3
x
3
+x
2
+1
⊕
x
4
+ x +1
x
4
+x
2
⊕
x
2
+x+1
x
2
+1
x
Таким образом x
5
+ x
4
+ x
3
+ x + 1
x
2
+ 1
= (x
3
+ x
2
+ 1) +
x x
2
+ 1
Контрольные вопросы

1. Что такое полином? Какие способы записи полиномов существуют?
2. Как умножаются полиномы?

3. Как осуществляется деление полиномов?
35

6. ПОНЯТИЕ ГРУППЫ, КОЛЬЦА И ПОЛЯ
6.1. Группа
Группой называется множество элементов, для которых определена не- которая операция «•» (сложение или умножение) и выполняется ряд приве- денных ниже аксиом G.1–G.4 [
4
,
13
].
Аксиома G.1. Операция «•» может быть применена к любым двум эле- ментам группы, в результате чего получается третий элемент группы.
Если a
∈ G и b ∈ G,
то a
• b ∈ G.
Аксиома G.1 определяет замкнутость операции в группе. Как прави- ло операции над элементами называют сложением («+») или умножением
(«·»; «×»), даже если они не являются обычными сложением и умножением.
В соответствии с двумя записями операций различают аддитивную и муль- типликативную группы [
4
,
13
].
Аксиома G.2.
Свойство ассоциативности. Для любых трех элементов a
, b и c из группы G верно a
• (b • c) = (a • b) • c.
То есть порядок выполнения операций несущественен.
Аксиома G.3. В группе G всегда существует единичный элемент e, та- кой, что a
• e = e • a = a для любого a ∈ G.
Для аддитивной группы единичный элемент называют нулем, обозначают 0 и определяют из уравнения a
+ 0 = 0 + a = a.
Для мультипликативной группы единичный элемент называют единицей и определяют из уравнения a
· 1 = 1 · a = a.
Аксиома G.4. Для любого элемента a ∈ G существует обратный эле- мент a
−1
такой, что a
• a
−1
= a
−1
• a = e.
Для аддитивной группы обратный к a элемент обозначается −a и находится из уравнения a
+ (−a) = (−a) + a = 0.
36

Для мультипликативной группы обратный к a элемент обозначается a
−1
и находится из уравнения a
· a
−1
= a
−1
· a = 1.
Кроме того, для любого элемента a ∈ G и любого целого положительного n
(a n
)
−1
= (a
−1
)
n
Можно ввести степени элемента a c целыми отрицательными показателями так что a
−n
= (a n
)
−1
[
14
,
15
]. Также можно обозначить a
0
= e.
Все обычные правила действий со степенями остаются справедливыми в лю- бой группе [
14
,
15
].
Рассмотрим все возможные степени произвольного элемента g группы
G
. . . , g
−2
, g
−1
, g
0
= e, g
1
= g, g
2
, . . . .
Если все эти степени различны, то элемент g называется элементом беско- нечного порядка; иначе он называется элементом конечного порядка.
Для любого элемента конечного порядка существуют такие числа N,
что g
N
= e. Наименьшее из этих чисел называется порядком n элемента g [
14
,
15
].
Также верно утверждение, что для любого элемента g порядка n равен- ство g m
= e имеет место тогда и только тогда, когда m делится на n [
14
,
15
].
В группе G порядок 1 имеет только единичный элемент e [
14
,
15
].
Соответственно, выделяют конечные группы, состоящие из конечного числа элементов, и бесконечные. Количество элементов в конечной группе,
называется ее порядком [
14
].
Аксиома G.5.
Аксиома коммутативности. Для двух произвольных элементов a и b из G справедливо[
13
,
14
,
15
]
a
• b = b • a.
Если кроме аксиом G.1–G.4 выполняется аксиома коммутативности
G.5, то группа называется коммутативной или абелевой [
4
,
13
,
14
].
В качестве примера аддитивной группы можно привести совокупность действительных чисел. Единичным элементом при этом является ноль. Мно- жество всех действительных чисел без нуля образует мультипликативную группу. Единичным элементом является 1, а обратным
1
a
[
13
].
Другим примером группы является совокупность двоичных n-символь- ных комбинаций, которая образует группу из 2
n элементов вокруг операции
37

сложения по модулю 2. Единичным является элемент, состоящий из нулей
(например, 0000), а обратный элемент равен самому элементу (0101 ⊕ 0101 =
0000) [
13
].
6.2. Подгруппы и смежные классы
Подмножество элементов группы G называется подгруппой H, если оно удовлетворяет всем аксиомам группы. Для того чтобы определить, являет- ся ли H подгруппой G, надо проверить только замкнутость операции (G.1)
и наличие обратных элементов (G.4) в подмножестве H. Например, множе- ство целых чисел является подгруппой группы из множества действительных чисел [
13
,
14
,
15
].
Таким образом, любая подгруппа автоматически является группой [
14
].
Подмножество группы G, состоящее из ее единицы e, а также сама груп- па G тоже являются подгруппами. Они получили название тривиальных под- групп [
14
].
Важным классом подгрупп являются циклические подгруппы [
1
]. Цик- лической подгруппой группы G называется подгруппа H порядка m, состоя- щая из элементов (h, h
2
, h
3
, . . . , h m
−1
, h m
= e) = (e, h, h
2
, h
3
, . . . , h m
−1
) [
13
].
Для произвольной группы G и ее подгруппы H подмножество группы
G, состоящее из всех элементов вида h • g (или g • h), где h — прозвольный элемент подгруппы H, а g — некоторый фиксированный элемент группы G,
называется смежным классом элемента g по подгруппе H и обозначается через Hg (или gH) [
14
].
Смежные классы, образованные операцией h • g, получили название пра- вых смежных классов (Hg), а классы, образованные операцией g • h — левых смежных классов (
gH) [
13
]. Для абелевых групп правые и левые смежные классы совпадают [
13
,
1
].
Отдельный элемент g ∈
gH называется представителем смежного класса gH [
1
].
Для смежных классов верен ряд теорем [
14
].
1. Смежный класс Hg
0
любого элемента g
0
из смежного класса Hg совпадает с классом Hg. То есть, если два смежных класса пересекаются,
то они совпадают.
2. Два элемента g
1
и g
2
группы G тогда и только тогда принадле- жат одному смежному классу по подгруппе H, когда g
1
• g
−1 2
∈ H.
3. Смежный класс Hg тогда и только тогда совпадает с подгруппой
H, когда g ∈ H.
Для подгруппы H конечной группы G верна теорема Лагранжа. По- рядок конечной группы делится на порядок любой ее подгруппы. Соответ-
38

ствующее частное равно индексу подгруппы. При этом, под индексом под- группы понимается число смежных классов по подгруппе H [
14
].
Подгруппа H группы G называется нормальным делителем, если для любого элемента h ∈ H и любого элемента g ∈ G элемент g • h • g
−1
принад- лежит H. Любая подгруппа абелевой группы является конечным делителем
[
14
].
Для примера возьмём бесконечную группу целых чисел Z. В ней возь- мем подгруппу 5Z из чисел, кратных 5. Индекс подгруппы равен 5. Получим следующие смежные классы
0 + 5Z = {. . . , −15, −10, −5, 0, 5, 10, 15, . . .};
1 + 5Z = {. . . , −14, −9, −4, 1, 6, 11, 16, . . .};
2 + 5Z = {. . . , −13, −8, −3, 2, 7, 12, 17, . . .};
3 + 5Z = {. . . , −12, −7, −2, 3, 8, 13, 18, . . .};
4 + 5Z = {. . . , −11, −6, −1, 4, 9, 14, 19, . . .}.
В качестве другого примера возьмем конечную циклическую группу G
поворотов на углы, кратные
360
◦
9
G = {g
0
, g
1
, g
2
, g
3
, g
4
, g
5
, g
6
, g
7
, g
8
},
где g i
— поворот на i
·360
◦
9
Группа H = {g
0
, g
3
, g
6
} является подгруппой группы G, а подгруппы g
0
H = {g
0
, g
3
, g
6
},
g
1
H = {g
1
, g
4
, g
7
},
g
2
H = {g
2
, g
5
, g
8
}
являются левыми смежными классами группы G по подгруппе H. При этом
G = g
0
H ∪ g
1
H ∪ g
2
H.
6.3. Кольцо
Кольцом R называется множество элементов, на котором определены две операции — сложение и умножение, и выполняется ряд аксиом [
13
,
1
].
Аксиома R.1. Множество R является аддитивной абелевой группой.
Аксиома R.2.
Замкнутость операции умножения. Для любых двух элементов a, b ∈ R определено их произведение a
· b = c ∈ R.
Аксиома R.3. Для любых трех элементов a, b, c ∈ R выполняется ассо- циативный закон a
· (b · c) = (a · b) · c,
a
+ (b + c) = (a + b) + c.
39

Аксиома R.4. Для любых трех элементов a, b, c ∈ R выполняется дис- трибутивный закон a
· (b + c) = a · b + a · c,
(b + c) · a = b · a + c · a.
Аксиома R.5. В кольце существует элемент e, называемый единицей кольца, который является нейтральным элементом относительно умножения,
т. е. e · a = a · e = a для любого a ∈ R [
1
].
Элемент a 6= 0 кольца R называется делителем нуля, если в R суще- ствует такой элемент b 6= 0, что a · b = 0 [
1
].
В кольце для операции умножения аксиомы G.3, G.4 и G.5 (п.
6.1
) могут не выполняться. Если же операция умножения коммутативна в кольце, то та- кое кольцо называется коммутативным. Если в кольце существует единич- ный элемент относительно операции умножения (выполняется аксиома G.3),
то это кольцо называется кольцом с единицей [
13
].
Примером кольца являются все целые положительные и отрицательные числа и нуль, образующие коммутативное кольцо с единицей относительно обычных операций сложения и умножения [
13
].
6.4. Поле
Полем F называют коммутативное кольцо с единицей, в котором каж- дый ненулевой элемент имеет мультипликативный обратный элемент (т. е. об- ратный по умножению) [
13
,
1
].
Другими словами, полем называют множество, которое является адди- тивной абелевой группой; ненулевые же элементы этого множества образуют мультипликативную абелевую группу, и выполняется закон дистрибутивно- сти [
13
].
По аналогии с группами число элементов поля называется порядком поля. Поля, порядки которых конечны, называются конечными полями или полями Галуа. Конечные поля имеют наибольшее значение в теории кодиро- вания [
13
]. Подробнее поля Галуа рассмотрены в разд.
7
Поле имеет ряд свойств, вытекающих из его определения [
13
].
F.1. Для любого элемента поля a · 0 = 0 · a = 0.
F.2. Для элементов a, b ∈ F, не равных нулю, a · b 6= 0.
F.3. Для любых элементов a, b ∈ F a + b 6= 0.
F.4. Если a · b = a · c и a 6= 0, то b = c.
Примером поля является множество чисел (0, 1, 2, . . . , p − 1), где p —
простое число, образующее конечное поле, в котором сложение и умножение производятся по модулю p [
13
].
40

Контрольные вопросы

7. МАТЕМАТИКА ПОЛЕЙ ГАЛУА
7.1. Поле Галуа и его свойства
В теории помехоустойчивого кодирования широко используются ко- нечные поля, называемые полями Галуа в честь французского математика
Эвариста Галуа (1811–1832), чьи работы легли в основу теории групп.
Теория полей Галуа подробно освещены во многих работах, как отно- сительно давно написанных трудах Н. Г. Чеботарёва [
16
,
17
,
18
], М. М. Пост- никова [
14
,
15
], Р. Лиддла и Г. Нидеррайтера [
19
] и других авторов, так и недавно вышедших трудах, таких как монография О. С. Когновицкого [
4
].
Поле Галуа, обозначаемое GF(q), представляет собой конечное мно- жество, состоящее из q элементов, обладающих свойствами поля. Число эле- ментов поля q является простым числом или степенью простого числа. Если q
— простое число, то элементами поля GF(q) с характеристикой q явля- ются числа 0, 1, 2, . . . , (q − 1). При этом в соответствии со свойствами поля сложение и умножение элементов такого поля осуществляется с приведением по модулю q. Такое поле Галуа называется простым.
Если характеристика q является степенью простого числа p, т. е.
q
= p m
, где m — целое, то элементами поля GF(p m
) будут многочлены степе- ни (m − 1) вида a
0
+ a
1
x
+ a
2
x
2
+ . . . + a m
−1
x m
−1
,
(7.1)
где все коэффициенты a i
пробегают полную систему вычетов по модулю p,
т. е. принадлежат простому полю GF(p). В этом случае p называется основа- нием поля, а m — степенью поля. Само поле Галуа называется расширенным.
В дальнейшем будем рассматривать только поля Галуа по основанию
2 — двоичные поля Галуа GF(2
m
). Соответственно, коэффициенты a i
из фор- мулы (
7.1
) равны 0 или 1.
7.1.1. Образующий полином поля Галуа
Поле Галуа GF(p m
) строится на основе так называемого образующего
(порождающего) многочлена p(x), который является неприводимой прими- тивной функцией степени m.
Важно: Кроме обозначения p(x) для образующего многочлена поля в некоторых источниках используется обозначение g(x) (также используется для обозначения порож- дающего многочлена кода). Здесь, чтобы избежать путаницы, мы будем использовать p(x)
для образующего многочлена поля, а g(x) для порождающего многочлена кода.
Как уже было сказано выше, существуют готовые таблицы с образую- щими полиномами. Их можно как найти в литературе [
4
], так и воспользо- ваться математическими пакетами, например Matlab или Octave. Если же нет
42