в табл. 2.1, 2.2 приведены результаты расчетов, иллюстрируюндих работу алгоритма на том же примере, что и ранее. Из этих таблиц видно, что при вычислениях в поле рациональных чисел (вообще говоря, и в других бесконечных полях -вещественных и комплексных) возникает необходимость оперирования с дробями, даже если в исходные данные и в конечный результат входят только целые числа,

как в приведенных примерах.

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

ГЛАВА ТРЕТЬЯ

АРИФМЕТИКА КОНЕЧНЫХ ЦИКЛИЧЕСКИХ ГРУПП

И КОНЕЧНЫХ ПОЛЕЙ

ЗЛ. ВВЕДЕНИЕ В АЛГЕБРЫ С БИНАРНЫМИ ОПЕРАЦИЯМИ

Исходные понягия и определения. В современной математике под алгеброй понимается наука о множествах объектов, между которыми установлены так называемые алгебраические операции [32, 34]. В свою очередь алгебраическая операция - это правило, которое произвольному упорядоченному набору элементов данного множества ставит в однозначное соответствие строго определенный элемент этого же множества. Возможен вариант, когда указанное соответствие регламентируется не для любых наборов элементов; такая операция называется частичной. flaj[ee подобные операции не рассматриваются.

Наибольшее значение имеют бинарные операции, которые каждой упорядоченной паре элементов данного множества ставят в соответствие третий элемент этого множества. Таким образом, бинарная операция на множестве К - это отображение К X К -К, где декартово произведение КХ К суть множество всех упорядоченных пар элементов из заданного множества К.

Фундаментальное значение для теории помехоустойчивого кодирования имеют особые алгебры - конечные циклические группы и конечные поля - конечные множества с од1[ой или двумя бинарными операциями, наделенными специальными свойствами.

Группа. Множество К с заданной на нем бинарной операцией * называется группой (обозначение: G = <К: * >), если операция * наделена следующими свойствами (удовлетворяет списку слелующих аксиом) [32-34]:

I. Замкнутость - любой паре (а, /3) элементов из множества К ставится в однозначное соответствие третий элемент уК, возможно,

совпадающий с одним из исходных элементов а либо (3 (система А"; * > с этим свойством называется группоидом).

2. Ассоциативность, т. е. (а * /3) * 7 = а * ()3 * 7) = а * /3 * 7 для [а, j3, 7] (система со свойствами пп. 1 и 2 - полугруппа).

3. Наличие "нейтрального" элемента е, такого, что еа~а*е=а для К (система со свойствами пп. 1 , . . 3 - моноид).

4. Существование для каждого элемента К обратного элемента хЕ: К, такого, что X * а = а *х = е.

Важное алгебраическое понятие "группа" может быть определено с помощью и иного списка аксиом, даже менее избыточного [34], например:

а) система <К; *>, т. е. множество К с бинарной операцией *, является группой, если эта операция удовлетворяет аксиомам пп, 1 и 2 (замкнутость и ассоциативность), а также для любых а, lGK однозначно разрешимы относительно неизвестных х,у уравнения*

(3.1)

б) система <К; *> является группой, если операция * удовлетворяет аксиомам пп. 1 и 2, а в множестве К содержатся левый нейтральный Cjj и левые обратные элементы, такие, что *а = а; * ~ для всех а В К.

Левый нейтральный и левые обратные элементы в утверждении гк "б" могут быть заменены на аналогичные правые э][ементы: а+е =

Левый и правый нейтральные элементы группы равны между собой и совпадают с единственным нейтральным элементом е. Для любого элемента а группы его левый Хд и правый Хд обратные элементы равны и совпадают с его единственным обратным х, т. е. а * х = Xj, * а =

= х*а = а *х = е для всех ос €

Группа называется коммутативной или абелевой в честь выдающегося норвежского математика Н. Абеля (N. Н. Abel, 1802-1829), если групповая операция * является коммутативной. Таким образом, аксиомы пп. 1 ... 4 дополняются еще одной.

5. Коммутативность, т.е. а*/3=13* а. Вместо символа * бинарной операции принято использовать знак суммы "+" (аддитивная запись) или произведения "•" (мультишшкативная запись), причем точку как

символ операции умножения между бyквaми-coмнoжитeJ[Ями допустимо опускать.

При аддитивной записи нейтральный элемент обозначается О, т. е. 0 + а= а + 0=о;, а обратный к а элемент называется противоположным и обозначается {-а), т. с. а + {-а) = 0.

Огсгсма <А; * >с замкнутой о;шрацией, удовлетворяющей условию (3.1), называется квази[ руиной [34].

При мультипликативной записи нейтральный и обратный к а элементы обозначаются соответственно 1 и а", т. е. о;-1=1*о;=а и ос а" ~ а~ а = [.

Подгруппой группы G = </С; *> называется подмножество АГ С К, являющееся группой относительно той же операции *.

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

Если множество К - конечное (содержит ограниченное число элементов), то группа G = КК; *> называется конечной. Любая подгруппа конечной группы, естественно, также конечна.

Для мультипликативной группы G = </С; •> вводится понятие натуральной степени а", где п- нуль или натуральное число:

раз

Это понятие без труда обобщается:

для отрицательных степеней, если рассмотреть степени обратного к а элемента а ~

а а = a- . . . , (а")" = а";

для рационалЫ[ых степеней, если ввести корни

где д - а, / = 2, 3, . . . , /с.

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

Группа называется циклической, порожденной элементом а, если

каждый элемент есть некоторая натуральная степень а .

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

Если же при некотором w выполняется равенство = 1 и w - минимальное натуральное число с таким свойством, то говорят, что элемент а имеет порядок w. В этом случае циклическая группа конечна и также имеет порядок w (число ее элементов X = w):

для л = "З к\ к - произвольное целое число.

Всякая группа простого порядка (w - простое число) является циклической. С другой стороны, всякая циклическая группа является абелевой, причем справедливы соотношения

«"а" - а" (а")

(3.2)