Un algorithme de transformation de Fourier rapide à double base

pp. 481-494 481

Un algorithme de transformation de Fourier rapide double base

Pierre D U H A M E L *

Analyse

Cet article ddcrit un algorithme de transformation de Fourier rapide proposd rdcemment, qui prdsente des avantages en complexitd de calcul, occupation mdmoire et rdgularitd de structure. Aprds avoir bridve- ment ddcrit l'algorithme d double base dans le cas de signaux complexes, l'application aux cas de signaux rJels et rdels symdtriques est examinde, ainsi que le lien avec un algorithme optimal quant au nombre de multiplications complexes non triviales.

Mots cl6s : Transformation Fourier discr6te, Transfor- mation. Fourier. rapide, Alg.orithme,. Complexit6. algorithme, Algorlthme optimal, Op6ratlon artthm6tlque, Nombre r6el, Nombre complexe.

Sommaire

I. Introduction. II. L'algorithme d base double.

III. L'algorithme d base double appliqud d des donndes complexes.

IV. L'algorithme d base double appliqud d des donndes rdelles.

V. L'algorithme d base double appliqud d des donndes rdelles et symdtriques.

VI. Ddcomposition d'une transformation de Fourier discrbte de longueur 2" en produits de polyn6mes.

VII. Conclusion.

Annexe. Bibliographie (25 rdf.).

A << SPLIT-RADIX )) FAST FOURIER TRANSFORM

Abstract

A detailed description of a recent algorithm for the fast computation of the discrete Fourier transform is presented. This algorithm has some advantages when considering computational complexity, (< in place)) computation, and regularity of its implementation. After briefly recalling the split-radix algorithm in the case of complex data, we show how it can be adapted to real and real symmetrical data. Finally, we enlight the relationship between split-radix algorithm, and an algorithm with minimum number of non-trivial complex multiplication.

Key words : Discrete Fourier transformation, Fast Fourier transformation, Algorithm, Algorithm complexity, Optimal algorithm, Arithmetic operation, Real number, Complex number.

I. INTRODUCTION

Depuis l'article de Cooley-Tuckey [1], de nombreux travaux ont 6t6 effectu6s pour obtenir les algorithmes les plus rapides possibles pour le calcul de la trans- form6e de Fourier discr&e.

Les premiers propos6s, dits /l base 2, 4, ou mSme 8, ont 6t6 des extensions directes de l'algorithme initial, /t l'exception notable de [12] qui, bien que m6connu jusqu'/t une p6riode tr6s r6cente, pr6sentait une complexit6 de calcul plus faible que t o u s l e s algorithmes pr6sent6s jusqu'alors. En fait, cet algorithme demandait un nombre de multiplications et d'additions identique/L celui des meilleurs algorithmes r6cemment propos6s, mais avec une structure tr6s peu r6guli6re, compliquant/t la fois sa programmation et une 6ventuelle r6alisation mat6rielle.

Puis, les travaux de Winograd sur la complexit6 des calculs, conjointement /t diff6rents travaux pr6- curseurs ont mis en 6vidence l'int6rSt d'algorithmes

* CNET/PAB/RPE, 38-40, rue du G6n6ral Leclerc, 92131 Issy-les-Moulineaux.

1/14 ANN. T~L~CO~Lqq., 40, n ~ 9-10, 1985

482 P. D U H A M E L . - A L G O R I T H M E DE T R A N S F O R M A T I O N DE F O U R I E R R A P I D E

rapides dont les longueurs, cette fois-ci, n'6taient plus des puissances de 2, mais des produits de petites longueurs premi6res entre elles (choisies parmi 2, 3, 4, 5, 7, 8, 9, 16, pour les plus courantes). Deux types d'algorithmes ont r6sult6 de ces travaux : l'algorithme dit de Winograd [10], et l'algorithme d i ten facteurs premiers [8].

Parall61ement, les algorithmes rapides portant sur des longueurs N = 2" ont 6t6 am61ior~s par l'introduction d'une s6rie d'algorithmes ~ coefficients r6els [2, 3, 4] qui pr6sentaient la m~me complexit6 multiplicative que celui de Yavne [12], c'est-~-dire la plus faible connue ~ ce jour, avec une structure plus r6guli6re, mais 6galement plus d'additions (Tabl. I et II).

Cependant, parmi tous ees algorithmes, les plus utilis6s restaient ceux de la premi6re g6nfration, sp6cialement eeux ~ base 2 et ~ base 4, ~ cause de leur structure simple (en << papillon >>), et de la possibilit6 de les programmer ~ en place >>, m~me s'ils apparaissaient plus cofiteux en terme de complexit6 arithm6tique que les algorithmes de Winograd et en facteurs premiers. Des essais de programmes optimis6s de mani6re comparable ont m~me montr6 que la base 4 semblait encore ~tre le plus rapide.

Le champ de recherches sur les transform6es de Fourier rapides (TFR) monodimensionnelles semblait presque clos, et l'on n'attendait plus d'am61ioration sensible, quand trois nouveaux algorithmes [11, 13, 15] furent propos6s, atteignant la m~me complexit6 multiplicative et additive que celui de Yavne [12], mais avec une structure beaucoup plus simple.

Cet article d6crit l'un de ces algorithmes : la a'VR double base [11] qui semble cumuler les avantages

des m6thodes classiques et des m6thodes r6centes :

- - un nombre minimal ~ la fois de multiplications et d'additions, parmi les algorithmes connus,

- - l a m~me r6gularit6 de programmation (ou de r6alisation) que les algorithmes b. base 4,

- - la m~me souplesse d'emploi que les algorithmes base 2 (utilisables pour toutes les puissances de 2 :

N = 2"),

- - pas de r6arrangement des donn6es ~ l'int6rieur de l'algorithme,

possibilit6 de programmation en place pour des donn6es r6elles ou r6elles sym6triques, avec une complexit6 arithm6tique r6duite (la plus faible parmi les algorithmes connus, ex-aequo avec les plus r6cents),

- - bon conditionnement num6rique.

Dans cet article, nous pr6sentons tout d'abord le principe de l'algorithme ~ base double dans le cas de signaux complexes, et nous comparons sa comple- xit6 de ealcul ~t celle d'autres algorithmes.

Deux variantes de structure sont pr6sent6es, selon que l'on recherche la rapidit6 d'ex6cution, ou une plus grande r6gularit6 de l'algorithme.

Puis, nous traitons l'application de cet algorithme des signaux r6els et r6els sym6triques.

Enfin, nous faisons le lien entre cet algorithme et un algorithme bas6 sur une d6composition de la transformation de Fourier discr6te en produits de polyn6mes. La comparaison de leurs complexit6s multiplicatives (ici le hombre de multiplications complexes non triviales) semble indiquer que l'algorithme ~ base double est optimal quant au hombre de multiplications jusqu'~ une longueur 64.

I I . L ' A L G O R I T H M E A B A S E D O U B L E

Cet algorithme trouve son origine dans une observation tr6s simple :

Le graphe de fluenee d'un algorithme ~ base 2 et entrelacement temporel peut se transformer de mani6re 6vidente en graphe de fluence d'un algorithme

base 4 uniquement en changeant les exposants de la racine de l'unit6 servant de coefficients multiplicateurs (les <~ twiddle factors>>). Ce faisant, il apparait assez vite que, h chaque 6tage de l'algorithme, une base 4 est plus int6ressante pour les termes impairs, et une base 2 pour les termes pairs de la T F D .

L'algorithme h racine double est donc bas6 sur la d6composition suivante :

N - 1

(1) xk = Y. x. w~ k, k=O

la TFD ~ calculer (autre notation : Xk = TFD(k, N, x,). Un 6tage de l'algorithme ~ entrelaeement temporel d6compose (1) en :

N I 2 - 1

X2k = E (X. + Xn+,,12 ) W~ "k, n = O

N I 4 - - 1

(2) X4k+a = E [(x, - - x,+u/2) -b n~O

j ( x . + , , 4 - x.+3,,4)1 W~ W~ "~, N I 4 - 1

X'~k+3 = E [ ( X . - - X n + , , 2 ) - - . = o

i (x.+N/~ - - x.+3N/~)] W]" W~ "~.

Le premier 6rage d'un algorithme ~ base double et entrelacement temporel remplace done le ealcul d'une TFD de longueur N par celui d'une TFD de longueur moiti6, et deux TFD de longueur N]4, au prix de (N]2 - - 4) multiplications complexes g6n6- rales (3 multiplications et 3 additions r6elles) et de 2 multiplications par ~/1-(2 multiplications et 2 additions r6elles).

