1.3.4. Основные понятия о свойствах многочленов и полях Галуа

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

Полем Галуа называется конечное коммутативное поле. Конечное поле - это конечное множество из q элементов, в котором определены правила для выполнения арифметических операций. Поле Галуа из элементов обозначается.

Поля Галуа обладают следующими свойствами:

• в поле определены две операции: сложение и умножение;

• результатом сложения или умножения двух элементов поля является элемент этого же поля;

• поле всегда содержит мультипликативную единицу 1 и аддитивную единицу 0, т.е. идля любого элемента, принадлежащего полю;

• для любого элемента , не равного нулю, существует обратный элемент по сложению (минус) и по умножению (), такой, чтои(в случаеобратный элемент совпадает с самим элементом);

• выполняются обычные правила ассоциативности , коммутативностии дистрибутивности.

Для каждого допустимого значения существует ровно одно поле.

Если - простое число, то элементами поля являются числа 0, 1, ..., (-1), а сложение и умножение являются обычными сложением и умножением по модулю.

Если является степенью простого числа, т.е. если, то элементами поля являются все многочлены степениили менее, коэффициенты которого лежат в простом поле.

Правила умножения и сложения таких многочленов получаются из обычного умножения и сложения многочленов и последующего приведения результата по модулю некоторого специального многочлена степени. Этот многочлен обладает тем свойством, что его нельзя разложить на множители, используя только многочлены с коэффициентами из поля. Такие многочлены называютсянеприводимыми, они аналогичны простым числам. Как и простые числа, они могут находиться методом перебора. Для двоичных кодов такие многочлены должны быть неприводимыми над полем . Наиболее подробная таблица неприводимых над полеммногочленов представлена в [2,4,10].

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

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

Пусть неприводимый многочлен имеет вид

.

(1.19)

Пусть - примитивный элемент поля. Если неприводимый многочленпримитивный, то.

Запись поля Галуа осуществляется в виде набора из многочленов степени, не превышающей. Первый элемент записи всегда равен нулю (нулевой элемент поля) и обычно в записи не приводится. Остальныемногочленов представляют собой степени от 0 допримитивного элемента поля. Здесь и далее принимается, что старшие степени многочленов записываются слева, младшие справа.

Построение поля проводится в следующем порядке:

• записываются степени примитивного элемента от 0 до (m-1); запись производится в виде

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

;

• записываются многочлены, соответствующие остальным степеням , отдо. Указанные степениопределяютсяпосредством: а) умножения предыдущего многочлена, т.е. многочлена, соответствующего , на; б) заменына многочлен; в) приведения подобных членов.

Таким образом, поле Галуа GF(2^m) запишется в виде

(1.20)

Умножение элементов поля Галуа сводится к сложению степеней умножаемых элементов и приведению результата в диапазон …. Операция сложения элементов поля Галуавыполняется над двоичными числами по модулю 2. Степеньопределяется по соответствию результата сложения в поле вида (1.20).

Пример. Многочлен является неприводимым примитивным многочленом третей степени. Следовательно, при помощи этого многочлена может быть построено поле. Согласно формулам (1.20), поле будет иметь вид

.

(1.21)

В соответствии с (1.21) выражение можно вычислить следующим образом:² + ⁵ = ³ = (011); ³ = ⁴ = (110); 1 + ³ =  = (010);  = ² = (100); ⁴ + ² =  = (010). Таким образом, искомое выражение будет равно () =  = (010).

Также для построения поля Галуа важны следующие свойства:

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

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

• если - корень многочлена, тоназываетсяминимальной функцией , если- примитивный элемент, то(x) называется примитивным многочленом;

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

Пример. Многочлен неприводим над полем, но он может быть разложен на множители над полем. Если полеGF(2³) задано в соответствии с (1.21), то подстановкой можно найти, что  является корнем . Действительно,() = ³ +  + 1 = (011) + (010) + (001) = (000) = 0. Также корнями являются² и ⁴, что можно проверить подстановкой. У неприводимого многочлена над полем может быть не болееm корней. Дальнейшее повышение степени  дает повторение тех же самых корней (,² и ⁴), действительно, ⁸ = , ¹⁶ = ² и т.д. Многочлен может быть также получен, если известно, что, ² и ⁴ являются корнями одного и того же многочлена. Например, .

Элемент  является примитивным элементом поля GF(2³), поэтому является примитивным многочленом. Многочлен (x⁷-1) разлагается на множители следующим образом: (x⁷-1) = (x³+x²+1)(x³+x+1)(x+1). Корнем примитивного многочлена (x+1) является ⁰ = 1, корнями (x³+x+1) - , ², ⁴; корнями (x³+x²+1) - ³, ⁶, ¹²=⁵. Все эти семь корней являются ненулевыми элементами поля GF(2³), состоящего как раз из семи ненулевых элементов.