Поля Галуа. Поля остатков от деления. 4б. L4. corr. 1.Поле, 2.Мин. функция. M это поле характеристики p. Теорема 14
 Скачать 336 Kb.
|
|
Лекция 4б 1. Поле Галуа. Определение. Генерация поля Поле – это множество не менее чем из двух элементов, над которыми задана пара бинарных операций, называемых сложением и умножением и обладающих тем свойством , что для них существуют обратные операции: вычитание и деление (кроме деления на ноль). В любом поле множество всех элементов образует по операции сложения циклическую (аддитивную) группу; аналогично множество ненулевых элементов образует по операции умножения циклическую (мультипликативную) группу. Поле GF( pr ) называется расширением поля GF(p). Теорема 6.13. Пусть p(x) - многочлен с коэффициентами из поля F = GF(p). Алгебра многочленов над полем F по модулю p(x) является полем тогда и только тогда , когда многочлен p(x) - неприводим в поле F, т.е. если p(x) нельзя представить в виде произведения многочленов с коэффициентами из F. Поле, образованное многочленами над полем F (т.е. c коэффициентами из этого поля) по модулю неприводимого многочлена p(x) степени m, называется расширением поля степени m над F, т.е. GF(pm) . Первоначальное поле F называется основным полем. Поле много –  ( изоморфный – сходный по форме) Поля Галуа, которые могут быть образованы многочленами по модулю неприводимого многочлена над полем GF(p), называются полями характеристики p. Таким образом, при любом выборе m поле GF(pm) - это поле характеристики p . Теорема 6.14. В поле характеристики p имеет место равенство (a +b)p =ap + bp. Генерация элементов поля GF(pm) Конечные поля GF(pm) порядка pm , где характеристика p – простое число, а размерность m - натуральное число, порождаются с помощью неприводимых полиномов степени m. Особенно удобно использовать примитивные неприводимые полиномы F(x); в этом случае простое поле GF(p) может быть расширено до поля GF(pm) за счёт присоединения корня α полинома F(x). В таблице 11 представлены примитивные неприводимые полиномы характеристики 2 (до степени m =10) с коэффициентами из простого поля GF(2), а также полиномы характеристик 3, 5, 7 малых степеней. Впрочем, с математической точки зрения выбор полинома не существенен, так как все конечные поля одного и того же порядка изоморфны. Таблица 11. Неприводимые примитивные полиномы невысоких степеней r и характеристик p  Пусть основание поля q=pm  Группа, которая состоит из всех степеней одного из её элементов, называется циклической группой. В технике помехоустойчивого кодирования наибольшее применение получили поля характеристики p=2. Алгебраические операции над элементами поля GF(2^a)  …..как произведения по модулю многочлена F(x), определяем все элементы поля . Отсюда ясно, что поле GF(2a) полностью определяется многочленом F(x). Заметим , что для βi deg i вычисляется по mod n=2a -1. Согласно определению обратного элемента, βi β –i = β0= βn =1, если n – порядок элемента β. Отсюда β –i = βn-i .   2. Корни неприводимого многочлена и минимальные функции Элемент b поля GF(qm) называется корнем многочлена a(x) над GF(q) , если при x = b a(b)=0. Отсюда следует, что многочлен a(x) делится без остатка на многочлен x+b, т.е. a(x) = (x+b)h(x). Если же a(x) делится без остатка на (x+b)s, но не делится на (x+b)s+1 , то элемент b называется корнем кратности s многочлена a(x). При s=1 корень называется простым. Степенью многочлена называется наибольшая степень x в слагаемом с ненулевым коэффициентом. У многочлена a(x) не может быть в поле GF(qm) при любом m более чем deg a(x) корней. В то же время существует такое m , что многочлен a(x) имеет в поле GF(qm) ровно deg a(x) корней при условии, что каждый корень считается столько раз, какова его кратность. В любой конечной группе может существовать конечное число элементов и по- этому где- то должно появиться повторение, т.е. gi = gj для некоторых i и j . Умножая это равенство на (gi )-i , получим 1 = g j -i . Пусть e - наименьшее целое положительное число, такое, что ge =1. Число e называется порядком элемента g.Группа, которая состоит из всех степеней одного из её элементов, называется циклической группой. Минимальной функцией или минимальным многочленом над полем GF(2а) для элемента bGF(2am) называется нормированный многочлен m(x) наименьшей степени p с коэффициентами из GF(2а), не приводимый над этим полем, такой, что m( b) =0. Нормированным многочленом называется такой многочлен, у которого коэффициент при наивысшей степени x равен 1. Очевидно, что над полем GF(2) все многочлены нормированы. Неприводимым многочленом называется такой многочлен степени p над полем GF(q), q = 2a, который не делится ни на один из многочленов степени меньшей p (но большей 0) с коэффициентами из того же поля. Неприводимый многочлен не может быть представлен в виде произведения многочленов с меньшими степенями. Неприводимый многочлен, одним из корней которого является примитивный элемент b расширенного поля , называется примитивным. Неприводимый многочлен f(x) степени m, который делит двучлен Xn +1, n = 2m – 1, и не делит никакой двучлен Xs + 1, s < 2m - 1, называется примитивным.  Всякий многочлен p(x) степени m над GF(2) (т.е. с коэффициентами из этого поля), неприводимый над этим полем и имеющий корень b в расширенном поле GF(2m), имеет корни b,b2,b4,b8 и так далеее до bh, h= 2(m – 1) . Пример q = 2. Корни минимальной функции образуют совокупность {β 2^j}, где j - показатель степени 2, изменяется в пределах 0 j m – 1, т.е. имеются m различных корней β,β2,β4,... и т.д. mi(x)=x + bi - минимальная функция над GF(2a) для элемента bi, i = 0,1,…, 2a - 2. Теорема 6.27. Все корни неприводимого многочлена имеют один и тот же порядок. Порядок корней неприводимого многочлена называется показателем, которому этот многочлен принадлежит. Если неприводимый многочлен принадлежит показателю e, то он является дели- (e = 2m – 1)   Основные свойства минимальной функции  В частности, k = m. Пусть основание основного (исходного) поля q = 2a, GF(2am) - расширенное поле. Случай а=1, q=2 соответствует разложению многочлена xn+1, где n= 2m -1, на произведение двоичных неприводимых многочленов. Исследуем его на примере m =4. В качестве элемента b выберем примитивный элемент поля GF(24). Обозначим через mi(x) минимальную функцию над GF(2) для bi, i = 0,1,.....,14. Из указанного выше свойства минимального многочлена имеем по mod n = 2m – 1 = 15, при a=1, q=2, m=4 в GF (24) : ----------------------------------------------------------- 1) Поле GF(2am), m 1, называется расширением поля GF(2a). mi(x) для βi, i = 0,1,....., 14. Deg mi(x) £ m=4, следовательно, не более m=4 корней для каждой mi(x). m0(x) = x +1, корень β0, m1(x) = m2(x)=m4(x)=m8(x), m3(x)=m6(x)=m12(x)=m9(x), m5(x)=m10(x), m7(x)=m14(x)=m13(x)=m11(x). Deg mi(x) m . Т.к. минимальные многочлены не имеют кратных корней,то X15 – 1 = m0(x)m1(x)m3(x)m5(x)m7(x). Причём, deg mi(x) = 1 4 4 2 4. m1(x) = (x + β)(x + β2)( (x + β4)(x + β8) = x4 +x + 1, m3(x) = (x + β3)(x + β6)( (x + β12)(x + β9) = x4+ x3+ x2+ x + 1, m5(x) = (x + β5)(x + β10) = x2 +x + 1, m7(x) = (x + β7)(x + β14)( (x + β13)(x + β11) = x4+ x3 + 1, или m7(x) =m8-1(x) = x4 (x - 4 +x -1 + 1) = (x4 + x3 + 1) , где f -1(x) –многочлен, двойственный f(x), определяемый как f -1(x) = xn f(x -1), а n = deg f(x). Разложение мрогочлена xn -1 на произведение минимальных многочленов над GF(2) проводится аналогично при любых m. При этом минимальные многочлены mi(x) могут быть взяты из таблиц или вычислены. --------------------------------------------------------------------------------------------------------- Случай m=1 соответствует рассмотрению q-ичных кодов с основанием q= 2a. При m = 1 рассмотрим разложение многочлена xn+ 1, n = 2a – 1, на произведение минимальных многочленов над полем GF(2a). В качестве элемента b выберем примитивный элемент поля GF(2a). n - 1 В поле GF(q= 2a) имеет место разложение xn – 1= П (x – bi), ( 26 ) i= 0 где Mi(x) = x - bi - минимальный многочлен над полем GF(2a) для элемента β i , i = 0,1,….., 2a – 2. Т.о., разложение многочлена (x(2a – 1)) + 1 на произведение минимальных многочленов над GF(2a) при любом а однозначно определяется выр. ( 26 ). |