Vad FFT faktiskt visar dig - Fourier Transform förklaras (Svenska)

Frågan

Spela ett ackord på ett piano - säg, C och E tillsammans. Ditt öra hör ett ljud. Men det ljudet är två frekvenser överlag: 261,6 Hz och 329,6 Hz. Din cochlea skiljer dem fysiskt - olika hårceller resonerar vid olika frekvenser, skickar distinkta signaler till din hjärna.

Fast Fourier Transform gör samma sak, men med siffror istället för hårceller. Ge det en signal (en sekvens av amplitudeprover över tiden) och den returnerar en lista över frekvenser och deras styrkor. Svar: ** Vilka frekvenser finns, och hur mycket av varje?**

Vad händer faktiskt

En signal provtagen över tiden är en lista över siffror: amplituden vid varje provpunkt. En 1 sekunders inspelning på 44 100 Hz är 44 100 nummer. Dessa siffror beskriver signalen i **-tidsdomän ** - amplitud som en funktion av tid.

FFT konverterar detta till **frekvent domän ** - amplitud som en funktion av frekvens. Samma information, olika representation. Som att växla mellan kartesiska och polära koordinater: ingenting skapas eller förstörs, bara återuttryckt.

Den matematiska kärnan: varje periodisk signal kan skrivas som en summa av sinus och kosinvågor vid olika frekvenser. Detta är Fouriers teorem (1807). FFT beräknar koefficienterna i den summan - hur mycket av varje frekvens är i signalen.

Varför "snabbt"

Det naiva sättet att beräkna en Fourier transform kräver N2 operationer för N-prover. För 1024 prover är det cirka 1 miljon operationer. Algoritmen Cooley-Tukey (1965) minskar detta till N·log2 (N) - cirka 10 000 operationer för samma ingång. En 100x speedup. För en miljon prover är hastigheten 50.000x.

Tricket: dela N-punkten förvandlas till två N/2-punkts transformer, återkommande. Detta kräver att N är en kraft på 2 (eller du pad med nollor). Varje del halverar problemet. "Fjäril" -operationen kombinerar halvorna:

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

Där W är en komplex exponentiell (en rotation i det komplexa planet). Samma två underresultat ger dig två utgångspunkter. Det är därför algoritmen är "snabb" - den återanvänder varje beräkning två gånger.

PinePaper implementering är en lärobok Cooley-Tukey radix-2 DIT (beslut i tid). 40 rader av JavaScript. Vi skrev det från början istället för att importera ett bibliotek eftersom vi ville att eleverna skulle kunna läsa källan och förstå varje rad.

Vad dessa barer betyder

När du ser en spektrumanalysator - barer som hoppar till musik - representerar varje bar en frekvensbin. Höjden är storleken (styrka) av den frekvensen i den nuvarande signalen.

** En ren sinvåg** ger en hög bar vid dess frekvens och inget annat.
En kvadratvåg producerar staplar på den grundläggande och varje udda harmoniska (3: e, 5: e, 7: e ...), minskar som 1/n. Det är därför kvadratvågor låter "buzzy" - de innehåller högfrekvent energi som rena synder inte.
** Vitt brus** producerar barer av ungefär lika höjd överallt. Varje frekvens är närvarande med lika stor sannolikhet.
En mänsklig röst ger en grundläggande (höjdpunkten du hör) plus formanter - resonanttoppar från formen av din sångkanal som skiljer vokaler.

Fönster: Varför kanterna materia

Det finns en fångst. FFT antar att signalen upprepas för alltid. Men vårt prov är ändligt - det börjar och slutar. Om signalen inte råkar vara noll vid båda ändpunkterna, skapar den plötsliga cutoff artificiellt högfrekvent innehåll. Detta kallas spectral läckage.

Fix: multiplicera signalen med en **-fönsterfunktion* som smakar smidigt till noll vid kanterna. Vanliga fönster:

Hann* (kosinklocka): bra allmänt syfte, förlorar en viss frekvensupplösning
*Hamming: liknar Hann men når inte noll vid kanter, något bättre suppression
Blackman: smalare huvudlob, bättre suppression, förlorar mer frekvensupplösning

Valet är alltid en avvägning mellan frekvensupplösning (hur exakt du kan identifiera en frekvens) och spektral läckage (hur mycket energi blöder i angränsande bin). Det finns inget perfekt fönster. Detta är en följd av osäkerhetsprincipen - du kan inte ha godtyckligt exakt kunskap om både tid och frekvens samtidigt.

Där FFT lever

Du interagerar med FFT-resultat hela tiden:

*MP3 och AAC-komprimering: omvandla ljud till frekvensdomän, kassera frekvenser under hörseltröskeln, komprimera vad som återstår. Omvandlingen är hela grunden för förlust av ljudkomprimering.
** JPEG-komprimering*: 2D-versionen (DCT) omvandlar 8 x 8 pixelblock till frekvensdomän, kvantiserar högfrekventa komponenter. Det är därför JPEG artefakter visas som block.
*WiFi och 5G: OFDM-kodning delar data över många frekvensunderbärare. FFT konverterar mellan tidsdomänöverföring och frekvensdomändatasymboler.
*MRI imaging: den råa signalen från en MR-skanner är i frekvensutrymme. Den omvända FFT rekonstruerar den rumsliga bilden. Bokstavligen: varje MRI du någonsin sett är en omvänd Fourier-transform.
*Shazam: beräknar spektrogrammet (FFT över skjutfönster), extraherar toppar, matchar mönstret mot en databas. FFT är det första steget i att känna igen varje låt.

En 60-årig algoritm, i fickan, kör miljarder gånger per dag.

Prova det

Öppna PinePaper, välj Spectrum Analyzer generator. Generera en fyrkantig våg. Titta på barerna - du ser de udda harmonierna som faller av som 1/n. Växla till en sågtooth - nu är alla harmonier närvarande, faller av som 1/n. Växla till buller - platt spektrum, varje frekvens lika sannolikt.

Ändra fönsterfunktionen. Se hur Hann slätar spektrumet på bekostnad av bredare toppar. Växla till Blackman - smalare toppar men lägre sidobar.

Du läser inte om FFT. Du mäter signaler och observerar vad transformen avslöjar. Det är skillnaden mellan att veta och förstå.

Referenser

Brigham, E.O. (1988). The Fast Fourier Transform och dess tillämpningar*. Prentice Hall.
Cooley, JW & Tukey, JW (1965). En algoritm för maskinberäkning av komplexa Fourier-serien. * Matematik för beräkning*, 19(90), 297-301.
Fourier, J. (1822). Théorie analytique de la chaleur*. Paris: Firmin Didot.
Harris, F.J. (1978). Användning av Windows för harmonisk analys med diskret Fourier Transform. IEEE*, 66.1, 51-83.
Oppenheim, AV & Schafer, RW (2009). Discrete-Time Signal Processing (3rd ed.). Prentice Hall.
Shannon, C.E. (1949). Kommunikation i närvaro av buller. Proceedings of the IRE, 37(1), 10-21.
Smith, S.W. (1997). Forskaren och ingenjörens guide till digital signalbehandling* Kalifornien teknisk publicering.
Wang, A., et al. (2003). En branschstyrka Audio Search Algorithm. Förfaranden för ISMIR 2003*. (Shazams ljud fingeravtryck algoritm.)
Wallace, GK (1991). JPEG Still Picture Compression Standard. Kommunikation av ACM*, 34(4), 30-44.

*PinePaper FFT är en Cooley-Tukey-radix-2-implementering med Hann, Hamming och Blackman-fönster, plus lågpass- och högpassfilter. Prova det gratis på [pinepaper.studio/editor] (/editor)