On obtient l'algorithme eomplet par application successive de cette d6composition, jusqu'au dernier 6rage, o~h quelques <~ papillons >> usuels ~t base 2 sont

ANN. TI~LI~COMMUN., 40, n ~ 9-10, 1985 2/14

483

1

2

)

&

5

6 ./

O

9

I0

11

12

13

It.

15

16

1"/

18

19

2O

21

22

23

21.

25

26

2")

20

29

30

31

FIG. 1. - - Graphe d'un algorithme h double base et entrelacement temporel de longueur 32.

Length 32 decimation in frequency split-radix algorithm.

P. DUHAMEL. - ALGORITHME DE TRANSFORMATION DE FOURIER RAPIDE

n6cessaires (le graphe d'une TFR ~t base double de longueur 32 est donn6 en figure 1).

I1 est 6galement possible de trouver un algorithme base double et entrelacement fr6quentiel par utilisa-

tion de la d6composition suivante :

lq12 - 1 N I4. - 1 (3) Xk = ~ x2.W~ "k q- W; Z x . .+ lW~ "k q-

n=O n=O ~14--- 1

w3k ~.~ X4n+ 3 W~q nk, n=0

que l 'on peut s6parer en quatre cas pour faire appa- raltre la cellule 616mentaire de calcul :

(4) Xk = TFD(k, N]2, (x2.)) + WIVED(k, 3[/4, (X..+I})-F- WaN k TFD(k, N/4, (x..+a)),

Xt~+NI4 = TFD(k -1- N / 4 , N / 2 , {x2.}) +

j W~ TFD(k, U/4, {x4. +1 }) - - J W~ k TED(k, NI4, {x.. + 3}),

Xk+st2 = TFD(k, N/2, {X2n})- Wg TFD(k, N/4, {x4.+ 1 ) ) - Wu 3k TFD(k, N]4, (x..+a)),

Xk+3NI4 = TFD(k -~- N / 4 , N / 2 , ( x 2 . ) ) - j W ~ TFD(k, U/4, (x4.+ 1)) -F-J W~ k TFD(k, U/4, {x..+ a)).

III. L 'ALGORITHME A BASE DOUBLE APPLIQUI~ A DES DONNI~ES COMPLEXES

Dans le cas de l'entrelacement temporel, comme dans celui de l'entrelacement fr6quentiel, l'algorithme

base double est une combinaison de d6composi- tions ~t bases 2 et 4 (localement, h chaque &ape). Intuitivement, on pourrait se dire que la complexit6 de calcul r6sultante doit ~tre interm6diaire entre les complexit6s des algorithmes ~t bases 2 et 4. En fait, nous allons voir maintenant que les hombres de multiplications et d'additions intervenant dans cet algorithme sont plus faibles que ceux des deux algorithmes initiaux.

IH.1. Complexit6 de caleui.

Soit M~ (resp. A, ~) le nombre de multiplications (resp. additions) r6elles non triviales n6cessaires au calcul d'une TFD complexe par l'algorithme ~ double base.

3/14 ANN. TI~LI~COMMUN., 40 , n ~ 9-10, 1985

484 P. DUHAMEL. - ALGORITHME DE TRANSFORMATION DE FOURIER RAPIDE

D'apr6s les 6quations (2) ou (4), on a :

c 2"- 1 (5) M. ~ = M.C_x + 2 M . _ 2 + 3 • - - 8 ,

et, avec M~ = 0, M~ = 0, il vient :

(6) M~ = 2"(n - - 3) + 4.

D'autre part, si l 'on oublie pour un instant les additions n6cessaires ~t l'6valuation des produits complexes, le nombre restant d'additions r6elles peut facilement ~tre 6valu6 h 2 • 2 n+l puisque, h chacun des n 6tages, un nouveau point est g6n6r6 par une addition complexe. Ainsi, comme le nombre d'additions r6elles n6cessaires au calcul des produits complexes est 6gal au nombre de multiplications r6elles :

(7) A ~ = n 2 " + ~ + M ~ . ,

(8) A~ = 3 • 2 " ( n - - 1 ) + 4 .

m.2 . Comparaison avec d'autres algorithmes.

Les quantit6s correspondant aux nombres de multiplications et d'additions intervenant dans un algorithme h double base sont compar6es dans les tableaux

I e t II avec les complexit6s arithm&iques d'algorithmes classiques (~ base 2, 4, 8, ~t facteurs r6els) et d'algorithmes plus r6cents, par Wang [14], Vetterli-Nuss- baumer [13] et Martens [15].

L'observation de ces tables montre que l'algorithme double base demande le nombre le plus faible la fois de multiplications et d'additions, ex-aequo

avec les algorithmes FFCT (fast Fourier cosine transform) [13] et RCFA (recursive cyclotomic factorization algorithm) [15] (le nombre d'op6rations donn6 en [15] a 6t6 cor r i# dans les tableaux pour tenir compte du fait qu'une multiplication par ~ / ] -ne demande que 2 multiplications et 2 additions r&lles).

En effet, si l 'on compare l'algorithme h base double aux algorithmes << classiques >) (base 2, 4, 8, et mSme base variable [6]), on peut facilement se rendre compte que tous les algorithmes en cause ont exactement le m~me nombre de coefficients multiplicateurs, si l 'on cumule le nombre de multiplications par j, ~/1-, Wn k . On peut done eonsid6rer que ce nouvel algorithme appartient ~ la m~me classe d'algorithmes classiques, d'autant plus que, on le verra plus loin, les structures de programmation (ou r6alisation) sont semblables. L'avantage essentiel de cet algorithme par rapport aux autres r6side

N

TABL. I. ~ Nombre de multiplications r~elles intervenant

Base 2

Number o f non-trivial multi ~lications to

Base 8 Base 4 Coefficient

r6el [2, 3, 4]

20

dans le calcul d 'une rvo complexe de longueur N.

compute a length N complex DFr.

Wang [141 FFCT [13]

20 i -

R C F A [15]

20 20

Base double

20 16 24 20

32 88 68 68 68 68 68

64 264 208 204 196 204 196 196 196

128 712 516 564 516 516 516

1 284

3 076

7 172

16 388

1 800

4 360

256 1 468

3 652

8 780

20 564

1 392

7 856

1 284

3 076

7 172

16 388

512 3 204

1 284

3 076

7 172

16 388

1 024

2 048

10 248

1 284 m .

3 076

7 172

16 388

TABL. II. - - Nombre d'additions r6elles intervenant dans le calcul d 'une TrO complexe de longueur N.

Number of real additions to compute a length N complex ro t .

N

16

Base 2

152

Base 4

148

Base 8 Rader

Brenner [2]

148

424

Wang [14]

148

388

FFCT [13]

148

388

RCFA [15]

148

388

Base double

148

388 32 408

64 1 032 976 972 1 104 972 964 964 964

128 2 504 2 720 2 356 2 308 2 308 2 308

256 5 896 5 488 6 464 5 564 5 380 5 380 5 380

512 12 868

29 260

65 620

12 420 13 566

30 728

12 292

27 652

61 444

1 024

14 976

34 048

12 292

27 652

61 444 76 288 2 048

28 336

12 292

27 652

61 444

ANN. T~L~COMMON., 40, n ~ 9-10, 1985 4114

P. DUHAMEL. - ALGORITItME DE TRANSFORMATION DE FOURIER RAPIDE 485

dans le fait qu'il maximise le nombre de multiplications par j = ~ / - - 1.

Si l 'on compare cet algorithme aux autres algorithmes r6cents, on se rend compte que l'algorithme de Wang [14] est moins int6ressant du point de vue de la complexit6 de calcul. En ce qui concerne les algorithmes qui demandent le m~me nombre de multiplications et d'additions, l 'algorithme de Vetterli- Nussbaumer [13] pr6sente une structure moins r6gu- li6re, faisant intervenir des r6arrangements des don- n6es ~ chaque 6tape de calcul. Quant ~t l 'algorithme de Martens [15], il s'agit en fait exactement d 'un algorithme ~ base double et entrelacement temporel. L'approche pr6sent6e ici a cependant deux avantages :

�9 Une meilleure compr6hension de ce que devrait &re la structure 616mentaire de calcul, permettant ainsi de r6duire le nombre d'appels m6moire par rapport ~t la pr6sentation qui a conduit h RCFA.

�9 La possibilit6 d'6tudier les deux types d'algorithmes h entrelacement fr6quentiel et temporel, qui ne sont plus 6quivalents au niveau de la r6gularit6 de structure pour des signaux r6els ou r6els sym6triques.

IH.3. Structme dans le cas de signaux complexes.

L'utilisation de la d6composition donn6e en (2) conduit naturellement ~ u n algorithme ~ sur place >), obtenu par l'utilisation r6p6titive de la structure 616mentaire de calcul donn6e en figure 2 que l 'on appelle ~t papillon )) ; par extension du terme habituellement utilis6 pour les algorithmes ~ base 2.

xo ~ / xo+x2

" " ,X ,

FIG. 2. - - Le ~< papillon ~ 616mentaire utilis6 dans l'algorithme ~ base double et entrelacement temporel.

The ~ butterfly >> used in the decimation-in-frequency split-radix algorithm.

I1 est dgalement facile de voir que le nombre minimal d'op6rations r6elles est obtenu ~ l'aide de seulement 4 types de << papillon>> diffdrents : le cas gdndral (6 multiplications rdelles), donn6 en figure 2, plus deux cas particuliers : k = 0 (pas de multiplication) et k = N]8 (4 multiplications r6eUes). Le quatri6me type de papillon est celui habituellement utilisd dans l 'algorithme ~i base 2 (sans multiplication) pour calculer des TFR de longueur 2.

