Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


5.3.3. Кольца и поля

Определение кольца

Кольцом  называется множество элементов, на котором определены две операции – сложение и умножение, и в  выполняются следующие аксиомы:

  1. R.1. Множество  является аддитивной абелевой группой.
  2. R.2. Для любых двух элементов  и  из  определено их произведение:  (замкнутость операции умножения).
  3. R.3. Для любых трех элементов ,  и  из  выполняется ассоциативный закон, т.е.  и .
  4. R.4. Для любых трех элементов ,  и  из  выполняется дистрибутивный закон, т.е. справедливы равенства:  и .

Заметим, что в кольце для операции умножения аксиомы G.3, G.4 и G.5 могут не выполняться. Если же операция умножения коммутативна в кольце, то такое кольцо называется коммутативным. Если в кольце существует единичный элемент относительно операции умножения (выполняется аксиома G.3), то это кольцо называется кольцом с единицей.

Пример 5.8. Все целые положительные и отрицательные числа и нуль образуют коммутативное кольцо с единицей относительно обычных операций сложения и умножения.

Пример 5.9. Легко убедиться, что полная система вычетов по модулю  также образует коммутативное кольцо с единицей относительно операций сложения и умножения по модулю .

Определение поля

Полем  называют коммутативное кольцо с единицей, в котором каждый ненулевой элемент имеет мультипликативный обратный элемент (т.е. обратный по умножению).

Другими словами, полем называют множество, которое является аддитивной абелевой группой; ненулевые же элементы этого множества образуют мультипликативную абелевую группу, и выполняется закон дистрибутивности.

По аналогии с группами число элементов поля называется порядком поля. Поля, порядки которых конечны, называются конечными полями. Конечные поля имеют наибольшее значение в теории кодирования.

Отметим некоторые свойства полей, вытекающие из их определения.

1. Для любого элемента поля .

2. Для ненулевых элементов  и  поля .

3. Для любых элементов  и  поля .

4. Если  и , то .

Пример 5.10 Множество всех действительных чисел образует поле. Существует также поле комплексных чисел, поле рациональных чисел, но не может быть поля целых чисел, поскольку обратные элементы по умножению, кроме единицы, не являлись бы целыми.

Пример 5.11. Множество чисел , где  – простое число, образует конечное поле, в котором сложение и умножение производятся по модулю .

Пример 5.12. При  имеем простейшее двоичное поле, состоящее из двух элементов 0 и 1. Эти элементы являются соответственно единичными элементами относительно операций сложения и умножения по модулю 2, которые определяются правилами: ; ; ; ; . Так как , то операции сложения и вычитания в двоичном поле совпадают, а так как , также совпадают операции умножения и деления. Это поле находит широкое применение в теории и технике помехоустойчивого кодирования. Более сложные конечные поля рассмотрены в 5.3.5.

Кольцо полиномов

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

Степенью полинома называется наибольшая степень переменной  с ненулевым коэффициентом. Многочлен называется нормированным, если коэффициент при наивысшей степени  равен 1. Два полинома

 и

(5.8)

называются равными, если они имеют одинаковую степень, т.е. , и равные коэффициенты , . При этом считается, что , где  – единичный элемент поля . Полином, все коэффициенты которого равны нулю, называется нулевым. Степень нулевого полинома равна нулю.

В кольце полиномов операции сложения и умножения вводятся следующим образом. Для двух полиномов (5.8) их сумма

 

а произведение

 

В частности, если , , то . Нетрудно проверить, что при введенных таким образом операциях сложения и умножения множество  полиномов является кольцом, которое называется кольцом полиномов над полем .

Свойства делимости полиномов в кольце

Пусть  и  – два полинома степени  и  соответственно, причем . Говорят, что  делится на , если в кольце  существует третий полином  такой, что . Деление полиномов в кольце  не всегда возможно даже на ненулевой многочлен. Например, деление невозможно, если степень делимого меньше степени делителя.

Укажем основные свойства делимости полиномов в кольце.

1. Если  и  – полиномы из  и  делится на , а  делится на , то многочлены  и  отличаются друг от друга лишь множителем нулевой степени, т.е. , где  – элемент поля.

2. Если каждый из полиномов  и  делится на , то их сумма  и разность  делятся на .

3. Если ,  и  – полиномы из  и  делится на , а  делится на , то  делится на .

4. Ненулевые элементы поля  являются делителями любого полинома из .

5. Для любой пары полиномов  и  существует единственная пара многочленов  (частное) и  (остаток) таких, что  причем степень  меньше степени .

6. Полином  называется наибольшим общим делителем (НОД) полиномов  и , если  – полином наивысшей степени, который делит как , так и . НОД обозначается:  Два полинома называются взаимно простыми, если их НОД равен 1.

Полином, который делится только на себя и на элемент поля , называется неприводимым над полем .

Кольцо вычетов по модулю

При описании блочных кодов [25, 30, 33] широко используется понятие кольца вычетов по модулю некоторого полинома  с коэффициентами из поля .

Для полиномов существуют понятия, аналогичные введенным в 5.8 для чисел, если заменить в этих понятиях слово «число» словом «полином». Так, если при делении полиномов  и  из  на  получаются одинаковые остатки, то многочлены  и  сравнимы между собой по модулю многочлена  из  или .

Все полиномы, сравнимые между собой по модулю , образуют класс вычетов по модулю , а каждый полином класса называется вычетом по модулю . Каждый класс характеризуется своим представителем, в качестве которого обычно выбирают полином, степень которого меньше степени . Количество классов вычетов по модулю  равно числу многочленов, степени которых меньше степени .

Совокупность классов вычетов по модулю  образует кольцо вычетов по модулю . В качестве операций сложения и умножения в этом кольце используются сложение и умножение по модулю .

Пример 5.13. Рассмотрим кольцо классов вычетов по модулю полинома  над двоичным полем. Полиномы вида , где  – произвольный полином, степень которого меньше 2, при фиксированном  образуют класс вычетов по модулю . Так как всего имеется 4 разных полинома  степени меньше 2, то возможны 4 следующие класса вычетов:

Здесь  – произвольный полином. В качестве представителей классов обычно выбирают вычеты наименьшей степени, которые совпадают с полиномами  и образуют кольцо классов вычетов по модулю полинома , т.е. множество .

 



<< ПредыдущаяОглавлениеСледующая >>