ГЛАВА 2

ВВЕДЕНИЕ В АЛГЕБРУ

Поиск хороших кодов, контролируюш,их ошибки, в значительной мере связан с мощными и изящными структурами современной алгебры. Многие найденные важные коды основаны на структурах колец многочленов и полей Галуа. Кроме того, эти алгебраические понятия и методы являются необходимым рабочим инструментом для конструирования кодеров и декодеров. Данная глава и гл. 4 посвящены изложению тех разделов алгебры, которые важны для теории кодов, контролирующих ошибки. Изложение ведется строго, но ограничивается лишь используемым в дальнейшем материалом.

2.1. 2-ПОЛЕ И 6-10-ПОЛЕ

Вещественные числа образуют известное множество математических объектов, которые можно складывать, умножать, вычитать и делить. Аналогично комплексные числа образуют множество объектов, которые можно складывать, вычитать, умножать и делить. Обе эти арифметические системы являются важнейшей основой всех инженерных дисциплин. Нам необходимо построить другие, менее известные арифметические системы, полезные при исследовании кодов, контролирующих ошибки. Такие новые арифметические системы состоят из множеств и операций над элементами этих множеств. Хотя мы будем называть операции «сложением», «вычитанием», «умножением» и «делением», они не обязательно будут теми же операциями, что в элементарной арифметике.

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

1) абелееа группа ): множество математических объектов, которые можно «складывать» и «вычитать»;

2) кольцо: множество математических объектов, которые можно «складывать», «вычитать» и «умножать»;

3) поле: множество математических объектов, которые можно «складывать», «вычитать», «умножать» и «делить».

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

Прежде чем переходить к формальным понятиям, выполним некоторые вычисления в простейшем из всех возможных полей, а именно в поле, состоящем только из двух элементов. (Поле вещественных чисел содержит бесконечное число элементов.) Обозначим через О и 1 два элемента поля и определим операции сложения и умножения равенствами

0 + 0 = 0, 0-0 = 0, 0+1 = 1, 0-1=0, 1+0 = 1, 1-0 = 0,

1 + 1=0, Ы = 1.

Так определенные сложение и умножение называются сложением по модулю 2 и умножением по модулю 2. Заметим, что из равенства 1 + 1=0 следует что -1 = 1, а из равенства 1-1 = 1 -• что 1" = 1. Используя это, легко проверить, что, за исключением деления на нуль, вычитание и деление всегда определены. Алфавит из двух символов О и 1 вместе со сложением по модулю 2 и умножением по модулю 2 называется полем из двух элементов и по приведенным в гл. 4 соображениям обозначается через GF (2).

В указанной арифметической системе можно осуществлять известные алгебраические операции. Пример дается следующей системой уравнений над полем GF (2):

X + Г + Z = 1, X +Y =0, X -I- Z = 1.

Эту систему можно решить вычитанием третьего уравнения из первого, что дает F = 0. Тогда из второго уравнения получаем X = О, аиз первого уравнения Z = 1. Подстановкой получен-

) Абелева группа является частным случаем группы. Арифметическая операция группы общего вида слишком слаба для того, чтобы называться сложением.

ного решения в исходную систему уравнений проверяем, что оно правильно.

Чтобы получить другой способ решения, предположим, что можно доказать возможность применения обычных методов линейной алгебры над полем GF (2). Определитель системы вычисляется следующим образом:

1 1 1

D = det

1 1 О 1 О 1

Эту систему уравнений можно решить по правилу Крамера:

1 1 1

0 1 О

1 О 1

= 0, F = D-i.

L1 1

Го О 1 1 1

= 0,

1 1 1 1 1 О 1 О 1

= 1.

Вторым примером поля является 6-10-поле. Это поле содержит 16 элементов, которые мы обозначим символами О, 1,2, 3, 4, 5, 6, 7, 8, 9, Л, В, С, D, Е, F. Таблицы сложения и умножения в этом поле выписаны на рис. 2.1. Отметим, что здесь правила сложения и умножения значительно отличаются от известных правил сложения и умножения вещественных чисел; в то же время эти таблицы обладают внутренней закономерностью и позволяют осуществлять вычитание и деление. Для деления надо взять X : у = х- iy~), где у~ - элемент поля, удовлетворяющий условию у-у~ = 1. Просмотр таблицы умножения показывает, что каждый ненулевой элемент имеет обратный, и, следовательно, деление всегда определено, за исключением деления на нуль.

Большинство методов линейной алгебры, так же как и матричные операции, переносится на случай произвольного поля. Именно поэтому поля с конечным числом элементов оказались очень полезными. Мы будем изучать эти поля и найдем способы построения таблиц сложения и умножения, которые порождают поле даже для большого числа элементов. Со временем мы увидим, что поля с q элементами можно построить тогда и только тогда, когда q равно р", где р - простое, am - произвольное положительное целое число. Но прежде мы должны ввести понятия групп и колец.