Remarquons que l'utilisation du troisi6me papillon complexe (k = N[8) ne fait gagner que peu d'op6- rations :

113 (2 n - - ( - - 1) n) - - 1 multiplications et additions rdelles pour une transform6e de longueur 2", dont la moiti6 (~l une unitd pr6s) darts l 'avant-dernier &age.

C'est pourquoi dans le programme FORTRAN donnd en annexe I, nous avons choisi, pour des raisons de facilitd de programmation (et donc de compacitd du programme) de programmer explicite- ment les deux derniers 6tages ; ce qui permet en plus de rdduire le nombre d'appels mdmoire en y incluant les papillons de longueur 2. Ainsi, l 'avant-dernier dtage transforme les TFD de 8 points en TFD de 4 points, qui seront calculdes dans le dernier dtage, et calcule les 4 autres sorties par une transformation impaire. Le dernier &age est constitu6 de transformations de 4 points compl6tes.

De plus, afin d'obtenir une vitesse d'exdcution maximale, les adresses de ddbut de bloc sont prd- calcul6es sdpar6ment, en mSme temps que les constantes multiplicatives.

Le calcul d 'une TFR de 1 024 points par l'inter- m6diaire de ce programme prend 92,2 ms, contre 100,3 ms pour le m~me calcul par le programme compact ~l racine 4 de Morris [21] (moyennes sur 200 calculs sur un Honeywell-Bull DPS 8).

I1 peut ~tre int6ressant de comprendre off se situent les gains de vitesses observ6s. A cet effet, une estima- tion du nombre d'op6rations 616mentaires portant sur les nombres flottants (addition, multiplication, chargement, 6criture m6moire) a 6t6 effectu6 (cf, Tabl. III). On se rend alors compte que l 'algorithme

base double demande moins d'op6rations que l'algorithme ~t base 4 quel que soit le type d'op6ra- tion consid6r6.

TABL. III. - - Nombre d'op6rations flottantes intervenant dans une TFD de longueur 1024 (estimations bas6es sur l'assem- bleur g6n6r6 par le compilateur FORTRAN d'un Honeywell-Bull

DPS 8).

Number of floating point operations in a 1024-point FFT (estimations based on the assemblor generated by the FORTRAN compiler

on a Honeywell-Bull Des 8).

fld fstr fad fsub fmp

FFT 4 Base double

22 884 28 506 19 120 9 386 8 026

21 280 27 652 18 749 9 073 7 342

Pour d'autres applications que la programmation de TFR sur gros calculateur (par exemple r6alisation mat6rielle, ou n6cessit6 de r6duire soit l 'occupation m6moire, soit les pr6-calculs), il peut &re utile de disposer d 'un algorithme encore plus r6gulier. On peut obtenir un tel algorithme en permutant les sorties de la cellule de calcul 616mentaire, comme indiqu6 en figure 3.

5/14 ANN. TI~L~COMMUN., 40, n ~ 9-10, 1985

486 P. D U H A M E L . - A L G O R I T H M E DE T R A N S F O R M A T I O N D E F O U R I E R R A P I D E

Xo

X2

x~

FIG. 3. -- << Papillon >> A sorties permut6es permettant d'obtenir un algorithme plus r6gulier.

<< Butterfly ~> with permuted outputs for a more regular split-radix algorithm.

k w~ ((xo- x~) +l(x, -x~)) w~,

Xo+X2

Xl + ~

w~ ((Xo-x~)+j(x,-x~)) w~'

Dans ce cas, le diagramme de la TFR h double base de longueur 32 de la figure 1 se transforme en celui de la figure 4, ofa les adresses des d6buts de bloc de chaque &ape apparaissent de mani6re p6riodique, permettant ainsi une programmation FORTRAN simple ~ 3 boucles imbriqu6es comme dans le cas des algorithmes classiques.

Cependant, cette permutation pr6sente deux incon- v6nients :

- - l e s 6chantillons de sortie de l'algorithme ne sont plus dans un ordre correspondant h l'inversion de la repr6sentation binaire des indices, comme dans les algorithmes habituels, et l 'ordre obtenu ne permet plus une remise en ordre naturelle dans le m~me vecteur ;

- - l'algorithme obtenu demande plus de lectures/ 6critures en m6moire (2 lectures et 2 6critures suppl6- mentaires par bloc 616mentaire de calcul).

Effectivement, on peut constater que le programme r6sultant est plus lent (96,7 ms pour une TFR de longueur 1 024, dans les m~mes conditions que pr6- c6demment). N6anmoins, la r6gularit6 du diagramme r6sultant peut ~tre int6ressante darts le cas d'une r6alisation mat6rielle.

Dans la suite de cet article, comme nous d6sirons &ablir des algorithmes de TFR permettant des calculs << en place >> pour des signaux r6els, nous aurons besoin d'une repr6sentation sch6matique de la progression de l'algorithme dans les diff6rentes 6tapes, de la signification des r6sultats interm6diaires, et de l'endroit ofa ceux-ci sont stock6s.

0

1

2

3

& S

6

7

0

t

10

11

12

13

l&

15

16

17

18

19 ZO

23

24

25

Z6

27

21

3O

31

-..,. -....

W| W I 6 $

e9

WII 1

W" W't

w' ~, \ w- ~

Wo

W'-~2 " 2 W L

e

W o

W" X & 2Q

w_.' w'

~__ w_.'

W t

FIG. 4. ~ Graphe sym~tris~ d'un algorithme h double base et entrelacement temporel de Iongueur 32.

Symmetrical decimation in frequency split-radix diagram.

2~, W o

28

w ~ ~ 7 23

3

19 27

ANN. T,~gCOMMUN., 40, n ~ 9-10, 1985 6/14

P. DUHAMEL. - ALGORITHME DE TRANSFORMATION DE FOURIER RAPIDE 487

~tage 1 ~tage 2 6tage 3 . . . . . . . . .

0 1 2 3 &

5 6 ? $

9 10 11 12 13 lt, 15

0 2 t, 6

10 12

~ ~ 6 8

12 't 6

9 I 5 9

3 ?

11 15

12

s t 13

'I 11

't 15

FIG. 5. ~ Repr6sentation sch6matique de la progression d'un algorithme b. base double et entrelacement temporel de longueur

16.

Schematic representation of the progression of a 16 point decimation in frequency split-radix algorithm.

bloc de longueur N]2 "-~ intervenant /t l'6tage i est la TFD d'une partie de la s6quence initiale (les indices correspondant ~ ce sous-ensemble sont not6s ~t c6t6 du bloc).

On peut constater facilement que, dans le cas de signaux complexes, les algorithmes ~ racine double et entrelacement temporel ou fr6quentiel sont 6qui- valents : les diagrammes sont exactement sym6triques, et leur complexit6 (nombre d'op&ations arithm6tiques, hombre de papillons n6cessaires pour obtenir le hombre minimal de multiplications) est identique. Nous allons voir dans le paragraphe suivant qu'il n 'en est pas exactement de mSme quand cet algorithme est appliqu6 ~. des signaux r~els.

IV. L ' A L G O R I T H M E A BASE DOUBLE

APPLIQUI~ A DES DONN]~ES R]~ELLES

Cette repr6sentation est fournie en figure 5 pour l 'algorithme ~t double base et entrelacement temporel sur donn6es complexes de longueur 16 : ~t l'6tage 0, les papillons sont appliqu6s ~t un bloc de longueur N, bloc qui sert ~t calculer chacun des 6chantillons Xk, k = 0, . . . , 15. Apr6s cette premi6re &ape, nous avons maintenant un bloc de longueur N/2, appartenant ~t l'6tage 1, qui sert 6. calculer les 6chantillons pairs X2~, k = 0 . . . . . 7, et 2 blocs de longueur N]4, appartenant donc ~ l'6tage 2, utilis6s pour le calcul de X4k+l , k = 0, . . . , 3 et X'4k§ k = 0 , . . . , 3 respectivement. Ce processus est ensuite appliqu6 successivement h t o u s l e s blocs de longueur N/2 ~ apparaissant h r6tage i, i = 0, . . . , n - - 1.

