Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

ГЛАВА 2. АЛГЕБРАИЧЕСКОЕ ВВЕДЕНИЕ

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

Данная глава состоит из двух частей. Сначала вводятся наиболее значительные алгебраические понятия и каждое из них иллюстрируется несколькими примерами. В конце главы дается обзор некоторых разделов теории векторных пространств и матриц. Гл. 6 также является чисто математической и посвящена теории колец и конечных полей. Эти две главы ни в коей мере не претендуют на полное математическое изложение материала, а скорее дают лишь минимальные математические предпосылки для исследования кодов.

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

2.1. Группы

Группой О называется совокупность объектов или элементов, для которых определена некоторая операция и выполняются аксиомы Пусть -элементы группы. Операция — это однозначная функция двух переменных, которая может быть обозначена , но обычно записывают как — с или и называют сложением пли умножением, даже если эта операция не является арифметическим сложением или арифметическим умножением обычных чисел.

Аксиома G.1 (замкнутость). Операция может быть применена к любым двум элементам группы, в результате чего получается третий элемент группы.

Аксиома G.2 (ассоциативный закон). Для любых трех элементов и с группы если операция записана как сложение, или а если операция записана как умножение.

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

Аксиома G.3. Существует единичный элемент.

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

Аксиома G.4. Каждый элемент группы обладает обратным элементом.

Если операция называется сложением, то обратный элемент, соответствующий элементу а, обозначается — а и определяется как решение уравнения Если операция называется умножением, то обратный элемент обозначается и определяется уравнением

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

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

Теорема 2.1. Группа обладает единственным единичным элементом, и каждому элементу группы соответствует единственный обратный элемент.

Доказательство. В группе только один единичный элемент, ибо если имеются два единичных элемента 1 и 1, то Аналогично обратный элемент единствен, потому что если бы некоторому элементу группы соответствовали бы два обратных элемента выполнялась бы цепочка равенств так что эти элементы должны были бы совпадать. Ч. т. д.

Заметим, что обратный элемент произведения равен произведению обратных элементов сомножителей, взятых в обратном порядке, так как и поэтому

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

Многие важные группы получаются как совокупность преобразований некоторого пространства. Групповая операция, называемая умножением, определяется при этом следующим образом: преобразование есть результат последовательного выполнения сначала преобразования а затем преобразования а. Например, совокупность вращений -мерного евклидова пространства является группой. Заметим, что вращения двумерного пространства образуют абелеву группу, в то время как вращения трехмерного пространства не коммутативны.

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

Например, одним из возможных преобразований является поворот квадрата на 90° против часовой стрелки, так что А переходит в переходит в переходит в переходит в С, Это преобразование можно записать с помощью обозначений, обычно используемых для подстановок»

Имеется всего восемь таких преобразований:

(см. скан)

Таблица умножения в этом случае имеет вид

(см. скан)

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

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

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