Главная Помехоустойчивое кодирование



Можно убедиться,что (х* +1) =Пх)а{х),

где а{х) =х + 5х*° + Пх + 13х +4х* + + + + 14х + + 12х + 8, GF(2*),

т. е. /(х) делит х + 1 и, следовательно, все корни уравнения f(x) = О лежат в поле GF(2*).

Факторизация полинома на основе орбитального метода. При исследовании уравнений второго - пятого порядка было установлено, что их корни могут быть сгруппированы на основе орбитальных представлений. В частности, для поля GF(2 ) было показано, что если zi - корень

- корень соответствующего уравне-

одного из уравнений "а", то z\ ния "б":

а) корень Zx 2 +2 +£) = О

2+2 О

2 + 2 +£i2 + £2 = О 2 +JU2 + 1 = 0

б) корень zl

2 +2 + £) =0; 2+2 +£ =0; z" z ElztEl

2 +ju2 + v

в общем случае справедлива следующая теорема орбит [54]. Пусть заданы два полинома над полем GF {q = 2 ):

f2iz)

(5.73) (5.74)

и полином fl (2) имеет корень 2i, тогда zj - корень полинома/2 (2); наоборот, если Zi - корень полинома /2 (2), то \fz - корень fx (2).

Элемент Zi является корнем полинома (5.73) тогда и только тогда, когда 2 - корень полинома

. .Ла\г \а\, GF(2),

(5.75)

- 1

/2),

где X = 2,/ = 1, 2,.. .,/•- 1,т.е. X = 2,4,..., 1» (тУ = 2

причем/ (2) =/(2).

Полином (5.75) f-(z) назьшается орбитальным, соответствующим полиному (5.73) fl (2).

Таким образом, полиномы fx (2) и fiz) при некоторых X могут иметь общие корни и, следовательно, содержать общие делители. Применив алгоритм Евклида, можно вьщелить наибольший общий делитель указанных полиномов 17(2) , а значит разбить fi (2) на две части: общую

8-1610



и взаимно простую с f\{z). Подобный метод выявления корней полиномов назовем орбитальным.

В работе [54] отмечается: чем выше степень полинома/i (2), тем больше шансов на то, чтобы он имел общие корни с одним из своих орбитальных полиномов. Для примера зададимся полиномом

fl (z) = 2 + 192* + 32 + 192 + 292 + 32 +

+ 2б2 + 13, GF(2).

(5.76)

Найдем его орбитальный полином для X = 2 типа (5.74): /2(2) =2 +б2* +5z +62 +262 +52 +202 + 25, GF(2). (5.77)

Воспользовавшись алгоритмом Евклида, найдем НОД для полиномов (5.76) и (5.77): 77(2) = 232 + 23 = 23(z + 1). Расчеты сведены в табл. 5.10, в которой полиномы заменены соответствующими им

Таблица 5J0

Выявление корней полинома (5.76) орбитальным методом

(Ь 19,

(1, 6,

= 23 (1.1), zx = 1

-

= 2 (1,22). 22 =22

= 9 . (1,14).z3=14



векторами. Таким образом, исходный полином (5.76) делится на двучлен г + 1, т. е. имеет корейь Zi = 1.

Так как элемент 1 образует самостоятельный циклокласс, то этот же корень Z\ - \ будет и у любого другого орбитального полинома, соответствующего fy (z). Орбита зтого корня новых значений не содержит: Zl = Z для любого X. Поэтому без ущерба для вычислительного процесса указанный корень можно исключить, т.е. полином (5.76) - разделить на Zi + 1. В результате получим полином

(г) fxiz) : (2 + 1) =2* +22 +202+62 3 + 132 +

+ 272 + 13,

которому соответствуют орбитальные полиномы g(z) =2* +52 + 15z +2l2 +7z + 122 + 18

8 (2) = 2* + 92 + 292* + 102 + 13z +232 +4

(5.78)

(5.79) (5.80)

gxbiz) =z* + 172 +262* + 192 +25z + 142 + 7. (5.81)

Как видно из расчетов, представленных в табл. 5.10, пары полиномов (5.78) и (5.79), (5.78) и (5.80) имеют следующие наибольшие общие делители:

НОД [gx{z),g{z)] =22 +23 = 2(2 + 22); НОД [gx{)>Sfi{z)] =92 +22 = 9(2 + 14).

Следовательно, полином (5.78), а также заданный полином (5.76) имеют корни 22 = 22, 2з = 14. Можно показать, что использование полинома (5.81) не дает новых корней, так как НОД [g{z) , gк, {z)] = - const.

Разделив полином (5.78) на произведение (z + 22) (z + 14) , получим частное

2 +202 + 292 +2z + 10.

(5.82)

Итак, заданный полином (5.76) факторизуется следующим об-р азо м:

z + 19z* + 3z + 192* + 29 + 3z + 26z + 13 =

= (2 + 1) (z + 22) (z + 14) (z + 20z + 29z + 2z + 10).

Полином (5.82) имеет множество корней (5,6,7,26} е GF(2), которые могут быть найдены одним из методов, изложенных в § 5,3. Заметим также, что алгоритм Евклида может быть использован в мощд-фицированном виде без операций деления (см. § 2.3).

Воспользуемся понятием циклокласса (см. § 3.4) и проанализируем возможность изложенного вьппе метода. Он позволяет выявлять корни



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 [74] 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.0236