Hvad FFT faktisk viser dig

Spørgsmålet

Spil en akkord på et klaver - sige, C og E sammen. Dit øre hører én lyd. Men denne lyd er to frekvenser overlejret: 261,6 Hz og 329,6 Hz. Din cochlea adskiller dem fysisk - forskellige hårceller genlyd ved forskellige frekvenser, sender tydelige signaler til din hjerne.

Den Fast Fourier Transform gør det samme, men med tal i stedet for hårceller. Giv det et signal (en sekvens af amplitude prøver over tid) og det returnerer en liste over frekvenser og deres styrker. Det svarer: * * hvilke frekvenser er til stede, og hvor meget af hver? * *

Hvad er faktisk Happening

Et signal, der udtages med tiden, er en liste over numre: amplituden ved hvert prøvepunkt. En 1-anden optagelse ved 44,100 Hz er 44,100 numre. Disse tal beskriver signalet i * * tidsdomænet * * - amplitude som en funktion af tiden.

FFT konverterer dette til * * frekvensdomænet * * - amplitude som funktion af frekvens. Samme information, forskellig repræsentation. Som at skifte mellem kartesiske og polære koordinater: Intet skabes eller ødelægges, kun re- udtrykkes.

Den matematiske kerne: Hvert periodisk signal kan skrives som en sum af sinus og cosinbølger ved forskellige frekvenser. Dette er Fouriers sætning (1807). FFT beregner koefficienterne for dette beløb - hvor meget af hver frekvens der er i signalet.

Hvorfor "hurtigt"

Den naive måde at beregne en Fourier transformere kræver N ² operationer for N prøver. For 1024 prøver er det omkring 1 million operationer. Cooley- Tukey algoritmen (1965) reducerer dette til N · log (N) - omkring 10.000 operationer for samme input. En 100x speedup. For en million prøver, speedup er 50,000x.

Tricket: split N- punkt omdanne til to N / 2- punkt transformerer, rekursivt. Dette kræver, at N er en effekt på 2 (eller du pad med nuller). Hver split halverer problemet. Operationen "sommerfugl" kombinerer halvdelene:

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

Hvor W er en kompleks eksponentiel (en rotation i det komplekse plan). De samme to sub- resultater giver dig to outputpunkter. Derfor er algoritmen "hurtig" - den genbruger hver beregning to gange.

PinePaper implementering er en lærebog Cooley- Tukey radix-2 DIT (decimation i tid). 40 linjer JavaScript. Vi skrev det fra bunden i stedet for at importere et bibliotek, fordi vi ønskede, at eleverne skulle kunne læse kilden og forstå hver linje.

Hvad disse barer betyder

Når du ser en spektrumanalysator - barer hoppe til musik - hver bar repræsenterer en frekvens bin. Højden er størrelsen (styrken) af denne frekvens i det aktuelle signal.

• • • En ren sinus bølge * * producerer en høj bar på sin frekvens og intet andet.
• • • En firkantet bølge * * producerer barer på det grundlæggende og hver ulige harmoniske (3., 5., 7....), faldende som 1 / n. Derfor lyder firkantede bølger "buzzy" - de indeholder højfrekvensenergi, som rene sinker ikke gør.
• • • Hvid støj * * producerer stænger af omtrent samme højde overalt. Hver frekvens er til stede med samme sandsynlighed.
• • • En menneskelig stemme * * producerer en grundlæggende (pitch du hører) plus formanter - resonant toppe fra formen af din vokal kanal, der adskiller vokaler.

Windowing: Hvorfor Edges Matter

Der er en hage. FFT antager, at signalet gentager sig for evigt. Men vores prøve er begrænset - den starter og stopper. Hvis signalet ikke tilfældigvis er på nul ved begge endepunkter, den pludselige cutoff skaber kunstig høj frekvens indhold. Dette kaldes * * spektral lækage * *.

Fixet: multiplicere signalet med en * * vinduesfunktion * *, der tapper glat til nul ved kanterne. Almindelige vinduer:

