Quello che il FFT ti mostra

La questione

Suona un accordo su un pianoforte — dire, C ed E insieme. Il tuo orecchio sente un suono. Ma quel suono è due frequenze sovrapposte: 261.6 Hz e 329.6 Hz. La vostra coclea li separa fisicamente — diverse cellule di capelli risuonano a frequenze diverse, inviando segnali distinti al vostro cervello.

Il Fast Fourier Transform fa la stessa cosa, ma con numeri al posto delle cellule dei capelli. Dagli un segnale (una sequenza di campioni di ampiezza nel tempo) e restituisce un elenco di frequenze e i loro punti di forza. Risponde: che frequenze sono presenti, e quanto di ciascuno?

Cosa succede in realtà

Un segnale campione nel tempo è un elenco di numeri: l'ampiezza ad ogni punto campione. Una registrazione di 1 secondo a 44.100 Hz è 44.100 numeri. Questi numeri descrivono il segnale nel dominio time — ampiezza come funzione del tempo.

Il FFT lo converte al dominio frequenza — ampiezza come funzione di frequenza. Stesse informazioni, rappresentazione diversa. Come passare tra coordinate cartesiane e polari: nulla viene creato o distrutto, solo riespresso.

Il nucleo matematico: ogni segnale periodico può essere scritto come una somma di onde sine e cosene a frequenze diverse. Questo è il teorema di Fourier (1807). Il FFT calcola i coefficienti di tale somma — quanto di ogni frequenza è nel segnale.

Perché "Fast"

Il modo ingenuo di calcolare una trasformazione di Fourier richiede Operazioni N2 per campioni N. Per 1024 campioni, sono circa 1 milione di operazioni. L'algoritmo Cooley-Tukey (1965) riduce questo a N·log2(N) — circa 10.000 operazioni per lo stesso input. Una velocita' di 100x. Per un milione di campioni, il speedup è di 50.000x.

Il trucco: dividere il N-point si trasforma in due trasformazioni N/2-point, ricorsivamente. Ciò richiede che N sia una potenza di 2 (o pad con zero). Ogni divisione ha il problema. L'operazione "butterfly" combina le metà:

X[k]     = Even[k] + W · Odd[k]
X[k+N/2] = Even[k] - W · Odd[k]

Dove W è un complesso esponenziale (una rotazione nel piano complesso). Gli stessi due sub-risultati ti danno due punti di uscita. Ecco perché l'algoritmo è "veloce" — riutilizza ogni calcolo due volte.

L'implementazione di PinePaper è una cartella di testo Cooley-Tukey radix-2 DIT (decisione nel tempo). 40 linee di JavaScript. L'abbiamo scritto da zero piuttosto che importare una biblioteca perché volevamo che gli studenti fossero in grado di leggere la fonte e capire ogni linea.

Che cosa quei bar Mean

Quando si vede un analizzatore di spettro — barre che saltano alla musica — ogni barra rappresenta un cestino di frequenza. L'altezza è la grandezza (forza) di quella frequenza nel segnale corrente.

• Un'onda di sine pura produce una barra alta alla sua frequenza e nient'altro.
• Un'onda quadrata produce barre all'armonica fondamentale e ogni strana (3 °, 5 °, 7 °...), diminuendo come 1 / n. Ecco perché le onde quadrate suonano "buzzy" — contengono energia ad alta frequenza che i sintoni puri non fanno.
• Il rumore bianco produce barre di altezza approssimativamente uguale ovunque. Ogni frequenza è presente con pari probabilità.
• Una voce umana produce un fondamentale (il passo che senti) più formanti — picchi risonanti dalla forma del tuo tratto vocale che distinguono le vocali.

Finestra: Perché i bordi

C'e' una fregatura. Il FFT assume che il segnale si ripeta per sempre. Ma il nostro campione è finito — inizia e si ferma. Se il segnale non è a zero a entrambi gli endpoint, il cutoff brusco crea contenuti ad alta frequenza artificiali. Questo si chiama "perdita dello spettro".

La correzione: moltiplicare il segnale per una funzione finestra che tocca senza intoppi a zero ai bordi. Finestre comuni:

