Capitolo 6

Una procedura usuale nella risoluzione di un problema matematico consiste nell'applicare alla variabile incognita del problema un'opportuna trasformazione, in modo da ottenere nella nuova variabile, un problema di più facile soluzione; risolto poi il problema "trasformato", si ritorna al problema originario mediante la trasformazione inversa. Tra le varie trasformazioni a disposizione, quella di Fourier occupa un posto di rilievo per l'importanza delle sue applicazioni.

La Trasformata discreta di Fourier (DFT), è caratterizzata da un campo applicativo vastissimo, che spazia dall'interpolazione trigonometrica alla risoluzione di sistemi lineari, dai problemi differenziali alle derivate parziali alle antenne, dall'ottica all'elaborazione dei segnali; in quest'ultimo campo, in particolare, riveste un ruolo fondamentale per le sue applicazioni, soprattutto per quanto riguarda il "filtering" dei segnali, cioè quel processo computazionale che trasforma un segnale campionato in un altro e che prende il nome di filtro digitale.

Esempi di campi di applicazione dei filtri digitali basati su DFT sono l'elaborazione di immagini e la ricostruzione di segnali acustici o, più in generale, l'elaborazione di forme di informazione costituita da un numero discreto di dati.

Sebbene la trasformata discreta di Fourier risulti una potentissima procedura di risoluzioni di molti problemi matematici, essa è caratterizzata da una complessità computazionale che è eccessiva quando si utilizza la DFT per risolvere problemi di grandi dimensioni. Tutto ciò ha portato alla ricerca di un algoritmo per il calcolo della DFT che avesse una complessità inferiore.

Nel 1965 l'ingegnere dell'IBM Cooley e il matematico Tukey giunsero alla determinazione dell'algoritmo noto come "Decimation in time", detto anche Fast Fourier Transform (FFT), che riduceva notevolmente la complessità computazionale della DFT e ne aumentava inoltre la stabilità. L'FFT è semplicemente un algoritmo che consente di calcolare in modo molto rapido la trasformata discreta di Fourier DFT.

La strategia su cui si basano gli algoritmi FFT, detti "divide and conquer", è quella di ricondurre il calcolo di una DFT di lunghezza N, al calcolo di una DFT di lunghezza inferiore.

Una variante all'algoritmo decimation in time è il "decimation in frequency". La differenza principale fra i due algoritmi è nell'ordine con cui sono svolte alcune operazioni. Nel decimation in time, anche detto algoritmo di Cooley-Tukey, gli elementi in input vengono riarrangiati mediante un'operazione di bit-reverse, e quindi viene calcolato l'output della FFT, mediante log₂N iterazioni. Nel decimation in frequency o algoritmo FFT di Sande-Tukey vengono preliminarmente eseguite log₂N iterazioni sui dati di ingresso e quindi viene applicato il bit-reverse.

Una classe di algoritmi FFT è quella detta radix-r, in cui il calcolo di una DFT di lunghezza N=r^s, è ricondotto al calcolo di una DFT di lunghezza r. Se r è uguale a due, allora l'algoritmo è di tipo particolarmente agevole (FFT radix-2), in generale esistono algoritmi per N=r₁r₂...r_k detti mixed-radix.

Per quanto riguarda il vantaggio computazionale, mentre il calcolo di una DFT di lunghezza N con il metodo tradizionale ha una complessità di tempo di O(n²) e quelli di tipo mixed-radix una complessità di tempo O(n(r₁+r₂+...+r_k)), gli algoritmi FFT ne hanno una di O(nlog₂N), da cui segue la convenienza a adottare tali algoritmi.

Gli algoritmi che sono analizzati, sono gli FFT radix-2, che sono i più utilizzati nel campo applicativo, sia perché un elaboratore in genere utilizza un sistema floating-point in base due, sia perché per N=2 ^s alcuni degli esponenziali che occorre calcolare nel corso del procedimento, sono tali da evitare l'esecuzione effettiva delle moltiplicazioni.