Hva FFT faktisk viser deg

Spørsmålet

Spill en akkord på et piano - si C og E sammen. Øret ditt hører én lyd. Men den lyden er to frekvenser superimponert: 261,6 Hz og 329,6 Hz. Din cochlea fysisk skiller dem - forskjellige hårceller resonere ved forskjellige frekvenser, sende forskjellige signaler til hjernen din.

Fast Fourier Transform gjør det samme, men med tall i stedet for hårceller. Gi det et signal (en sekvens av amplitudeprøver over tid) og det returnerer en liste over frekvenser og deres styrker. Det svarer: ** hvilke frekvenser er tilstede, og hvor mye av hver

Hva som faktisk skjer

Et signalprøvet over tid er en liste over tall: amplituden ved hvert prøvepunkt. En 1 sekunds opptak på 44.100 Hz er 44.100 tall. Disse tallene beskriver signalet i ** tidsdomene** — amplitude som en funksjon av tid.

FFT konverterer dette til frekvente domene - amplitude som funksjon av frekvens. Samme informasjon, forskjellig representasjon. Som å bytte mellom kartesisk og polarkoordinater: ingenting er skapt eller ødelagt, bare re-uttrykt.

Den matematiske kjernen: hvert periodisk signal kan skrives som en sum av sinus- og cosinusbølger ved forskjellige frekvenser. Dette er Fouriers teori (1807). FFT beregner koeffisientene til det summet — hvor mye av hver frekvens er i signalet.

Hvorfor "Fast"

Den naive måten å beregne en Fourier transformasjon krever N2 operasjoner for N-prøver. For 1024 prøver er det ca. 1 million operasjoner. Coley-Tukey-algoritmen (1965) reduserer dette til N·log2(N) — rundt 10.000 operasjoner for samme inngang. 100x hastighet. For en million prøver er hastigheten 50 000x.

Tricket: Del N-punktet forvandles til to N/2-punkt forvandler, rekursivt. Dette krever at N er en effekt på 2 (eller du puder med nuller). Alle deler problemet. "Butterfly-operasjonen kombinerer halvdelene:

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

Når W er en kompleks eksponentiell (en rotasjon i det komplekse planet). De samme to underresultatene gir deg to utgangspunkter. Derfor er algoritmen " rask — gjenbruker den hver beregning to ganger.

PinePapers implementering er en lærebok Cooley-Tukey radix-2 DIT (beslutning i tide). 40 linjer av JavaScript. Vi skrev det fra grunn av i stedet for å importere et bibliotek fordi vi ønsket at studentene skulle kunne lese kilden og forstå hver linje.

Hva disse barene betyr

Når du ser en spekteranalysator - barer hoppe til musikk - hver bar representerer en frekvenskasse. Høyden er størrelsen (styrke) på den frekvensen i det aktuelle signalet.

• *En ren sinusbølge produserer en høy bar i sin frekvens og ingenting annet.
• ** En firkantet bølge ** produserer barer på det grunnleggende og hver merkelig harmonisk (3., 5., 7....), synker som 1/n. Det er derfor firkantede bølger lyd - buzzy - de inneholder høyfrekvent energi som rene siner ikke gjør.
• **Hvit støy ** produserer barer med omtrent samme høyde overalt. Hver frekvens er til stede med like sannsynlighet.
• ** En menneskelig stemme** produserer et grunnleggende (høydepunktet du hører) pluss formanter - resonante topper fra formen av vokalkanalen din som skiller vokaler.

Vindu: Hvorfor kantene

Det er en fangst. FFT antar signalet gjentar seg for alltid. Men vår prøve er finite - det starter og stopper. Hvis signalet ikke skjer å være på null ved begge endepunktene, skaper det bråe avklippet kunstig høyfrekvent innhold. Dette kalles spektral lekkasje.

Reparasjonen: multiplisere signalet med en vindufunksjon som tapper jevnt til null i kantene. Vanlige vinduer:

