Capitolo 7La DFT e la FFT

Tutto quello che precede ha costruito intuizione. Questo è l'algoritmo reale: data soltanto una lista di numeri campionati, calcola esattamente quali frequenze sono presenti nel segnale — senza sbirciare come è stato costruito.

Progetta un segnale (come nel Capitolo 5)

Trascina per impostare l'ampiezza di ogni frequenza

Spettro calcolato solo a partire dai campioni (l'uscita della DFT)

Segnale / campioni |X_k| recuperato dalla DFT

La formula

La Trasformata Discreta di Fourier prende $N$ campioni $x_0, x_1, \dots, x_{N-1}$ e produce $N$ numeri complessi che descrivono il contenuto in frequenza del segnale:

Trasformata Discreta di Fourier

$$ X_k = \sum_{n=0}^{N-1} x_n \, e^{-i 2\pi k n / N} \qquad k = 0, 1, \dots, N-1 $$

Ogni $X_k$ risponde a una domanda: "quanto è presente della frequenza $k$ (in cicli per finestra di campioni)?" $|X_k|$ — il modulo di quel numero complesso — è esattamente l'altezza della barra che vedi tracciata sopra. Questa è la stessa rotazione $e^{-i\theta}$ dei cerchi del Capitolo 4, solo eseguita una volta per ogni frequenza che vuoi testare, invece che disegnata nel tempo.

Nota che lo spettro sopra si accende solo alle frequenze che hai effettivamente impostato con le manopole — tutto il resto legge praticamente zero. La DFT ha recuperato la tua ricetta di frequenze partendo da nient'altro che i valori grezzi dei campioni.

Perché esiste la FFT

Calcolata direttamente, la formula sopra costa $O(N^2)$ moltiplicazioni — per ciascuna delle $N$ frequenze di uscita, sommi su tutti gli $N$ campioni di ingresso. La Trasformata Veloce di Fourier (FFT) non è una formula diversa; è la stessa DFT calcolata in modo intelligente, dividendo ricorsivamente la somma in campioni di indice pari e dispari e riutilizzando il lavoro tra loro. Questo riduce il costo a $O(N \log N)$:

N (campioni)	DFT: N² op	FFT: N·log₂N op	Accelerazione

Con $N$ piccolo la differenza conta a malapena. Nelle dimensioni usate dal reale trattamento di audio, immagini e segnali radio — milioni di campioni — la FFT è l'unica ragione per cui tutto ciò funziona in tempo reale.

Il ciclo completo, in una frase: un segnale viene campionato (Cap. 6) rispettando il limite di Nyquist, la FFT trasforma quei campioni in uno spettro (questo capitolo) usando la stessa idea di fasore rotante degli epicicli (Cap. 4), quello spettro viene modificato o analizzato nel dominio della frequenza (Cap. 5), e una trasformata inversa — la stessa formula eseguita al contrario — ricostruisce un segnale nel dominio del tempo come somma di onde sinusoidali (Cap. 3). Quel ciclo completo è la trasformata di Fourier.