L'algorithme dual (entrelacement fr6quentiel) pr6- sente un diagramme compl6tement sym6trique (Fig. 6) dont l 'interpr6tation est 16g6rement diff&ente : chaque

' t 12

o I 6

"I s t 13

'I 11 ?

~176 ~ 2 1

8 4 2 12 6 3

6 & 10 5 12 6 14 ?

1 e 5 9 9 10

13 11 3 12 7 13

11 I/, 15 15

Flo. 6. - - Graphe d'un algorithme h double base et entrelacement fr6quentiel de longueur 32.

Length 32 decimation in time split-radix algorithm.

I1 est facile de r6duire la complexit6 de calcul dans un algorithme h base double, que ce soit celui ~t entrelacement temporel, ou celui h entrelacement fr~quentiel.

IV.1. Complexit~ arithm~tique.

En effet, quand la s6quence x , est r6elle, Xk et XN-k sont complexes conjugu6s. Report6 dans l'6qua- tion (2), ceci signifie qu'il est inutile de calculer ~t la fois {X4k+l} et {X4k+3}, car :

(9) (X4k+3 } = (X'N_,akt+I)) = (X,~k,+l }.

On voit donc qu'un algorithme h base double et entrelacement temporel d6compose une TED r6elle de longueur 2 nen une TFD r6elle de longueur 2"-x (pour calculer XEk), plus une TFD complexe de longueur 2 n-2 (pour calculer X4R+I), au prix de 3 • 2 n-2 - - 4 multiplications r6elles, 3 • 2"-2 __ 4 additions r6elles dues aux coefficients multiplicatifs et 2" additions.

On obtient donc ainsi la complexit6 arithm6tique d 'une TFD r6elle ~t entrelacement temporel :

(10) M~, = M~_I + M~_2 + 3(2 " - 2 - 2 ) + 2,

et, avec M [ = 0, MI = 0, il vient :

(11) M~ = 2 " - a ( n - 3) + 2 = M~./2,

de m~me : g e (12) A~ = An_ 1 "~- An_ 2 -~- 2" + 3 • 2 n - 2 - 4,

= Ar_ , -+- 2"-2(3 n - - 2),

et, avec A] = 2, i lv ien t :

(13) A r = ( 3 n - - 5 ) 2 "-1 + 4 = A ~ . / 2 - - 2 " + 2 .

Si maintenant on introduit le fait que les donn6es sont r6elles dans l '6quation (3), on voit qu 'une

7/14 ANN. T ~ L ~ C O M M U N , , 40, n ~ 9-10, 1985


d6composition it base double et entrelacement fr6- quentiel transforme une TFR r6elle de longueur 2" en une TFR r6elle de longueur 2"-1 et deux TFR r6elles de longueur 2 "-2, au prix de (2 "-2 - - 2) multiplications du type Pk = W~{X~}, autant du type : P; = w~k{x~'}, X~ et X~,' &ant /t sym&rie hermitienne, plus une multiplication du type W~/8 X~/8 et une multiplication W~ "/8 X~ t . .

Or : I

P, = j P * et Pk = - - J P / , * .

On voit done imm6diatement que le nombre de multiplications r6elles peut &re divis6 par 2 par rapport it une transform~e complexe. Le nombre d'additions peut lui aussi ~tre r6duit en caleulant en m~me temps les << papillons>> correspondant it Xk et ceux correspondant it X - s , auquel cas on a l '6quation de r6currence �9

r r 2 " - - r (14) A~ = A._ 1 + 2 An_ 2 q- 3 • 2 + M . ,

ce qui conduit exactement /L la m~me complexit6 arithm&ique que dans le cas de l'algorithme r6el it entrelacement temporel.

Une comparaison avec les complexit6s d'autres algorithmes publi6s est fournie dans le tableau IV oh le nombre d'op6rations de [17] a 6t6 corrig6 pour prendre l 'algorithme de multiplication complexe it 3 multiplications et 3 additions r6elles. Ici encore, on voit que l 'algorithme it base double a la m~me complexit6 que l 'algorithme FFCT, soit un nombre d'op6rations nettement plus faible que l 'algorithme de Bergland [17].

IV.2 . Structure dans le cas de s ignaux ~t valeur r6elle.

Si nous appliquons une d6composition de type entrelacement temporel it une s6quence r6elle, comme montr6 en figure 7, le bloc de l'&age 0 est r6el eondui- sant apr6s application de la d6composition it un bloc de Iongueur N[2 it l'6tage 1, qui est 6galement r6el.

o, o r o :[ 1 2 4

2 4 II Re/, T 3 6 12 Ira4 J. & 8 Re2 S 10 Re 10 6 12/: Ira2 ? 14 1, Ira10 II RI! 1 RI! 1 ' 9 Re$ Re9

10 Re9 Ira1 ' 11 Re 13 Im 9, 12 Ira1 Rt5 13 Ira5 In~5 14 I rn 9 Re 13 15 lm 13 Im13

FIG. 7. - - Repr6sentation sch6matique d'un algorithme/t base double et entrelacement temporel de longueur 16 appliqu6

/t des donn6es r6elles.

Schematic representation of a 16-point decimation in frequency split-radix algorithm on real data.

Les deux autres blocs de longueur N]4 appartenant /t l'6tage 2 sont complexes, mais comme d6jit indiqu6 au paragraphe pr6c6dent, il n'est pas n6cessaire de calculer X4k+a, de telle sorte que les endroits cor- respondants du diagramme peuvent &re utilis6s pour stocker la partie imaginaire du bloc servant it calculer X4~+1. Ce processus est r6p6t6 jusqu'it ce que la transform6e totale soit obtenue.

Remarquons que, puisque nous devons appliquer la d6composition /t des blocs de donn6es r6elles (le premier bloc de chaque &age) mais aussi it des blocs de donn6es complexes, le nombre de papillons n6cessaires pour une r6alisation it nombre minimal d'op6rations est maintenant 8.

Si maintenant nous appliquons une d6composition de type entrelacement fr6quentiel it une s6quence r6elle, tous les blocs consid6r6s sont des TFD de s6quences r6elles, et pr6sentent une sym&rie hermitienne. I1

TABL. IV. - - Nombre d'op6rations r6elles intervenant clans le calcul d'une TFD de longueur N.

Arithmetic complexity for the computation of FOT'S on real data.

N

16

32

64

128

256

512

Bergland [17]

12

44

132

356

900

2 180

Multiplications

FFCT [13]

10

34

98

258

642

1 538

Base double

10

34

98

258

642

1 538

Bergland [17]

60

172

452

1 124

2 692

6 276

Additions

FFCr [13]

60

164

420

1 028

2 436

5 636

Base double

60

164

420

1 028

2 436

5 636

1 024 5 124 3 586 3 586 14 340 12 804 12 804

2 048 11 780 8 194 8 194 32 260 28 676 28 676

ANN. T~L~CO~iXm., 40, n ~ 9-I0, 1985 8/14


I , oo T.,o I I~'4 I ~.~ /~4

Jim 10 TRe 6 lira 12 LRe 14 Jim 14

Re 9 Re 5 IRe 5 Re 9

Irn 13 IRe 13 "[Re 3 Re 3

I" * / n, . ~Re 15 .Elm 15

'Re 0 Re 1 Re 2 Re 3 Re 4 Re 5 Re 6 Re 7 Re 8 Ira9 Im 10 Im 11 Im 12 Im 13 Im 14 Ire 15

i I~ I: 10 _ERe 10 12 |lm 2 14 .Jim 10

]Re1 ~Rel

10 / " 9 I'm ' 11 JRo 13 JAm 9 12 | lm 1 TRe s 13 | l m 5 .Elm 5 14 Jim 9 TRe 13 15 ~lm 13 Dm 13

ENTRELACEMENT TEMPOREL ENTRELACEMENT FREQUENTIEL

FIG. 8. ~ Repr6sentation sch6matique d'un algorithme /t base double et entrelacement fr6quentiel de longueur 16 appliqu6 /~ des donn6es r6elles.

Schematic representation of a 16-point decimation in time split-radix algorithm on real data.

est done possible de travailler << en place >> en utilisant, pour un bloc de longueur L, les L/2 -k 1 premi6res places m6moire pour la partie r6elle des 6chantillons de transform6e correspondant, et les L/2 - - 1 restants pour la partie imaginaire des autres 6chantillons. Ceci conduit au sch6ma de la figure 8 pour lequel 4 <~ papillons>> diff6rents sont n6cessaires.

Quand ceci est possible (permutation des donn6es avant transformation plut6t qu'apr6s), l'algorithme entrelacement fr6quentieI sera done pr&6r6 /t l'algorithme/t entrelacement temporel quand il sera appliqu6

des donn6es r6elles. Remarquons cependant que, parmi les 8 << papillons>> diff6rents n6cessaires au calcul de la TFR r6elle /t entrelacement temporel, plusieurs sont rarement utilis6s, ce qui permet de trouver facilement des r6alisations sous-optimales avec des performances satisfaisantes.

I1 est bien stir 6galement possible d'accroitre la r6gularit6 de ces algorithmes, comme dans le cas des donn6es complexes, par une permutation des sorties des << papillons >>.

V. L'ALGORITHME A BASE DOUBLE APPLIQUI~ A DES D O N N ~ E S R]~ELLES

ET SYM~TRIQUES

I1 peut 6galement &re int6ressant d'avoir /t sa disposition des algorithmes rapides et << en place >> pour calculer la TFO d'un signal sym6trique ~t valeurs r6elles, par exemple pour des calculs d'autocorr61ation [22].

Si l'on introduit une sym&rie sur les donn6es de l'algorithme ~ double base et entrelacement temporel (Fig. 9), on voit, par application de l'6quation (2) que la premi6re &ape de l'algorithme transforme une s6quence r6elle sym6trique de longueur N en une s6quence r6elle sym6trique de longueur N]2, plus une s6quence complexe avec une sym6trie hermitienne de longueur NI4, la meme d6composition devant ensure ~tre attribude & chacune d'entre-elles.

Une premi6re remarque, qui va nous permettre de calculer la complexit6 arithm&ique de cet algorithme, est que la complexit6 d'une TFD d'un signal

sym6trie hermitienne est la m~me que celle d'une transformation d'un signal r6el.

V

Xls=Xl

xo xl

X2

X3

X4

XS

XB

•

Xo=Xz

Xlo = xe

Xl l =Xs

X12 :X 4

X13= X~

X14 = x2

te X2+Xlo =a2

p x3+x~ =as

/e x4+x~2= a4

xs+x~3=an

/e xe+x~4= az

X7+X lS : ~1

% - - ~ ((xa - r~) + ICx, - x,)) w* = b,

