FFT — Trasformata di Fourier veloce spiegata in modo semplice

La FFT, o trasformata di Fourier veloce, è un modo rapido per calcolare la trasformata discreta di Fourier (DFT). Se parti da campioni equidistanti, la DFT ti dice quanto di ciascuno schema di frequenza discreto è presente in quei campioni.

Il punto importante è che la FFT non cambia il risultato. Fornisce gli stessi valori della DFT ottenuti con la formula diretta, ma ci arriva con molto meno lavoro ripetuto.

FFT in una frase

La FFT è un algoritmo più veloce per ottenere gli stessi numeri nel dominio della frequenza già definiti dalla DFT.

Che cosa misura la DFT

Supponi di avere campioni $x_0, x_1, \dots, x_{N-1}$. La DFT produce numeri $X_0, X_1, \dots, X_{N-1}$ definiti da

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

Ogni $X_k$ misura quanto fortemente i dati corrispondono a uno schema di frequenza discreto.

Se i campioni sono equidistanti con frequenza di campionamento $f_s$, allora i bin di frequenza adiacenti sono separati da

$$\frac{f_s}{N}$$

Questa condizione è importante. Senza una frequenza di campionamento nota, hai comunque i bin della DFT, ma non puoi etichettarli come frequenze fisiche, per esempio in hertz.

Perché la FFT è più veloce

La FFT è una famiglia di algoritmi per calcolare la DFT in modo efficiente. L’idea principale è riutilizzare la struttura dei fattori esponenziali complessi invece di ricalcolare da zero somme quasi identiche.

La versione più facile da visualizzare è la FFT radix-2. Funziona in modo più naturale quando $N$ è una potenza di $2$, e divide una trasformata di lunghezza $N$ in due trasformate di lunghezza $N/2$ prima di combinare i risultati.

Per la DFT diretta, la quantità di calcoli cresce dell’ordine di $N^2$. Per i metodi FFT più comuni, scende a circa $N \log N$.

È questa differenza che rende la FFT importante nella pratica. Per input piccoli, entrambi i metodi possono sembrare accettabili. Per input grandi, la FFT è enormemente più veloce.

Come la FFT divide il lavoro

Invece di confrontare direttamente ogni campione con ogni schema di frequenza, la FFT scompone il problema in trasformate più piccole e poi le ricombina con fattori di fase.

Una suddivisione standard è:

1. Metti i campioni con indice pari in un elenco.
2. Metti i campioni con indice dispari in un altro elenco.
3. Calcola trasformate più piccole su questi elenchi.
4. Combina le due metà.

Questo è il principio del divide et impera applicato all’analisi in frequenza.

Esempio di FFT a 4 punti

Prendi il segnale a 4 punti

$$x = [1, 0, 1, 0]$$

Questo schema alterna $1$ e $0$, quindi ci aspettiamo una certa struttura in frequenza invece di un risultato completamente piatto.

Dividilo in indici pari e dispari:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

La DFT a 2 punti della parte pari è

$$E = [2, 0]$$

e la DFT a 2 punti della parte dispari è

$$O = [0, 0]$$

Per una FFT a 4 punti, il passaggio di combinazione è

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

dove

$$W_4 = e^{-i 2 \pi / 4}$$

Poiché $O_k = 0$, la combinazione è particolarmente semplice:

$$X = [2, 0, 2, 0]$$

Ora interpreta il risultato.

$X_0 = 2$ è il termine a frequenza zero, quindi riflette il valore medio non nullo dei campioni. Il valore non nullo in $X_2$ cattura la parte alternata dello schema in questo caso a 4 punti. Se prima sottrai la media, il termine $X_0$ scompare e la componente alternata risalta più chiaramente.

Questo esempio è piccolo, ma l’idea si estende: risolvi trasformate più piccole, poi combinane i risultati invece di ricostruire ogni volta l’intera somma.

Errori comuni sulla FFT

Trattare FFT e DFT come risultati diversi

Non lo sono. La FFT è un metodo più veloce per calcolare la DFT.

Leggere i bin come frequenze fisiche troppo presto

Le posizioni dei bin diventano frequenze fisiche solo quando è nota la spaziatura dei campioni. Se la frequenza di campionamento è $f_s$, allora la spaziatura tra i bin è $f_s/N$ per campioni equidistanti.

Supporre che lo zero-padding aggiunga nuove informazioni

Lo zero-padding può far apparire uno spettro più liscio perché campiona la trasformata sottostante in modo più fine, ma non aggiunge nuovi dati misurati.

Ignorare la preparazione del segnale

La rimozione della media, l’applicazione di finestre e scelte accurate di campionamento possono contare molto. Se queste condizioni vengono ignorate, l’output della FFT può essere ancora matematicamente corretto per i campioni dati, ma fuorviante nell’interpretazione.

Dove si usa la FFT

La FFT compare ovunque servano informazioni rapide nel dominio della frequenza a partire da dati campionati. Esempi comuni includono analisi spettrale, filtraggio, elaborazione di immagini, analisi delle vibrazioni, risoluzione numerica di equazioni differenziali e calcoli rapidi di polinomi o convoluzioni.

Il motivo è pratico: molte operazioni diventano più semplici o più veloci dopo il passaggio dal dominio dei campioni al dominio della frequenza.

Prova un caso simile

Prendi $8$ campioni equidistanti di un’onda sinusoidale su un periodo completo e calcola la DFT con una calcolatrice o uno script. Poi aggiungi un offset costante e confronta il nuovo output. Il valore più grande in $X_0$ è un modo semplice per vedere che cosa separa la FFT.