Algoritmo Fast Fourier Trasform (FFT)

La trasformata di Fourier è uno strumento matematico particolarmente flessibile largamente utilizzato nella elaborazione dei segnali in numerosi campi (acustica, spettroscopia, comunicazioni satellitari, trattamento di immagini, ...).

Dal 1965 (Cooley e Tukey) sono state superate difficoltà computazionali permettendo il calcolo veloce della trasformata di Fourier tramite un algoritmo generalmente noto come FFT: questo ha dato grande impulso alle tecniche interferometriche per la spettroscopia in trasformata di fourier.

Il processo digitale di calcolo della trasformata di Fourier si può essenzialmente ridurre alla moltiplicazione di un vettore di $N$ elementi per una matrice $N\times N$ i cui elementi sono radici complesse dell'unità: l'elemento di riga $h$ e colonna $k$ è:

$$e^{2\pi i hk/N}$$

essendo $i$ l'unità immaginaria. Evidentemente ogni elemento della matrice è diverso da zero e questo comporta che, nonostante la semplicità concettuale del calcolo, si devono svolgere $N^2$ moltiplicazioni.

Nel caso di una misura con l'interferometro di Michelson, se si vuole fare una scansione dello specchio mobile di $1 mm$ con passi dell'ordine di $\lambda /10$, è necessaria l'acquisizione di $N\approx 5000$ valori se si assume $\lambda \approx 0.5 \mu m$ per la luce visibile. Il calcolo della trasformata richiederebbe 25 milioni di moltiplicazioni.

In questo calcolo, tuttavia, molte moltiplicazioni vengono ripetute più volte: sfruttando particolari proprità algebriche della matrice di Fourier e organizzando il calcolo in modo efficiente possono essere eliminate quasi tutte le ridondanze nelle operazioni riducendo il numero complessivo di moltiplicazioni da $N^2$ a $N\log_2 N$. Nel caso del vettore di 5000 elementi si ha una riduzione del numero di moltiplicazioni di un fattore 400. Il vantaggio dell'applicazione della FFT cresce rapidamente al crescere di $N$.

La pubblicazione del lavoro di Cooley e Tukey del 1965 fu affrettata e dettata (vd. B.A. Cipra SIAM News vol. 26-3, Maggio 1993) principalmente dal fatto che l'algoritmo si prestava ad essere sottoposto a brevetto: Cooley lavorava presso la IBM la cui politica era volta ad evitare che software e algoritmi venissero ``imbottigliati'' da brevetti; la conseguente decisione fu di rendere l'algoritmo di ``pubblico dominio'' con la pubblicazione dell'articolo.