Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
6.4. ПОЛЯ И МНОГОЧЛЕНЫ
Значительная часть алгебраической теории кодирования основана на теории конечных полей. Грубо говоря, поле — это множество элементов, в котором сложение, вычитание, умножение и деление могут трактоваться как обычные правила арифметики. Более точной является следующая формулировка: поле — это множество по меньшей мере двух элементов, замкнутое*) по двум операциям, называемым сложением (+) и умножением (•), и удовлетворяющее следующим аксиомам:
Множество элементов называется замкнутым по операции •, если для любой пары элементов (а, Ь), принадлежащих множеству, а ¦ Ь также принадлежит этому множеству.
229
1. Множество элементов образует абелеву группу по операции сложения.
2. Множество ненулевых элементов (где 0 является нейтральным элементом группы по операции сложения) образует абелеву группу по операции умножения.
3. Выполняется дистрибутивный закон
(a Jrb)-c = a- cJrb-c для всех а, Ъ, с. (6.4.1)
Легко непосредственно убедиться, что множество действительных чисел с обычными операциями сложения и умножения удовлетворяет этим аксиомам. Множество двоичных элементов 0 и 1 с операцией сложения по модулю 2 и обычным умножением также удовлетворяет этим аксиомам. Однако множество целых чисел не удовлетворяет этим аксиомам, поскольку любое целое число, большее 1, не имеет обратного по операции умножения элемента, который являлся бы целым числом.
Условимся всюду обозначать нейтральный по операции сложения элемент символом 0, а нейтральный по операции умножения элемент — символом 1. Будем всюду обозначать обратные элементы по операциям сложения и умножения как —а и а_1 соответственно.
Следующие соотношения выражают некоторые элементарные свойства полей:
а • 0 = 0 • а = 0 для всех а\ (6.4.2)
а • Ь Ф 0 для всех ненулевых а, Ь\ (6.4.3)
— (а • Ь) = (—а) ¦ b = а • (—Ь) для всех а, Ь; (6.4.4)
a-b = a-b'=3~b = b' для а Ф 0. (6.4.5)
Чтобы проверить справедливость (6.4.2), допустим, что а и b произвольны и заметим, что а-Ь = а-ф + 0) = а- Ь + а- 0. Отсюда следует, что а • 0 является нейтральным элементом в группе по сложению [см. (6.3.5)] и а • 0 = 0. Соотношение (6.4.3) утверждает, что множество ненулевых элементов замкнуто по умножению; это следует из аксиомы 2. Чтобы проверить (6.4.4), запишем следующее соотношение
0 = 0 • b = [a -f (—а)\ ¦ b = а • b + (—а) • Ь.
Поэтому (—а) • b является обратным элементом по операции сложения для а • Ь. Вторая часть равенства (6.4.4) доказывается аналогично. Из (6.4.4) следует, что, не вызывая недоразумений, знак минус может использоваться без скобок; в дальнейшем мы так и будем поступать. Чтобы доказать математическое правило сокращения (6.4.5), заметим, что из а ¦ b = а • V следует 0 = а ¦ b — а • Ъ' = а ¦ (Ь — Ь'). Так как аф 0, то отсюда следует, что b — Ь' = 0 и b = Ь'.
В дальнейшем будут рассматриваться лишь поля Галуа, которые по определению являются полями с конечным числом элементов. Следующая теорема будет часто весьма полезной при решении вопроса
о том, образует ли поле некоторое конечное множество элементов.
Теорема 6.4.1. Аксиома 2 в данном выше определении поля для случая конечного множества элементов может быть заменена более
230
слабым условием (2'): операция умножения является коммутативной и ассоциативной и выполняется (6.4.3).
Доказательство. Легко видеть, что (6.4.2), (6.4.4.) и (6.4.5) по-прежнему верны, поскольку их доказательства не опирались на аксиому 2. Пусть а — ненулевой элемент множества; рассмотрим последовательность а, а2, а3, где а2 = а-а, as = а-а-а и т. д. Так как рас-сматриваемое множество конечно, то должны существовать два целых числа / и i, j > i, для которых
а1 — а1 = а1-а’~1. (6.4.6)
Покажем, что а<~‘ является нейтральным элементом по операции умножения. Умножая обе части (6.4.6) на произвольный элемент b и сокращая на а‘ (который является ненулевым элементом), получаем
Ь = Ь-а>~1.
Отсюда следует, что а>~1 является нейтральным элементом по операции умножения. Наконец, обратный по операции умножения элемент для а равен ai-‘~l (или а, если / = i + 1). Так как а — произвольный элемент, то любой ненулевой элемент имеет обратный и аксиома 2 справедлива. |
Чтобы пояснить на примере использование этой теоремы, выберем простое число р и рассмотрим множество целых чисел 0, 1, ..., i, где
i — р — 1. Введем операции сложения и умножения по модулю р [это означает, что элемент поля i + j задается остатком Rp (i + /); от деления обычной суммы i + j на р]. Обратный по сложению элемент для элемента i — это элемент, соответствующий р — i Существование обратного по умножению элемента не совсем очевидно, но следует из теоремы 6.4.1. Поэтому для любого простого р неотрицательные целые числа, меньшие чем р, образуют поле в арифметике по модулю р. Если р не простое, эти элементы не могут образовывать поле в арифметике по модулю р, поскольку существуют два ненулевых элемента, обычное произведение которых равно р; отсюда следует, что их произведение по модулю р равно нулю. Ниже мы покажем, то существуют поля с рп элементами, где р — простое, а п — большее 1 целое число, однако правила сложения и умножения в этих полях не являются сложением и умножением по модулю рп. Как и в теории групп, порядок поля Галуа равен числу элементов в поле; в дальнейшем будем обозначать любое поле с q элементами через GF(q).