• • • Hann * * (cosine klokke): godt generelt formål, mister en vis frekvens opløsning
• • • Hamming * *: ligner Hann, men ikke når nul i kanterne, lidt bedre sideelobe undertrykkelse
• • • Blackman * *: smallere hovedlap, bedre sideelobe undertrykkelse, mister mere frekvensopløsning

Valget er altid en afvejning mellem frekvensopløsning (hvor præcist du kan identificere en frekvens) og spektrallækage (hvor meget energi bløder ind i nærliggende dåser). Der er ikke noget perfekt vindue. Dette er en konsekvens af usikkerhedsprincippet - man kan ikke have vilkårligt præcist kendskab til både tid og frekvens samtidigt.

Hvor FFT bor

Du interagerer konstant med FFT-resultater:

• • • MP3 og AAC kompression * *: omdanne lyd til frekvens domæne, kassere frekvenser under høringstærskelen, komprimere hvad der er tilbage. Transformere er hele grundlaget for lossy lyd komprimering.
• • • JPEG komprimering * *: 2D version (DCT) transformerer 8 × 8 pixel blokke til frekvens domæne, kvantificerer høj frekvens komponenter. Det er derfor JPEG artefakter vises som blokke.
• • • WiFi og 5G * *: OFDM kodning deler data på tværs af mange frekvens underbærere. FFT konverterer mellem tids- domæne transmission og frequency- domæne data symboler.
• • • MRI imaging * *: det rå signal fra en MRI scanner er i frekvensområde. Den inverse FFT rekonstruerer det rumlige billede. Bogstaveligt talt: Hver MRI du nogensinde har set er en omvendt Fourier forvandling.
• • • Shazam * *: beregner spektrogram (FFT over skydevinduer), udtrækker toppe, matcher mønstret mod en database. FFT er det første skridt i genkendelse af alle sange.

En 60-årig algoritme, i lommen, kører milliarder af gange om dagen.

{{widget: function- plot}}

Prøv det

Åbn PinePaper, vælg Spectrum Analyzer generator. Generér en firkantet bølge. Se på barerne - du vil se de ulige harmoniske falder ud som 1 / n. Skift til en savtand - nu alle harmoniske er til stede, falder ud som 1 / n. Skift til støj - fladt spektrum, hver frekvens lige sandsynligt.

Ændr vinduesfunktionen. Se hvordan Hann udjævner spektret på bekostning af bredere toppe. Skift til Blackman - smallere toppe, men lavere sidestykker.

Du læser ikke om FFT. Du måler signaler og observerer, hvad transformationen afslører. Det er forskellen på at vide og forstå.

Henvisninger

• Brigham, E.O. (1988). * Den hurtige Fourier transformere og dens applikationer *. Prentice Hall.
• Cooley, J.W. & Tukey, J.W. (1965). En algoritme til maskinberegning af Complex Fourier-serien. * Matematik af Computation *, 19 (90), 297-301.
• Fourier, J. (1822). * Théorie analytique de la chaleur *. Paris: Firmin Didot.
• Harris, F.J. (1978). Om brugen af Windows til Harmonisk Analyse med Diskret Fourier Transform. * Arbejdet i IEEE *, 66 (1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). * Discrete- Time Signal Processing * (3rd ed.). Prentice Hall.
• Shannon, C.E. (1949). Kommunikation i nærvær af støj. * Arbejdet ved IRE *, 37 (1), 10-21.
• Smith, S.W. (1997). * The Scientist and Engineers Guide to Digital Signal Processing *. Californien Technical Publishing.
• Wang, A., et al. (2003). En industriel styrke Audio Search Algithm. * Arbejdet i ISMIR 2003 *. (Shazams lydfingeraftryk algoritme.)
• Wallace, G.K. (1991). JPEG stadig billede Kompression Standard. * Kommunikation af ACM *, 34 (4), 30-44.

---

• PinePaper 's FFT er en Cooley- Tukey radix-2 implementering med Hann, Hamming og Blackman Windowing, plus lavpas- og højpasfiltre. Prøv det gratis på [pinepaper.studio / editor] (/editor). *