. \ / J ((x.-,.)+,x.-,~))w.-~.-jc.

~ l ~ ((x3- x,) +J(xz- xO) w~ = b~ -Jcl

N Inutlle

FIG. 9. - - Sym6trie intervenant dans un algorithme /~ base double appliqu6 /l des donn6es r6elles et sym6triques.

Symmetry involved in a split-radix algorithm on real symmetric data.

V.1. Complexit6 arithm6tique.

On voit, d'apr6s l'6quation (2) que la d6composition cit6e ci-dessus s'obtient au prix de 3(2 "-3 - - 1) + 1 multiplications et de 2" + 3(2 "-3 - - 1) additions, ce qui implique :

M~, s = M~,LI + M,~_2 § 3(2 "-3 - - 1) + 1,

M~, s = 2 " - 2 ( n - 3) + 1 = M~I2,

(15)

(16)

et :

(17)

(18)

A~,' -- A~,Lt + A~,_2 + (3n - - 4) 2 "-3 + I,

A~ s = 2,-2(3 n - - 7 ) + n + 3 = A ~ . / 2 - - 2 . - l + n + l .

Remarquons que, dans ce d6compte d'op6rations, une multiplication par 2 n'est compt6e, ni comme une multiplication, ni comme une addition. Ceci se justifie clans le cas d'une r6alisation en virgule fixe,

9/14 ANN. T~L~COMMUN., 40, n ~ 9-10, 1985


car dans ce cas, une mise ~t l'Tehelle par des facteurs 2 ou 4 est nTcessaire h l'entrTe du <~ papi l lon, pour 6vi- ter les dTpassements de capacitT. Les multiplications par 2 dues ~t l'algorithme peuvent alors se combiner avec le facteur d'Tchelle.

Une comparaison prTcise est difficile avec l'algorithme de Ziegler [18], qui a utilis6 l'algorithme de multiplication complexe ~ 4 multiplications et 2 additions rTelles.

NTanmoins, l 'algorithme ~ base double devrait avoir une complexit6 arithmTtique plus faible, car les deux algorithmes sont fondTs sur une rTduction de redondance, et diminuent done d 'un facteur approximativement 6gal ~ 2, les nombres d'opTrations de l'algorithme de Bergland [17], et de l'algorithme

base double appliqu6 ~ des donnTes rTelles. LA encore, l'algorithme propos6 ci-dessus demande

la m~me complexit6 qu'un FFCT sur donnTes rTelles sym&riques [22] (Tabl. V.).

I I 12 13 I t 15 16 1"/-1 ~8,1k

! I

~ 0I | Re| I

a,t I 11111 R,:' R~2'

R, 11 Ih110~ II 21 Ili26

Re R ~ I Rt l l Re R ~ Re Re R ~1~ RetT Re II 12 I l l ~ I Re R~S 1 lm R1~21 i In Ro131 lm: I 't Re~t

Fro. 10. - - ReprTsentation schTmatique d'un algorithme h base double et entrelacement temporel de longueur 32 appliqu6

des donnTes rTelles et symTtriques.

Schematic representation of a 32-point decimation in frequency algorithm on real symmetric data.

TABL. V. - - Nombre d'op6rations rbelles intervenant dans le calcul d'une TFD rTelle et symTtrique de longueur N par l'algo-

rithme ~t double base. Arithmetic complexity of a split-radix algorithm on real symmetric

data.

N

16 32 64

128 256 512

1 024 2 048

I Multiplications

129 321 769

1 793 4 097

Additions

5 27 17 72 49 185

458 1 099 2 572 5 901

13 330

V.2. Structure dans le eas de signaux sym6triques valeur r6elle.

Du fait de la sym&rie des s6quences apparaissant lors d'une d6composition A base double d'une s6quence r6elle sym6trique, les N[2 + 1 emplacements m6moire n6cessaires au stockage des donn6es initiales non redondantes peuvent 6galement 8tre utilis6es pour stocker les s6quences transform6es : N]4 + 1 emplacements pour la s6quence r6elle sym6trique de longueur N/2, plus N]4 pour la s6quence complexe

sym6trie hermitienne. Ceci est repr6sent6 sur le premier 6tage de la figure 10

off l 'on volt que le dernier emplacement du vecteur est toujours utilis6 pour le point de sym&rie de la s6quence r6elle sym6trique (le premier bloc de chaque 6tage). Cette d6composition pent s'effectuer avec un nombre minimal d'op6rations ~ l'aide de 3 << papil lons, diff6rents, caract6ris6s par leurs coefficients multiplicateurs (W ~ , Wg Is, autres).

I1 reste maintenant h consid6rer le cas de la s6quence sym&rie hermitienne, dont il faut prendre la TFR.

Une application de la dTcomposition (2) ~t une sTquence complexe de longueur N]4 prTsentant une symTtrie hermitienne montre que la sTquence initiale est transformTe en 3 sTquences de longueurs respec- tives NI8, N I l6 et NIl6 , chacune ayant encore le m~me type de sym&rie, ce qui a deux consdquences : le hombre de coefficients multiplicateurs peut ~tre divis6 par 2, et l 'on peut de plus trouver des algorithmes << en place >> (voir la partie infTrieure du deuxiTme &age) de la figure 10. Comme cette partie de calcul n6cessite 4 << papi l lons, diffTrents, le nombre total se monte maintenant ~t 7 pour une TFR h nombre minimal d'opTrations sur des donnTes rTelles symT- triques.

Remarquons de plus que la partie infTrieure du diagramme fournit un algorithme de TFR de signaux

sym&rie hermitienne.

A ce point de l'exposT, un certain nombre de remarques s'imposent :

Nous disposons, avec l'algorithme ~t double base, d'une m&hode de calcul de la TFD de signaux complexes, rTels, rTels symTtriques (mais aussi de trans- formTes en cosinus discrTtes, et de TFD impaires, utilisTes dans le calcul des TFD a 2 dimensions par transformTes polynomiales) demandant dans chaque cas la complexit6 arithm&ique la plus faible connue.

