Calcolo numerico - Algoritmi FFT

Algoritmi FFT: decomposizione radix-2 e

radix-r

Cooley–Tukey, decimazione nel tempo e in frequenza

1 La FFT come famiglia di algoritmi

Con l’espressione Fast Fourier Transform non si indica una trasformazione diversa dalla

DFT, ma una famiglia di algoritmi che calcolano la stessa quantità con un numero

molto minore di operazioni. Il principio generale è il divide et impera: un problema

di dimensione viene scomposto in problemi più piccoli, le cui soluzioni vengono

N

combinate sfruttando le proprietà delle radici dell’unità.

L’algoritmo storicamente associato a Cooley e Tukey è particolarmente semplice quando

è una potenza di due. In questo caso si può dimezzare ripetutamente la dimensione fino

N

ad arrivare a trasformate di lunghezza uno o due. La riduzione non è un’approssimazione;

è una fattorizzazione esatta della matrice di Fourier.

2 Decimazione nel tempo

Si supponga pari. Partendo da

N −1

N kj

X

=

X x ω ,

k j N

j=0

si separano gli indici pari e dispari:

N/2−1 N/2−1 (2m+1)k

2mk

X X

+

=

X x ω x ω .

k 2m 2m+1 N

N

m=0 m=0

2

Poiché = ,

ω ω

N/2

N k

= +

X E ω O ,

k k k

N

dove N/2−1 N/2−1

mk mk

X X

= =

x ω x ω

E , O .

k k

2m 2m+1

N/2 N/2

m=0 m=0

Le quantità e sono DFT di lunghezza dei campioni pari e dispari.

E O N/2

k k 1

Per ottenere anche il coefficiente si usa

X k+N/2

k+N/2 k

−ω

=

ω .

N N

Ne segue k k

−

= + =

X E ω O , X E ω O ,

k k k k k

k+N/2

N N

−

per = 0, 1.

k . . . , N/2

La coppia di formule costituisce l’operazione elementare detta butterfly. A partire da

due valori e , si calcolano due uscite usando una moltiplicazione complessa per

E O

k k

k

il fattore e due somme. Il nome deriva dalla forma grafica dei collegamenti nel

ω

N

diagramma di flusso.

3 Ricorsione e complessità

Se (N ) indica il costo dell’algoritmo, la decomposizione produce due trasformate di

T

dimensione e un lavoro lineare per combinarle:

N/2 (N ) = 2T (N/2) +

T cN.

p

Per = 2 , risolvendo la ricorrenza si ottiene

N O(N

(N ) = log ).

T N

2

Il diagramma contiene = log stadi, ciascuno con butterfly. L’efficienza non

p N N/2

2

deriva dal calcolare meno coefficienti, ma dal riutilizzare sistematicamente risultati