Главная ->  Вычислительные алгоритмы 

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

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

+ dt

+ d,

rfj

+ d.

- d.

+ d,

+ (2

+ 3

= rfo

- d.

= d,

- d,

= d:

- d.

- dj

- d,

- t2

= t>

+ f,

= Ia

- t.

0,

+ o.

- Oo

+ D,

- D,

= Oi

- D,

- o.

- Oi

- 0.

+ O,

Г. . 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 вещественных сложений

-1 -1

-1 -1

- 1

-1 -1

-1 -1

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

1 0

0 -1

1 0

-1 2

] 0

1 -1

1 0

0 -1

-1 -

-1 2

[ 1

1 -1

1 -1

-1 -

, 1

1 0 1

-1 3

-1 0-1

Г9С.

; 1

1 1

-1 -2

-1 1

0 1

1 -1

-1 -1

0 0

>

1 -2

1 1

-2 1

1 1

-1 -1

2 2

-4 -1

2 2

-2 1

1 -2

2 2

-1 -4

-1 2

1 1

-2 -2

2 -1

-4 -1

-1 0

1 1

0 0

0 1

1 0

-1 0

1- 0

-1 1

30,.

0 1

-1 0

. 1 >

-2 1



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 вещественных умножении, и вещественных сложений

Э - 1

0 -

1 I

0 -

I -

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,

(о =

hi +

2r/7

To =

Ь. + bi

Ti =

ь, + *,

Ucose + cos2e + cos 39) -

1 Ti .

bi - b,

Гз -

1(2 cos 9 - cos 29 - cos 39)

Гз .

-bi - ь

I (cos 9 - 2 cos 29 -f cos 39)

Ti =

b, + bi

hcose + cos 29 - 2 cds 39)

Ti =

b, - b,

Г. =

Usiti в + sin 29 - sin 39)

-bi - b

ff4 =

i (2 sin 9 - sin 29 + sin 39)

To + Г,

0! =

3(sin 9 - 2 sin 29 - sin 39)

Г, =

Го -1- г,

fl] =

1. ~

ilsine + sin 29 + 2 sin 39)

Г, =

Го + Ti

/7 =

Го -

Ti + bi

Оз =

(i -

Ги =

T, + *,

0. -

/1 -

Г, =

Г. + b,

fl. -

f3 -

Уо =

ol =

is Л-

у, =

Г, - ;Ti.

fl, =

Ii +

Vi =

Г, - jT

flo =

№3 +

Vi =

T, + JT,

Vi =

Г, - jT..

1з =

T, + JT.,

У, -

T, + jT,o

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

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



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