= До 2+22 +азг + 4* + .. . + (5.68)

где коэффициенты - какие-либо числовые параметры выбранного поля.

Производная от полинома (5-68) по z определяется, как известно, соотношением

/,(2)= ",-Д,.2- =

/ = 1

ai + 22 + Здз z + 44 2 + .. .-nafjZ ,

где числовые коэффициенты 2, 3, 4, .. ., « означают, что соответству-юпщй член суммируется 2, 3, 4, .. .,« раз. В данном бесконечном поле операции "просуммировать п раз а" и "умножить п на а" совпадают. Они различны в конечном поле. Представим теперь, что полином (5.68) задан над каким-либо полем Галуа. Тогда формальная производная по аналогии определяется соотношением

i = 1

((1)) Ха, + ((2)) X (aj2) + ((3))X («32) + ..- +

+ ((«)) X («„г"-!), где ((/)) = 1 + 1 + ... + 1 (г штук

(5.69)

) ; значком " X " обозначена операция "просуммировать столько-то раз", т. е. нужно член повторить два раза, член anz - повторить п раз и т. д. Эта операция не совпадает с операцией умножения над конечным полем. В частности, для интересуюпщх нас в первую очередь полей GF(2) характеристики 2 сумма четного числа одинаковых слагаемых тождественно равна нулю, а нечетного числа - самому слагаемому

(см. гл.З). Поэтому для ПОЛЯ GF(2) из формулы (5.69) следует

( = О

где ф = int 0,5 (« - 1). Вторая производная в этом поле [вообще р-я в поле GF(p)] равна нулю. Полезны также следующие свойства формальной (как и обычной) производной:

[/(2)+ (г) и =/;(2)+;(2);

[/(2) (2)];=/; (2) (2)+/(2); (2). {5.щ

Из курса высшей алгебры [33] известна теорема о кратных корнях обычных алгебраических полиномов над числовым полем: если число

zi является n-кратным корнем полинома f (z) , то при п > 1 оно будет (п - 1)-кратным корнем полинома/ (г) ,а при «= 1 - не будет служить корнем для fz (z). Следовательно, если полиномы f(z) и fz (z) имеют общий делитель то у полинома/(г) есть кратные корни; более

того, каждый корень полинома tp(z) является кратным корнем полинома f(z). с некоторой коррекцией указанная теорема справедлива и для полиномов над конечным полем. Предположим вначале, что сам полиному (г) является некоторой степенью другого полинома: g(z) =

= f{z). Тогда

gz iz) = {{n))r-{z)f;{z).

(5.71)

Если n нацело делится на р, то формальная производная gz{z) тождественно равна нулю, в противном случае gx {z) содержит общий

с полиномом(г) множитель/" (г).

Предположим далее, что /(г) = {z - ZxYg(z). Воспользовавшись соотношениями (5.70) и (5.71), найдем

fUz) = ((«)) (2 ~ 20"-(2) + (2 - z.rg.iz). (5.72)

Если п кратно р, то первое слагаемое в соотношении (5.72) обра-

щается в нуль, т. е

f{z){z-zxrg,{z), п=]р,

где / - натуральное число. Следовательно, Zi является «-кратным корнем для/ (г).

Если же п нацело не делится на р, то ((«)) О и в формуле (5.72)

член (z - Zi)~ можно вьшести за скобки, т. е./г () имеет (« - 1)-кратный корень 2i.

Таким образом, для выявления отсутствия кратных корней у поли-мома/(2) над произвольным полем GF(p) можно использовать следующую процедуру:

1. Вычислить формальную производную/г (г).

2. Если окажется, что fz (z) = О, естественно, при f{z) Ф const, то все корни полинома f(z) кратные и их кратность пропорциональнар.

3. Если fz {z) Ф О, то найти т? - наибольший общий делитель (ПОД) для/(2) nfziz).

4. При п = const у полинома f{z) нет кратных корней; если же НОД - некоторая функция 17(2) от 2, то полином/(2) имеет кратные корни.

Зададимся, к примеру, следующими полиномами над полем GF(2):

а)/(г) = (2 + 1)2=2 + 1;

в) /(2) = (2 + 1) (2 + 2) (2 + 3) = 7 + 6Z +32+32+72+4

Найдем формальные производные по z: а)/; (2) =0;

б)/;(2) =2+1;

в)/; (2) =2* +32 +7.

Вычислим НОД 1/(2) для полиномов /(2) и/2 (2) =0и произведем исследование полинома/(2) на кратные корни:

а) так как (2) = О при/(2) const, то/(2) имеет кратные корни (четной кратности);

б) 1/(2) = 2 + 1 =/2 (2) const, т. е./(2) нацело делится nafi (2) , следовательно,/(2) имеет трехкратный корень 2 = 1;

в)/-(2) = rest (/(2) :/z()] = 7(2 + 1); так как/-(2) делит/2 (2) без остатка (rest = 0), то 17(2) = /"(2) = 7(2 + 1); таким образом, 2=1 - трехкратный корень/(2).

С другой стороны, для полинома (5.64) над полем GF(2) получим

/(О = /5 + 17/2 + 23f + 30; (О = 5/* + 23.

Воспользовавшись алгоритмом Евклида, найдем, что НОД 17(2) = = const; следовательно, исходный полином (5.64), GF(2), кратных корней не имеет.

Подсчет числа корней степенного уравнения, принадлежащих заданному полю. Для теории помехоустойчивого кодирования значение имеют только полиномы, у которых число различных корней в данном поле GF() равно степени уравнения. Если зто не так, то число ошибок в кодовом слове превышает допустимое. Оказьюается, можно найти число корней степенного уравнения /(х) = О, не решая его. Известно [35, 36], что произведение всех нормированных линейных полиномов X - 0, где /3 - разные ненулевые элементы поля GF(), дает двучлен

х- - 1,т.е.

х?-! ~ 1 = П (х Р), 0ФО.

Следовательно, полином (лг) = НОД \/(х),х~ - 1] равен произведению тех двучленов (х - /3) , которые соответствуют разным корням уравнения/(х) = О, Поэтому число корней полинома/(лг) в данном поле GF() равно степени полинома (х). Если окажется, что(х) =

= f (х) у т. е. х~ - 1 нацело делится на/(х) , то все корни заданного уравнения/(х) = О простые и лежат в поле GF(), Пример 5.16, Пусть дано уравнение

/(х) х*+5х+8x2 + 13jc+9, GF(2*).