Главная Помехоустойчивое кодирование Можно убедиться,что (х* +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) орбитальным методом
векторами. Таким образом, исходный полином (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 |