D'autre part, d'autres algorithmes existent, qui demandent exactement le m~me nombre de multiplications rTelles (bien que prTsentant en gTnTral d'autres inconvTnients par ailleurs). Ces algorithmes sont fondTs sur des principes diffTrents (FFCT, coefficients rTels).

Une question se pose alors naturellement :

Puisque ces mTthodes arrivent toutes au m~me nombre (le plus faible connu) de multiplications rTelles par des voles diffTrentes, ne seraient-elles pas optimales ? (au sens du nombre minimal de multiplications).

ANN. T~L~.COMM~., 40, n ~ 9-10, 1985 10/14


La suite de cet article fournit les premiers SlSments de rSponse h cette question, ~ partir de rSsultats dSj~t partiellement publiSs en [19] :

Apr~s avoir fourni une dScomposition de la TFD de longueur 2" en produits de polyn6mes, nous Svaluons le nombre minimal de multiplications complexes nScessaires au calcul de cet ensemble de produits de polyn6mes. Nous montrons ensuite le lien existant entre cet algorithme ~ opt imal , et l'algorithme ~. double base.

VI. DI~COMPOSITION D'UNE TRANSFORMATION

DE FOURIER DISCRETE DE LONGUEUR 2" EN PRODUITS DE POLYNOMES

Nous ne rappelons ici que les grandes Stapes de cette d6composition, en renvoyant le lecteur ~ [19] pour plus de d&ails.

ConsidSrons tout d 'abord un Stage de dScomposition ~t double base et entrelacement temporel (cf. 6q. (2)). Cet &age dScompose une TFD de longueur 2 ~ en 3 parties :

- - une TFD de longueur 2 "-1, U/(2 n, hr) , i = 0 . . . . , 2 n-2 ~ 1,

- - V~(2", h',) , i = 0, . . . , 2 " - 2 - 1,

oh :

(19) 2 n - 2 - 1

u,(2", h,) = X h, w~, W~", r=O

2 n - 2 - 1

V,(2". h~) = Y~ h" w~" W~". r=O

et h. et h'. sont des combinaisons lin6aires des Schan- tillons initiaux, de pSriode 2 "-2 '

(20) hr+ 2 n - - 2 = h, .

Remarquons tout d 'abord que {U~) et {V~} sont des fonctions du m~me type :

(21) V,(2", h'.) = - - j U2.-2_,_, (2", h~'),

avec : h~' = h'., r = 1, 2 . . . . , 2"-2 ~ 1,

h;' = j h o .

Une cons6quence directe de l'Squation (21) est que, si l 'on trouve une d6composition en produits de polyn6mes de U~(2", h,), on en aura 6galement une pour la TFD initiale.

Or : 2 n - 2 - 1

(22) U,(2", h,) = Z h, W:r W*N", r=O

2 n - 3 - 1

= X h ~ , W ~ ' W y ' + r=O

2n--4_1 2n--4_1

Z h4r+lW~'+lW~(4r+l)'-~ - Z h.r+3w~r+3w2~ (r+3)`, r =O r=O

= Ul(2 "-1, h2,) + SI(WN , hat+l) + T,(WN, h,,+ a)-

Iei encore, 7', est une fonction du type St :

(23) T~(WN, h4,+3) = jSl(Wff 1 , h -4 , - i ) ,

et apr~s avoir remarquS que :

f24) S,+2"-'(Wu, h, ,+l) = jS,(WN_, ha,+1),

et que : 2 " - 4 - 1

S,(W., h..+l) = Z h..+l W~ ('+'(k+', r=O

peut s'Scrire sous forme d 'un produit de polynSmes modulo z 2"-' • j, on voit que U~ peut se calculer par un ensemble de produits de polynSmes, et done qu'il en est de m~me pour la TFD initiale (cf. [19]).

Pour r6sumer, une TFD de longueur 2" sera obtenue par le calcul de 4 produits de polynSme de longueur 2"-*, plus 8 produits de polyn6me de longueur 2"- 5, etc.

VI.1 . C o m p l e x i t ~ de ealcui .

Comme z 2" ~ j e s t un polyn6me irr6ductible dans Q[j] (corps des nombres rationnels &endu par j, j2 = _ 1), un produit de polyn6mes modulo z 2" :~ j se calcule avec un minimum de 2 "+ x _ 1 multiplications complexes.

En sommant le nombre de multiplications n6ces- saires au calcul de (U~(2", h,)}, on obtient sa comple- xit6 :

(25) ~t{U,(2", h,)} --- 2 "-1 - - 2 n - - 3.

Un autre calcul simple nous permet ensuite d'obtenir la complexit6 multiplicative d'une TFD de longueur 2" par cet algorithme :

(26) [L{TFD2n } = 2 "+1 - - 2 n 2 -~- 4 n - - 8.

Tout semble indiquer que ce nombre de multiplications complexes non triviales est l 'optimum (cf. th. 3 de [23]) car les deux conditions essentielles pour que les complexit6s multiplicatives des produits de polyn6mes puissent &re additionnSes sont ici rSunies : ind6pendance lin6aire des variables intervenant dans les produits, ainsi que des constantes multiplicatives : en effet, aucune combinaison linSaire des variables intervenant dans chacun des produits ne redonne un Sl6ment de Q[j]. Des rSsultats plus complets seront publi6s ult6rieurement. Remarquons Sgalement que ce nombre d'op6rations a d6j~ 6t6 publiS dans [24], mais que l'approche utilis6e alors, basSe sur une utilisation des sym6tries, permettait difficilement d'Stablir une optimalitS Sventuelle.

Naturellement, comme les algorithmes optimaux de calcul des produits de polyn6mes deviennent beaucoup trop cofiteux en additions pour des degrSs supSrieurs h 4, cette dScomposition ne parait utile pratiquement que pour les longueurs correspondantes, c'est-h-dire N ~< 64.

Cependant, comme nous avons maintenant l'optimum, nous pouvons comparer les complexitds des

11/14 ANN. T~L~COMMUN., 40, n ~ 9-10, 1985


TABL. VI. ~ Nombre de multiplications complexes non triviales dans diffrrents algorithmes de TrR.

Number of non-trivial complex multiplications for several FFT algorithms.

N = 2 n

8

16 32 64

128 256 512

1 024

Base 2

(n - - 3) 2 "-1 + 2

2 10 34 98

258 642

1 536 3 586

Base 4

(9 n -- 26) 2 n-a + 4

Base double

(3 n - - 8) 2"-- (-- 1) n

8

76

492

2 732

2 8

26 72

186 456

1 082 2 504

Produit de polynOmes

2 " + 1 - 2 "2 + 4 n - - 8

2 8

26 72

178 408 890

1 880

diffrrents algorithmes connus au minimum absolu de multiplications complexes non triviales nrcessaires au calcul d'une TFD de longueur 2". Ceci est effectu6 dans le tableau VI.

Il nous est done facile de voir que l'algorithme ~t base double est, parmi les algorithmes comparrs, celui qui suit l 'optimum le plus longtemps, jusqu'~t N = 64, qui est prrcisrment la longueur ,u-delft de laquelle on ne saurait plus utiliser les algorithmes optimaux de produits de polyn6mes sans consrquences sur le nombre d'additions. C'est ce qui induit la situation off l'algorithme ~ base double est optimal dans une sous-classe convenablement choisie.

V I . 2 . L i a i s o n a v e c l ' a l g o r i t h m e ~ b a s e d o u b l e .

La premirre &ape du raisonnement aboutissant ~t la description de la TFD de longueur 2 nen produits de polynrmes &ait une drcomposition ~t racine double et entrelacement temporel (cf. 6q. (19)). II est 6gale- ment facile de voir que la deuxirme &ape de ce raisonnement, explicitre par l 'rquation (22) est aussi une drcomposition ~t racine double, mais cette fois-ci, ~t entrelacement frrquentiel, appliqure ~t la srquence (h,

Comme les d~compositions h racine double ont la m~me complexit6 l 'une que l'autre, les algorithmes h racine double auront la m~me complexit6 que l'algorithme de d~composition en produits de polyn6mes, pourvu que ces produits soient calcul&, au lieu de l'algorithme ~ nombre minimal de multiplications, h l'aide de :

2 n - 4 - 1

(27) Sl(WN,h,r+t)= W~' ~a (h4,+~ W~ "+~) W~ 6"~, r = 0

qui est l'expression exacte des deux d6compositions successives ~t entrelacements temporel et fr6quentiel.

On voit que l'6quation (27) aboutira ~t un calcul du produit de polyn6me avec un nombre minimal de multiplications (2"-* - - 1) tant que la TFO ne

cofitera pas de multiplications, c'est-h-dire tant que 2"-a ~< 4, ce qui correspond aux remarques d6jA faites au paragraphe pr6c6dent.

VII. CONCLUSION

Dans cet article, nous avons drcrit des algorithmes de transformation de Fourier rapide ~t base double appliqugs ~ des donnres complexes, r&lles, ou rrelles et sym&riques. Ces algorithmes prrsentent l'avantage de pouvoir &re effecturs << en place )~, de demander le nombre le plus faible connu d'oprrations arith- m&iques, et de ne pas nrcessiter de rrorganisation des donnres en cours de calcul.

De plus, la comparaison des complexitrs multiplicatives (hombre de multiplications complexes n o n

triviales) de cet algorithme et d 'un algorithme bas6 sur des drcompositions en produits de polynfmes permet de conjecturer les domaines d'optimalit6 suivants (cfi [20] pour transformations en cosinus et transformations de Fourier impaires) :

T F D complexe TFD rrelle

TFD rrelle-sym&rique

TFD sym&rique hermitienne

transformation en cosinus

transformation de Fourier complexe

N~< 64,

N ~< 64,

N~< 64,

N~< 64,

N ~ < 1 6 ,

N ~ < 3 2 ,

transformation de Fourier A 2 dimensions par transformation polynomiale N • N ~< 64 • 64

Remarquons qu'un critrre d'optimalit6 comptant le nombre de multiplications rrelles donner,i t des rrsultats sensiblement diffrrents [25]. La TFD complexe n'est alors optimale que pour N ~< 16. Cependant, l'optimalit6 par rapport aux multiplications complexes semble fournir un bon compromis entre nombre de multiplications et nombre d'additions.

ANN. T~L~CO~m., 40, n ~ 9-10, 1985 12/14

P. D U H A M E L . - ALGOR1THME DE TRANSFORMATION DE FOURIER RAPIDE 493

ANNEXE I

Programme de calcul d'un algorithme de transformation de Fourier rapide ~ double base appliqu6 6. des donn6es complexes avec des sorties permut6es. Les initialisations se font h l'aide du sous-programme << inisplitor >>. Ce programme permet d'obtenir une vitesse d'ex6cution maximale avec l'option d'optimisa- tion du compilateur FORTRAN, mSme sur des ordina- teurs ~t m6moire virtuelle.

Manuscrit rer le 25 avril 1985, accept6 le 3 juillet 1985.

s u b r o u t i n e s p l t t b r ( n , m ) d i m e n s i o n x ( i O 2 4 ) , y ( 1 0 2 4 ) d i m e n s i o n w l c ( 2 2 9 5 ) , w J m c m s ( 2 5 6 ) 0 w J m c p s ( 2 5 6 ) d i m e n s i o n w 3 c ( 2 5 6 ) , w 3 m c m s ( 2 5 6 ) , w 3 m c p s ( 2 5 6 ) d t m e n s | o n J x 0 ( 3 4 1 ) common x , y , w l c , w l m c m s , w t m c p s , w 3 c , w 3 m c m s , w 3 m c p s , J x O

c d a t a c 2 1 / 0 . 7 0 7 1 0 6 7 7 8 / d a t a c m / - l . 4 1 4 2 1 3 5 6 3 /

c n t - n / 2

C t s t e p = 1 i b = 0 n b � 9 t t n b = 0

C d o 30 J = l , m - 3 n2 �9 n t n l - n l / 2 n3 = n t + n 2 d o 10 t - l , n b

c c . . . . . . . . . . . . . O - m u l t b u t t e r f l y . . . . . . . . . . . . c

r = x ( J x O ( t b + t ) ) - x ( J x O ( t b + J ) + n 2 ) x ( J x O ( t b + t ) ) �9 x(jxO(Jb+i))+x(JxO(tb+t)+n2) s - x ( J x O ( t b § x ( J x O ( t b + t ) + n l ) = x ( J x O ( t b + t ) § 2 4 7 Sp " y ( J x O ( i b + l ) + n l ) - y ( j x O ( l b + t ) + n 3 ) x ( J x O ( i b § - P+sp x ( J x O ( I b + l ) + n 2 ) �9 P-Sp y ( J x O ( i b + t ) + n i ) = y ( j x O ( i b + i ) + n i ) + y ( J x O ( I b + i ) + n 3 ) P = y ( J x O ( t b + t ) ) - y ( J x O ( i b + t ) + n 2 ) y ( J x O ( t b + t ) + n 3 ) �9 r - s y ( J x O ( t b + t ) ) - y ( J x O ( t b + i ) ) + y ( J x O ( t b + t ) + n 2 ) y ( J x O ( t b + t ) + n 2 ) - r + s

c c . . . . . . . . . . . . . g e n e r a | 6 - m u l t b u t t e r f l y . . . . . . . . c

J s t e p - O d o 5 t J - J x O ( t b + t ) + t . J x O ( t b + i ) + n l - t J s t e p = J s t e p + t s t e p r �9 x ( t J ) - x ( t J + n 2 ) x ( t J ) = x ( l J ) + x ( l J § S �9 x ( i J + n t ) - x ( t J + n 3 ) x ( i J + n l ) = x ( t J + n l ) + x ( l J + n 3 ) =p - y ( t J + n l ) - y ( t J + n 3 ) t - r - s p r - r + s p y ( t J + n t ) = y ( t J + n t ) + y ( i J + n 3 ) r p �9 y ( t j ) - y ( t J + n 2 ) sp �9 r p + s spp = ( t + s p ) * w i c ( J s t e p ) x ( l J + n 2 ) = s p * w i m c m s ( J s t e p ) § y ( t J ) = y ( i J ) + y ( i J + n 2 ) y ( l j + n 2 ) = t * w l m c p s ( j s t e p ) + s p p r p �9 r p - s S " ( r + r p ) * w 3 c ( j s t e p ) x ( q j + n 3 ) �9 r p * w 3 m c m s ( J s t e p ) + s

5 C c

l o c

30 C C

y ( t J + n 3 ) �9 r * w 3 m c p s ( j s t e p ) + l c o n t i n u e

~ o n t l n u e

Ib - I b + n b 11nb �9 ]n lo I n b � 9 n b � 9 I n b + 1 1 n b + I t n b

t l t e p �9 t s t e p + l s t e p

d o 50 t = l , r Y o

c . . . . . . . . . . . . . 8 - p o t n t b u t t e r f t y . . . . . . . . . . . . . . c

r �9 x ( J x O ( i b + i ) + l ) - x ( j x O ( i b + i ) + 5 ) x ( J x O ( i b + l ) + l ) �9 x ( j x O ( i b + t ) + l ) + x ( J x O ( t b + t ) + 5 ) s �9 x ( J x O ( i b + l ) + 3 ) - x ( J x O ( t b + i ) + 7 ) x ( J x O ( t b + t ) + 3 ) �9 x ( J x O ( J b + l ) + 3 ) + x ( J x O ( t b + t ) + 7 ) ap �9 y ( J x O ( t b + i ) + 3 ) - y ( J x O ( t b + J ) + 7 ) y ( J x O ( t b + J ) + 3 ) - y ( J x O ( i b + J ) + 3 ) + y ( J x O ( i b + t ) + 7 ) PP �9 y ( J x O ( i b + l ) + l ) - y ( j x O ( t b + J ) + 5 ) t = s+Pp y2 - ( t - s p + r ) * c 2 1 X2 �9 t * c m + y 2 y ( J x O ( J b + l ) + l ) �9 y ( J x O ( J b + t ) ~ l ) + y ( J x O ( t b + l ) + 5 ) t " r + s p ap �9 ( t - P p + s ) * C 2 1 rp �9 t * C m + S p

r �9 x ( J x O ( t b + i ) ) = x ( J x O ( | b + t ) + 4 ) x ( j x O ( t b + t ) ) - x ( J x O ( t b + t ) ) + x ( J x O ( t b + t ) + 4 ) m " x ( J x O ( t b + t ) + 2 ) - x ( J x O ( t b + t ) + 6 ) x ( J x O ( i b + l ) + 2 ) �9 x ( J x O ( i b + i ) + 2 ) + x ( j x O ( I b + i ) + 6 ) t - y ( J x O ( I b + i ) + 2 ) - y ( j x O ( I b + l ) + 6 ) t J = r + t x ( J x O ( J b + t ) + 6 ) �9 t l + r p X ( J X O ( I b + J ) + 7 ) �9 t 1 - r p t = p - t x ( J x O ( i b + t ) + 4 ) �9 t + x 2 x ( j x O ( J b + J ) + 5 ) �9 t - x 2 y ( j x O ( t1=+t ) + 2 ) = y ( j x O ( t b + J ) § l b + t ) + 6 ) r = y ( J x O ( t b + i ) ) - y ( j xO( t b + t ) + 4 ) t = r - S y ( J x O ( I b + l ) + O ) �9 t + s p y ( J x O ( t b + t ) + 7 ) - t - s p y ( J x O ( t b + l ) ) �9 y ( J x O ( J b + t ) ) + y ( J x O ( t b + J ) + 4 ) g �9 Pea y ( J x O ( t b + J ) + 4 ) �9 s + y 2 y ( J x O ( I b + t ) + 5 ) �9 8 - y 2

50 c o n t i n u e c c . . . . . . . . . . . . . . 4 - p o t n t d f t . . . . . . . . . . . . . . . . c

t b = Jb+nb n b - n b + l n b + I n b d o 60 J � 9

60 c

r = x ( J x O ( I b + 1 ) ) + x ( J x O ( I b + i ) + 2 ) = �9 x ( J x O ( I b + l ) ) - x [ J x O ( i b + l ) + 2 ) t = x ( J x O ( I b + 1 ) + l ) + x ( J x O ( i b + i ) + 3 ) x ( J x O ( i b + t ) ) - r + t U = X ( J x O ( t b + t ) + l ) - x ( j x O ( t b + l ) + 3 ) x ( ~ x O ( t b + t ) + J ) = P - t P �9 y ( J x O ( i b + t ) + l ) + y ( J x O ( t b + t ) + 3 ) t " y ( J x O ( t b + i ) + J ) - y ( J x O ( I b + l ) + 3 ) x ( J x O ( t b + t ) + 3 ) = S+t x ( J x O ( i b + t ) + 2 ) - S - t t " y ( j x O ( t b + l ) ) - y ( J x O ( I b + t ) + 2 ) y ( J x O ( i b + t ) + 3 ) = t - U S = y ( J x O ( l b + t ) ) + y ( J x O ( t b + t ) + 2 ) y ( J x O ( t b + l ) ) = S+P y ( J x O ( i b + t ) + f ) - S-P y ( J x O ( t b + J ) + 2 ) �9 t + u c o n t l n u a

r e t u r n e n d

.../...

13/14 ANN. TI~LI~COMMUN., 40, n ~ 9-10, 1985


s u b r o u t i n e l n t s p l l t b r ( m ) d imension x ( t O 2 4 ) , y ( t O 2 4 ) , x x ( l O 2 4 ) , y y ( 1 0 2 4 ) d | m e n s t o n wlc(2295),w1mcms(256),wlmcps(256) d imension w3c(256),w3mcms(256),w3mcps(256) d i m e n s i o n J x 0 ( 3 4 t ) common x,y,wtc,wtmcms,wtmcps,w3c,w3mcms,w3mcps,JxO n = 2**m x n - n pt 3.1415926 ang - 2 . * p i / x n

do 31 1 - 1 , n / 4 C

w l c ( 1 ) = c o s ( 1 * i * e n g ) wimcms(1) = - w l c ( 1 ) - s l n ( 1 . * i * a n g ) wlraeps({) �9 - w l c ( 1 ) + s l n ( 1 . * i * a n g )

c w3c(1) �9 c o s ( 3 * i * a n g ) w3mcms(1) = - w 3 c ( 1 ) - s l n ( 3 . * 1 * a n g )

31 w3mcps(I) " - w 3 c ( t ) + s t n ( 3 . * t * a n g ) ] • �9 t JxO(2) " 1 JxO(3) = t JxO(4) �9 n /2§ JxO(5) " 3 " n / 4 + t |p = 5 n b = 3 Inb " 1 do 30 t= l ,m-4 do 20 J = l , n b JxO( Ip+J ) = JxO( Ip -nb+J )12§

20 con t i nua tp �9 Ip+nb do 10 ] = l , l n b J x O ( l p + j ) �9 jxO(Ip-nb-nb-lnb+J)/4+n/2§ JxO( Ip+J§ = JxO( ip§

10 con t i nue tp �9 t p§ l i n t ) = lnb Inb � 9 n b � 9 Inb+11nb+ l lnb

30 c o n t i n u a r e t u r n end

BIBLIOGRAPHIE

[1] COOL~V (J. W.), TuKEY (J. W.). An algorithm for machine computation of complex Fourier series. Math. Comput., USA (1965), 19, pp. 297-301.

[2] RADER ((3. M.), BP.ZN~R (N. M.). A new principle for fast Fourier transformation. 1EEE Trans. ASSP, USA (1976), 24, pp. 264-265.

[3] CHO (K. M.), TBff~s (G, C.). Real-factor FFr algorithms. Proc. o f 1EEE 1CASSP (1978), pp. 634-637.

[4] PREUSS (R. D.). Very fast computation of the Radix-2, Discrete Fourier Transform. IEEE Trans. ASSP, USA (1982), 30, pp. 595-607.

[5] NUSSBAU~R (H. J.). Fast Fourier Transform and convolu- tion Algorithm. Springer, Berlin (1981).

[6] JOHNSON (H.), BURROS (C. S.). Twiddle factors in the radix-2 wr. Actes de la Conf. Circ. Syst. Comput., Asilomar 1982, pp. 413-416.

[7] WINOGRAD (S.). O13. the multiplicative complexity of the Discrete Fourier transform. Advances in Mathematics, GB (1979), 32, pp. 83-117.

[8] BtmRUS ((2. S.), ESCnENBACrmR (P. W.). An in-place, in- order prime factor FFT algorithm. IEEE Trans. ASSP., USA (1981), 29, pp. 806-817.

[9] MORRIS (L. R.). Automatic generation of time efficient digital signal processing software. IEEE Trans. ASSP., USA (f6v. 1977), 25, n ~ 1, pp. 74-79.

[10] WlNOGRAD (S.). On computing the Discrete Fourier Transform. Math. Comput., USA (jan. 1978), 32, pp. 175- 199.

[11] DUHAMEL (P.), HOLLMANN (H.). Split-radix FFT algorithm. Electron. Lett., GB (jan. 1984), 20, n ~ 1, pp. 14-16.

[12] YAVNE (R.). An economical method for calculating the discrete Fourier transform. AFIPS Proc., Washington (1968), 33, pp. 115-125. Fall Joint Computer Conference.

[13] VETTERLI (M.), INTussBAUMER (H. J.). Simple FFT and DCT algorithms with reduced number of operations. Signal Processing, Nederl. (juil. 1984), 6, n ~ 4, pp. 267-278.

[14] WANG (Z.). Fast algorithms for the discrete W transforms and the Discrete Fourier Transform. IEEE Trans. ASSP, USA (aofit 1984), 32, n ~ 4, pp. 803-816.

[15] MARTENS (J. B.). Recursive cyclotomic factorization. A new algorithm for calculating the Discrete Fourier Trans- form. IEEE Trans. ASSP., USA (avr. 1984), 32, n ~ 2, pp. 750-761.

[16] MARTENS (J. B.). Discrete Fourier Transform algorithms for real valued sequences. 1EEE Trans. ASSP., USA (avr. 1984), 32, n ~ 2, pp. 390-396.

[17] BERGLAND (G. O.). A fast Fourier Transform algorithm for real-valued series. Commun. ACM (oct. 1968), 11, pp. 703-710.

[18] ZIEGLER (H.). A fast Fourier Transform Algorithm for symmetric real-valued series. IEEE Trans. ASSP, USA (d6c, 1972), 20, n ~ 5, pp. 353-356.

[19] DUHAMEL (P.), HOLLMANN (H.). Existence of a 2n-~r algorithm with a number of multiplications lower than 2 n+z. Electron. Lett., GB (ao~t 1984), 201 n ~ 17, pp. 690-692.

[20] DUHAMEL (P.). Implementation of << split-radix>> FFT algorithms for complex, real and real-symmetric data. Soumis pour publication dans IEEE Trans. on ASSP.

[21] MORRIS (L. R.). Digital signal processing software. DSPSW, Inc., Ottawa, Canada (1983).

[22] VETTERLI (M.). FFT'S of signals with symmetries and application to autocorrelation computation. Present6 MELECON'85. Madrid.

[23] AUSLANDER (L.), WINOGRAD (S.). The multiplicative complexity of certain semi-linear systems defined by polynomials. Adv. Appl. Math., DE (1980), 1, pp. 257- 299.

[24] MESCnEDER (B.). On the number of active. - op&ations needed to compute the Discrete Fourier Transform. Acta Informatica (1980), 13, pp. 383-408.

[25] I~IDEMAN (M. T.), BURRUS (C. S.). Multiply/add trade- otis in length-2 n r r r algorithms. ICASSP'85, Tampa, pp. 780-783.

ANN. T ~ L g C O ~ . , 40, n ~ 9-10, 1958 14/14

Documents

Un algorithme de transformation de Fourier rapide à double base