• Hann (kosinklokke): god generell hensikt, mister noen frekvensoppløsning
• Hamming: ligner på Hann men når ikke null ved kanter, noe bedre sidelobe undertrykkelse
• Blackman: smalere hovedlobe, bedre sidelobe undertrykkelse, mister mer frekvensoppløsning

Valget er alltid et avslag mellom frekvensoppløsning (hvor nøyaktig du kan identifisere en frekvens) og spektrallekkasje (hvor mye energi blømer i nabobøyler). Det er ingen perfekt vindu. Dette er en konsekvens av usikkerhetsprinsippet - du kan ikke ha vilkårlig nøyaktig kunnskap om både tid og frekvens samtidig.

Hvor FFT bor

Du samhandler med FFT-resultater hele tiden:

• MP3 og AAC-komprimering: transformer lyd til frekvensdomene, kast frekvenser under hørselsterskelen, komprimer det som gjenstår. Transformasjonen er hele grunnlaget for tapsaktig lydkompresjon.
• JPEG-kompresjon: 2D-versjonen (DCT) forvandler 8×8-pikselblokker til frekvensdomene, kvantiserer høyfrekvente komponenter. Derfor vises JPEG-gjenstander som blokker.
• WiFi og 5G: ODDM-koding deler data på tvers av mange frekvensundervogner. FFT konverterer mellom tidsdomeneoverføring og frekvensdomenedatasymboler.
• MRI-avbildning: råsignalet fra en MRI-skanner er i frekvensrom. Den inverse FFT rekonstruerer det romlige bildet. Litterært: Hver MRI du noensinne har sett er en invers Fourier-transformasjon.
• Shazam: beregner spektrogrammet (FFT over glidende vinduer), trekker ut topper, matcher mønsteret mot en database. FFT er det første steget i å gjenkjenne hver sang.

En 60-årig algoritme i lommen kjører milliarder ganger om dagen.

}

Prøv det

Åpne PinePaper, velg Spectrum Analyzer generator. Opprette en firkantet bølge. Se på barene - du vil se de merkelige harmoniene faller av som 1/n. Bytt til en sagtann - nå er alle harmonier til stede, faller av som 1/n. Bytt til støy — flatt spekter, hver frekvens like sannsynlig.

Endre vindusfunksjonen. Se hvordan Hann jevner spekteret på bekostning av bredere topper. Bytt til Blackman - smalere topper, men lavere sidelober.

Du leser ikke om FFT. Du måler signaler og observerer hva transformasjonen avslører. Det er forskjellen mellom å vite og forstå.

Referanser

• Brigham, E.O. (1988). * Den raske Fourier Transformer og dens programmer*. Prentice Hall.
• Coley, J.W. & Tukey, J.W. (1965). En algoritme for maskinberegning av komplekse Fourier-serien. * Matematikk i beregning*, 19(90), 297-301.
• Fourier, J. (1822). Théorie analytique de la chaleur. Paris: Firmin Didot.
• Harris, F.J. (1978). Ved bruk av Windows for Harmonisk analyse med Discrete Fourier Transform. Prosedenser av IEEE, 66(1) 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). Discrete-Time Signal Processing (3. ed.). Prentice Hall.
• Shannon, e.Kr. (1949). Kommunikasjon i tilstedeværelsen av støy. Begreper av IRE, 37(1), 10-21.
• Smith (1997). Forskeren og ingeniørens guide til digital signalbehandling*. California Teknisk Forlag.
• Wang, A., et al. (2003). En industriell-sterkt lydsøk algoritme. Begreper av ISMIR 2003. (Shazams algoritme.)
• Wallace, G.K. (1991). JPEG stillbilde komprimering standard. Kommunikasjon av ACM, 34(4), 30-44.

---

PinePaper's FFT er en Cooley-Tukey radix-2 implementasjon med Han, Hamming og Blackman vindu, pluss lavpass og høypass filtre. Prøv det gratis på Pinepaper.studio/editor.