5.3.5. Конечные поля

Определение конечного поля

Ранее в 1.3.2 дано определение поля  как коммутативного кольца с единицей, в котором каждый ненулевой элемент имеет мультипликативный обратный элемент. В теории помехоустойчивых кодов весьма важное значение имеют поля, образованные конечным множеством элементов – так называемые конечные поля Галуа (Galois Field), обозначаемые . В связи с этим дадим их развернутое определение.

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

1. GF.1. Из введенных операций над элементами поля одна называется сложением и обозначается как , а другая - умножением и обозначается как .
2. GF.2. Для любого элемента  существует обратный элемент по сложению  и обратный элемент по умножению  (если ) такие, что  и . Наличие обратных элементов позволяет наряду с операциями сложения и умножения выполнять также вычитание и деление: , . Поэтому иногда просто говорят, что в поле определены все четыре арифметические операции (кроме деления на 0).
3. GF.3. Поле всегда содержит мультипликативную единицу 1 и аддитивную единицу 0, такие что , и  для любого элемента поля.
4. GF.4. Для введенных операций выполняются обычные правила ассоциативности , , коммутативности ,  и дистрибутивности .
5. GF.5. Результатом сложения или умножения двух элементов поля является третий элемент из того же конечного множества.

Аксиомы GF.1 – GF.5 являются общими для полей как с конечным, так и с бесконечным числом элементов. Специфику же конечного поля определяет аксиома GF.5, где ключевыми являются слова «из того же конечного множества».

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

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

Очевидно, операции комбинирования элементов конечного поля не могут быть обычными сложением и умножением. Выполнение аксиомы GF.5 для простого конечного поля обеспечивается совершением арифметических операций по модулю числа , которое носит название характеристики конечного поля. Можно убедиться, что в кольце вычетов по модулю  (см. 5.3.1) каждый ненулевой элемент имеет обратный элемент тогда и только тогда, когда  – простое число [25, 26, 33]. Следовательно, кольцо вычетов по модулю простого числа  является простым полем . Элементами этого поля являются целые числа . Операции сложения и умножения в таком поле производятся по модулю . Пример простейшего двоичного поля  приведен в 5.3.3.

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

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

Очевидно, любые результаты вычислений в поле после приведения по модулю  должны оставаться обратимыми – только в этом случае наша система образует поле. Для этого используемый полином  должен быть неприводимым в поле , т.е. его нельзя разложить на множители, используя только многочлены с коэффициентами из . Это означает также, что  не имеет корней в поле . Аналогом неприводимого полинома является простое число в поле вещественных чисел.

К сожалению, регулярных методов поиска неприводимых полиномов не существует, они обычно определяются перебором. К настоящему времени имеются подробные таблицы неприводимых полиномов [30, 33].

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

Построение конечного поля

Построим конечное поле  и его расширение . Пусть элементами  являются 0 и 1, а элементами  – 16 всевозможных полиномов степени 3 и менее с коэффициентами из :

.

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

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

; ; ; .

(5.9)

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

В поле  операцией, которая может вывести результат за пределы поля, является умножение многочленов. Обычное перемножение может дать полином степени больше 3, не принадлежащий множеству элементов . Действительно, используя представление полиномов через векторы их коэффициентов [26], а также учитывая (5.9), получим

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

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

						– частное
					– остаток.

Или . Делением на полиномы первой степени  и , и второй степени ,  и можно убедиться, что рассматриваемый многочлен  неприводим над , а следовательно, не имеет в нем корней. В противном случае  раскладывался бы на сомножители  и , ибо корнями в поле  могут быть только 0 или 1.

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

В табл. 5.2 даны различные представления элементов  поля , заданного полиномом , а также полиномом .

Представление элементов поля по степеням примитивного элемента  удобно, в частности, при умножении элементов друг на друга. Для этого достаточно сложить их степени по модулю  (применительно к табл. 5.2 – по модулю 15). Например,

.

Прямые вычисления дают то же, но более трудоемко:

Таблица 5.2. Различные представления элементов поля

Ненулевые элементы поля
	Представление элементов поля через				Представление через
	полином	вектор	степень		вектор	степень
	1					1

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

Нетрудно убедиться, что примитивным в поле  является не только один элемент , но и , ,  и ряд других (предлагается их отыскать самостоятельно), а  и  таковыми не являются.

