DFT e FFT: la trasformata di Fourier al computer
Definizione della DFT, risoluzione e leakage, finestre, l'algoritmo FFT con la farfalla e il suo costo, convoluzione veloce, OFDM, compressione e radar.
La trasformata di Fourier della lezione di Metodi matematici è un integrale su un segnale continuo e infinito. Al computer si hanno invece 
campioni. La trasformata discreta di Fourier (DFT) è la versione per i segnali campionati, e la FFT (Fast Fourier Transform) è l’algoritmo che la calcola in modo efficiente. Inventata nella forma moderna da Cooley e Tukey nel 1965, è considerata uno degli algoritmi più importanti del Novecento: c’è in ogni oscilloscopio digitale, nel Wi-Fi, nel 4G e 5G, nella compressione MP3 e JPEG, nei radar.
La DFT
Dati campioni 
, presi con frequenza 
, la DFT è
![\[ X_k = \sum_{n=0}^{N-1}x_n\,e^{-2\pi i\,kn/N},\qquad k = 0, 1, \dots, N - 1 \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-ef54ed75e73cbd6808048499764edd7a_l3.png "Rendered by QuickLaTeX.com")
e la trasformata inversa
![\[ x_n = \frac1N\sum_{k=0}^{N-1}X_k\,e^{2\pi i\,kn/N} \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-3bf57ea528dda71f864307e7612fdbc0_l3.png "Rendered by QuickLaTeX.com")
Il coefficiente 
misura quanto il segnale somiglia a una sinusoide che compie 
periodi nella finestra di campioni, cioè alla frequenza 
. La risoluzione in frequenza è 
: per distinguere due frequenze vicine servono finestre lunghe.
Due proprietà da ricordare.
- Per un segnale reale
: la seconda metà dello spettro è lo specchio della prima, e le frequenze utili vanno da 0 a 
(la frequenza di Nyquist). È lo stesso fenomeno dell’aliasing. - La DFT tratta il segnale come se fosse periodico con periodo . Se la finestra non contiene un numero intero di periodi, l’inizio e la fine non si raccordano e lo spettro si “sparpaglia” sulle righe vicine (dispersione spettrale, o leakage). Si riduce moltiplicando il segnale per una finestra che va dolcemente a zero ai bordi (Hann, Hamming, Blackman): è l’opzione “window” degli analizzatori di spettro e degli oscilloscopi.
Il costo e l’idea della FFT
Calcolata direttamente, la DFT richiede somme di termini: 
moltiplicazioni complesse. Con 
sono 
operazioni.
La FFT sfrutta la struttura degli esponenziali. Con pari si separano i campioni di indice pari e dispari:
![\[ X_k = \sum_{m=0}^{N/2-1}x_{2m}\,e^{-2\pi i\,km/(N/2)} + e^{-2\pi i\,k/N}\sum_{m=0}^{N/2-1}x_{2m+1}\,e^{-2\pi i\,km/(N/2)} = E_k + W^k\,O_k \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-aa5006f9a093564b879eace99cd69fea_l3.png "Rendered by QuickLaTeX.com")
e 
sono le DFT, di lunghezza 
, dei campioni pari e dispari, e 
. Inoltre, poiché 
e 
hanno periodo e 
:
![\[ X_k = E_k + W^kO_k,\qquad X_{k + N/2} = E_k - W^kO_k \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-4bf63bf7ca3c0dc24ff6eed8d89a2bb9_l3.png "Rendered by QuickLaTeX.com")
Con una moltiplicazione si ottengono due coefficienti (la “farfalla”). Una DFT di lunghezza diventa due DFT di lunghezza più moltiplicazioni; ripetendo fino a lunghezza 1, con 
si fanno 
livelli. Il costo totale è
![\[ \frac N2\log_2 N \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-5fd73e860f02c75672059f47e480f632_l3.png "Rendered by QuickLaTeX.com")
moltiplicazioni. Con (circa 
): circa 
invece di , centomila volte meno. È la differenza tra un calcolo di pochi millisecondi e uno di ore.
La convoluzione veloce
La convoluzione di due sequenze di lunghezza costa direttamente operazioni. Con il teorema della convoluzione (lezione sulla trasformata di Fourier), si fa la FFT di entrambe, si moltiplicano gli spettri e si fa la FFT inversa: costo proporzionale a 
. È così che si applicano i filtri FIR molto lunghi, gli effetti di riverbero ricavati da una risposta impulsiva e la moltiplicazione di numeri interi enormi.
Le applicazioni
- Analisi di spettro. La funzione FFT degli oscilloscopi digitali mostra le armoniche di un segnale: si vede subito la distorsione di un amplificatore o il disturbo a 50 Hz della rete.
- OFDM. Wi-Fi, 4G, 5G e la TV digitale trasmettono i dati su centinaia o migliaia di sottoportanti ortogonali. Il trasmettitore costruisce il segnale con una FFT inversa, il ricevitore lo scompone con una FFT. Senza un algoritmo veloce queste tecniche non sarebbero realizzabili in un telefono.
- Compressione. MP3 e AAC lavorano su una trasformata simile (la MDCT) e scartano le componenti che l’orecchio non sente; JPEG usa la trasformata discreta del coseno su blocchi di 8×8 pixel.
- Radar e sonar. La distanza e la velocità dei bersagli si ricavano dalle frequenze presenti nel segnale ricevuto, calcolate con la FFT: è così che funzionano i radar automobilistici a 77 GHz.
Zero padding e risoluzione
Aggiungere zeri in coda ai campioni prima della FFT (zero padding) rende lo spettro più fitto e più bello da vedere, ma non aumenta la risoluzione: due frequenze più vicine di , con il numero di campioni veri, restano indistinguibili. Per separarle serve una finestra di osservazione più lunga. È lo stesso principio di indeterminazione tra tempo e frequenza visto per la trasformata continua.
