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



таблица 4.8

Число операций в двух вариантах вычисления циклической свертки длины п

Длина свертки п

Вариант I: Умн

Вариант П: Умн

< 100

< 130

Таким образом, согласно формуле (4.40) для свертки двух векторов достаточно теплицев, т. е. правый, циркулянт, верхняя строка в котором совпадает с одним из векторов, умножить на второй вектор, трансформированный так: его старшая компонента неподвижна, а остальные расположены в обратном порядке.

использование соотношений, представленных на риа,4-22, приводит j< класси-ческому варианту вычисления свертки, требующему 2л, - п операций, из них и умножений и п - п сложений. Так как рассматриваются двоичные векторы, то операция умножения (конъюнкция) схемно реализуется даже проще, чем сумма по модулю 2. В этом случае данный метод является, по-видимому, простейшим и к тому же регулярным (во всяком случае при простых числах п он требует меньшего суммарного числа операций).

Если же умножаются недвоичные векторы с компонентами, принадлежащими Некоторому полю, то на выбор метода существенно влияет способ представления элементов этого поля: в прямоугольных координатах проще выполняется сложение, а в полярных - умножение. Для минимизации числа умножений разработаны специальные алгоритмы [2, 20, 37, 39]. Так, алгоритм Винограда для w = 3

требует всего четыре умножения и 13 сложений. В этом случае вместо формул (4-40) используются следующие [2]:

т,=Д1+Д2; m2=ao+ai; ?Из=До+А2; «4 = Ао+1;

/i=/)i+/)2; hbo+bi; 1э~Ьо+Ь2\ U = bo+li;

kl = mi III т2 h; = гпз I3; k4= Ц;

fi~ кг +кз; Г2~к1+кз; 00 = 1+:4; Ci~r2+k4; C2~ri + ci.

В табл. 4.8 приведены количества операций (умножения Улей, сложения Сл и общее S) для двух вариантов вычисления сверток: I ~ классический; II -с минимизированным числом умножений. По общему числу операций вариант I предпочтительнее при простых числах п, а вариант II - при составных.



ГЛАВА ПЯТАЯ

УРАВНЕНИЯ НАД ПОЛЯМИ ГАЛУА

5.1. КВАДРАТНЫЕ УРАВНЕНИЯ

Приведение к каноническому виду. Пусть над некоторым полем задано квадратное уравнение

2 х + + = О, Л2ФО. (5.1)

Без потери общности вместо уравнения (5.1) можно рассматривать

уравнение

-Ах +5 =0,

(5.2)

тпе А =Ai/A2; В =0/2-

Если В = О (Ао - 0), то уравнение (5.2) имеет пару неравных корней, включая нулевой: х = О, JC2 = ~А, а если А =0 {А =0), то пару

равных корней: Xi = дгг = \fW.

Наибольший интерес представляет вариант АВ Ф 0. С помощью замены переменной х Az приведем уравнение (5.2) к каноническому виду:

2 +Z+/) =0,

(5.3)

где D =В/А = (Ao/A2)IAl

Уравнение (5.1) может быть представлено в виде (5.3) для произвольного поля. Нас интересуют квадратные уравнения над конечным полем характеристики 2, причем такие уравнения, которые не имеют кратных корней. Обычная "школьная" формула для корней квадратного уравнения над полем комплексных чисел в данном случае не подходит, потому что в знаменателе "школьной" формулы присутствует коэффициент 2 = 0 mod 2.

Использование нормального базиса. В работе [51] доказано следующее.

Утверждение 5.1. Квадратное уравнение (5.3), а следовательно, и уравнения (5.1), (5.2), над полем GF(2) имеет два корня z, z" G GF(2) тогда и только тогда, когда Tr(D) = О, где Tr(D) =

D + D + . .. + /) - след элемента Л; = 2-*.

Как показано в § 3.4, в любом поле характеристики 2 имеется нормальный базис 7» 7*» .. ., } с порождающим элементом 7. Произвольный элемент Z)£ GF(2 ) может быть представлен по нормальному базису в виде

7 - 1610



2 J. j. ..t5

a его след, согласно формуле (3.49), - в виде

Тг(/)) = Jo + -1 + • - • + -t?-!-

(5.4)

(5.5)

При Tr(Z)) = О пара корней z, z" уравнения (5.3) вычисляется В нормальном базисе по следующим формулам:

г = о / = о

где черта означает логическую операцию инверсии: z - 1 + z, z Е G (о, 1 } . В СВОЮ очередь, коэффициенты z находятся по коэффициентам с? разложения (5.5):

2о = 0; Zi = di\ Z2 = ci + 2; - • • ;

г - 1

г = 1

или рекуррентно

(5.6)

J = Z. -\-dj, / = 1, 2,. . . , г - 1; zo = 0. (5.7)

Таким образом, пара корней в указанном нормальном базисе записывается так:

- (2 i,z 2,...,zi,zo);

ч - - - - ч

(5.8)

Далее от нормального базиса {7, 7, 7*, . . . , 7} следует перейти к исходному степенному базису [а, а, а, .. , . Возвращаясь

к стай переменной х = Az = (А1/А2) z, находим корни х = Az\x" = = Az уравнений (5.1) и (5.2).

Рассмотрим несколько примеров.

Пример 5.1. Зададимся парой значений Xi,X2 Е GF(2*), я - а* + а + + 1, например: Xi = 5,Х2 = 8. Пользуясь табл. 3.5, составим выражение

(x + xi) (д: +2) =д:2 + (5 + 8)x + 5 • 8 = д:2 + 4x + 12, OF(2*).

Итак, пусть задано уравнение +4Х + 12= О, GF(24).

(5.9)

С ПОМОЩЬЮ подстановки х= 4z приведем уравнение (5.9) к каноническому виду:

z2 +2 +D = 0, D = 12/42 =6, GF(24). (5.10)

Используя табл. 3.] 6, запишем параметр D = 6 по примитивному



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.0439