Основные свойства конечных полей и полиномов

Связь между элементами конечного поля

Все ненулевые элементы  конечного поля  являются степенями одного примитивного элемента:

,  ;  .

Порядок элемента поля

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

,

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

Возведение многочлена над полем  в степень

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

Так для многочлена над полем характеристики  справедливо , в чем можно убедиться на примере:

,

Корни полиномов

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

Известная аналогия этому имеется и в конечных полях. Любой многочлен степени , в том числе и неприводимый над полем  (не имеющий корней среди элементов этого поля), всегда имеет  корней в расширении , и этими корнями является часть элементов поля . Как элементы конечного поля, корни находятся между собой в определенном соотношении. Если  – неприводимый полином с коэффициентами из  и  – его корень, то  также являются его корнями. В поле  корнями неприводимого полинома степени  будут .

Полиномы

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

.

(5.10)

Пусть  – порядок элемента поля , т.е. . Следовательно,  – корень полинома . Если  является также и корнем неприводимого многочлена , то  делится без остатка на .

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

Многочлен  делится на  только в том случае, если  делится на . Действительно, если корни  являются также корнями , то  должно делиться на .

Циклотомические классы

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

, , , ,…,

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

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

Убедимся в этом на примере полинома  над полем . Поскольку сложение и вычитание по модулю 2 здесь неразличимы, то записи  и  эквивалентны. Разложение  на неприводимые полиномы  выглядит следующим образом [30]:

.

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

Класс  содержит один элемент,  – два элемента, а классы ,  и  – по четыре элемента. Это значит, что неприводимый над полем  полином, имеющий в качестве корня элемент  поля , должен быть полиномом первой степени, т.е. . Корни  и  принадлежат неприводимому полиному 2-й степени, который определяется по известному правилу:

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

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

 

Таблица 5.3. Распределение элементов поля  по циклотомическим классам

Корни				Циклотомические классы	Полиномы

 

Минимальные многочлены

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

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

Любой другой полином, имеющий тот же корень , что и минимальный, делится на . На  делится и полином , т.к. корнями последнего в соответствии с (5.10) будут все ненулевые элементы поля . Степень минимального многочлена определяется количеством компонентов циклотомического класса, которому соответствует его корень (табл. 5.3). Действительно, минимальный многочлен, показатели корней которого принадлежат циклотомическому классу , может быть записан в виде

.

(5.11)

Для  (см. 5.3.5):

.

Аналогично для :

.

С учетом (5.10) справедливо равенство

,

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

Минимальные многочлены элементов  и  равны. В частности, в поле  равны минимальные многочлены элементов  и . В этом можно убедиться, обратив внимание на тот факт, что элементы  и  всегда соответствуют одному циклотомическому классу (табл. 5.3), а следовательно, принадлежат набору корней одного неприводимого полинома. Более того, между собой равны минимальные многочлены всех элементов, соответствующих одному циклотомическому классу, т.к. любые два соседние из таких элементов находятся в соотношении  и .

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

Таблицы неприводимых многочленов [33] обычно содержат сведения о том, какие из многочленов являются примитивными, что позволяет избежать возможных затруднений в определении примитивных элементов поля. В табл. 5.4 приведены примитивные многочлены над  для  от 1 до 20 [3, 30].

Помимо представленных в таблице примитивными являются также полиномы, векторы коэффициентов которых написаны в обратном порядке. Такие полиномы называются двойственными, или взаимными исходным.

 

Таблица 5.4. Примитивные многочлены до степени

Это пары  и ;  и  и т.д. Использовавшийся ранее при построении  полином  примитивен, на основании чего в качестве примитивного элемента поля был взят .

Изоморфизм конечных полей

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

В теории конечных полей доказывается, что все поля  одного порядка  изоморфны («подобны по форме»), т.е. между  и  существует взаимнооднозначное отображение  друг на друга, сохраняющее операции сложения и умножения. Это означает, что для любых двух элементов  и  из  справедливы соотношения

,	(5.12)
.	(5.13)

Нетрудно убедиться, что между полями, построенными на основе неприводимых полиномов  и  (табл. 5.2), существует взаимнооднозначное отображение: . Простой подстановкой можно убедиться, что при таком отображении сохраняются операции сложения и умножения (5.12) и (5.13). Например, для сложения

,
.

Аналогично для умножения

,
.