426 Приложение А. Набор алгоритаов циклических сверток

Г. . s, + s

Г, . X, - J,. Ti = S, + Sii

T, = s - s,

r, = Sl + J Г, . So - Su

Г, = s - s, Г, = s + s, Г. . s, + s, Г, = s, - s,

r,. = Го - Ti

r = r. + r,

Г, = Ti + T,

T = T, + T,

r = Го + Г,

r = - Г, + Г,

r,. . r, + r,

r . - Г. + Ti St = Г. + r s, = Ги + T

s: = Г4 + Г;

s, . r + Г-s. . -r,i. + r

s. - -r. + Г.

sf = - Гм + Г. j. . - г. + Г,

йтГ ическая свертка; 19 вещественных умножений, 74 вещественных сложений

Приложсиие А. Набор алгоритмов цнклическик сверток

426 Приложение А. Набор алгоритмов циклических сверток

D, Ог = D, = D, = D, = D, = Д. = £), = Dt = =

Д>о = Dn = £),i = Dn = =

Д = 0,б =

Д,7 =

Du =

= rfo - rfi = rfi - rf, = rfi - rf, = rfi - rfi = Л - rf, = di - dl = dt + dl + dt = di + d, + d, = dl + di + dl = h + ti = ti + t, h + t, + I, = lo + t. = t, + I, = Dl - Di = lo - r.

= 9 -

Di - D4 = 3 Го -о s

г - > г

-Di, + Го - 4 D, + Ii - I, -Di, + D

и - I, ь - t, 0,6 + D

Ti Ti >T, T.

T, r,o Tii = Tn = Til = 7-,; = Tii Tib =

r =

Ti, =

r =

Tic =

s, =

Sl = S! = 54 = 55 = Sf =

s? =

Sl + Sl s4 + Si Si. + Sii

= n + Ti = Si + s, = S4 + Ss = Sn + S,i = -T, + s, = T, + Ti = Sio - n = S, + Ti + T, = T, + S + T, Т,- Ti+ Ti

ъ + T, + s,+ Ti

= Ti + Sil + Г, + Ti Tc- Ti+ Ti . = Sit - s = Sn - s So + Tit Sa - Ti, - 7- So + T Tii - Ti, + Tit Ti, - Tii + Ti, T - T,i + 7io

- Ti, + Ti,

- Ti, + Ti,

- Ti, + Tic r.o + 7- Tii + Ti, Til + Ti,

приложение Б

НАБОР МАЛЫХ БПФ-АЛГОРИТМОВ ВИНОГРАДА

Ниже приводятся малые БПФ-алгоритмы Винограда для длин п = 2,3, 4, 5, 7, 8, 9 и 16. Алгоритмы записываются в виде матричного равенства

V = CBAv.

Матрица В является диагональной и выписываются только ее диагональные элементы. Матрицы А и С выписываются полностью. Кроме того, в обозначениях

а = Av, b = Ва, V = СЬ

выписываются последовательности сложений, которыми можно заменить умножения на матрицы А и В. Тривиальные сложения (сложения чисто вещественных или чисто мнимых чисел) отмечены звездочкой, но включены в полное число сложений. Они перестают быть тривиальными, если входные данные являются комплексными. Во всех алгоритмах мнимая единица / из диагональной матрицы передвинута в матрицу постсложений С.

2-точечное преобразование Фурье; О (2) вещественных умножений, 2 вещественных сложения

во = Уо + I а, = Но - У!

К = So у, = ь,

3-точечное преобразование Фурье; 2 (3) вещественных умножения, 6 вещественных сложений

1 1 I I

I -1

1 -J 1 I.

Jl я и, + 1

а, = V, - VI

во = Оо + й!

> - 2i/3

0 - 1

1 = COS в - I

! - sin в

Vo = 60 Го = *. + *, И, = т. - jb: У,-П* Jb:

430 Приложение Б. Набор малых БПФ-алгоритмов Випограда же, Тц :Г?Ге- 0(4)вещесгее них умно-1

Приложение Б. Набор малых БПФ-алгоритмов Винограда

7-точечное преобразование Фурье; 8 (9) вещественных умножений, 36 вещественных сложений

1 = Щ ~ ui

Oj = ti, ~ сз 0=1-0+1.=

л = 1-1 + uj

ffo = /о + /,

во . 1

в, - 1

в, . 1 8, = I

1 о о

0 0 1-0 1 О О О 1

К. . (.0

У,Ь,- jb

у, = Ь,

у, - bi jb

женйГТ? ° рГсР ° *УР 5 вещественных умножении, и вещественных сложений

0 I .

0 0 . Lo

a. = Vi ~ vi

1 = 111 - V.

= lo + I, а = o - (, Ol = a. + uj aa = + a.

1 0

0 -1.

в = 2t/5 Bo = 1

B, = l(cos 9 + cos 26) ~ 1

2 = 2 (COS в - COS29)

B, = sin в

Bt = sin e + sin 29

B, = sin 29 - sin в

-/ 0 -y -1 у 0 у 1 J -у о

Уа = bo

То = *о + *,

Т: = bi - Ь,

1 = Ь, * 6, г, = Г + Ь, Т.= Т,~ Ь, = Т,- jT,

У п~ щ

у. = т. * JT,

) Тривиальные сложения

Тривиальные сложения