• Hann (cosine bell): buon scopo generale, perde qualche risoluzione di frequenza
• Hamming: simile a Hann ma non raggiunge lo zero ai bordi, soppressione leggermente migliore del lobo laterale
• Blackman: lobo principale più stretto, migliore soppressione del lobo laterale, perde più risoluzione di frequenza

La scelta è sempre un tradeoff tra la risoluzione di frequenza (come precisamente è possibile identificare una frequenza) e la perdita spettrale (quanto sanguina energia nei contenitori vicini). Non c'è una finestra perfetta. Questa è una conseguenza del principio di incertezza — non si può avere una conoscenza arbitrariamente precisa del tempo e della frequenza contemporaneamente.

Dove il FFT vive

Interagisci costantemente con i risultati FFT:

• MP3 e compressione AAC: trasformare il dominio audio in frequenza, scartare le frequenze sotto la soglia dell'udito, comprimere ciò che rimane. La trasformazione è l'intera base di compressione audio perduta.
• Compressione JPEG: la versione 2D (DCT) trasforma i blocchi da 8×8 pixel a dominio di frequenza, quantizza componenti ad alta frequenza. Ecco perché gli artefatti JPEG appaiono come blocchi.
• WiFi e 5G: la codifica OFDM divide i dati in molti sub-carrieri di frequenza. Il FFT converte tra la trasmissione del tempo-dominio e i simboli di dati del dominio di frequenza.
• MRI imaging: il segnale grezzo di uno scanner MRI è nello spazio di frequenza. L'inverso FFT ricostruisce l'immagine spaziale. Letteralmente: ogni risonanza che hai mai visto è una trasformazione inversa di Fourier.
• Shazam: calcola lo spettrogramma (FFT su finestre scorrevoli), estrae i picchi, corrisponde al modello contro un database. Il FFT è il primo passo nel riconoscere ogni canzone.

Un algoritmo di 60 anni, in tasca, che corre miliardi di volte al giorno.

Prova

Aprire PinePaper, selezionare il generatore Spectrum Analyzer. Genera un'onda quadrata. Guarda le barre — vedrai le armoniche dispari che cadono come 1 / n. Passare a una segatura — ora tutte le armoniche sono presenti, cadendo come 1 / n. Passare a rumore — spettro piatto, ogni frequenza altrettanto probabile.

Modificare la funzione finestra. Guarda come Hann leviga lo spettro al costo di picchi più ampi. Passare a Blackman — picchi più stretti ma sidelobe più bassi.

Non stai leggendo del FFT. Stai misurando i segnali e osservando cosa rivela la trasformazione. Questa è la differenza tra conoscenza e comprensione.

Referenze

• Brigham, E.O. (1988). The Fast Fourier Transform e le sue applicazioni. Prentice Hall.
• Cooley, J.W. & Tukey, J.W. (1965). Un algoritmo per il calcolo della macchina della serie complessa Fourier. Matematica della Computazione, 19(90), 297-301.
• Fourier, J. (1822). Théorie analytique de la chaleur. Parigi: Firmin Didot.
• Harris, F.J. (1978). Sull'uso di Windows per l'analisi armonica con la trasformazione discreta Fourier. Procedimenti dell'IEEE, 66(1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). Elaborazione dei segnali in tempo libero (3 ° ed.). Prentice Hall.
• Shannon, C.E. (1949). Comunicazione nella Presenza del Rumore. Procedimenti dell'IRE, 37(1), 10-21.
• Smith, S.W. (1997). La guida dello scienziato e dell'ingegnere alla lavorazione digitale dei segnali. California Technical Publishing.
• Wang, A., et al. (2003). Un Algoritmo di Ricerca Audio Industriale-Strength. Procedure di ISMIR 2003. (l'algoritmo di impronte audio di Shazam.)
• Wallace, G.K. (1991). Il JPEG Still Picture Compression Standard. Comunicazioni dell'ACM, 34(4), 30-44.

---

PinePaper's FFT è un'implementazione Cooley-Tukey radix-2 con finestre Hann, Hamming e Blackman, oltre a filtri low-pass e high-pass. Provalo gratuitamente a pinepaper.studio/editore.