Was die FFT Ihnen tatsächlich zeigt

Die Frage

Spielen Sie einen Akkord auf einem Klavier - sagen Sie C und E zusammen. Dein Ohr hört ein Geräusch. Aber dieser Ton besteht aus zwei überlagerten Frequenzen: 261,6 Hz und 329,6 Hz. Ihre Cochlea trennt sie physisch - verschiedene Haarzellen schwingen auf verschiedenen Frequenzen mit und senden unterschiedliche Signale an Ihr Gehirn.

Die Fast Fourier Transformation macht dasselbe, aber mit Zahlen anstelle von Haarzellen. Geben Sie ihm ein Signal (eine Sequenz von Amplitudenproben im Laufe der Zeit) und es gibt eine Liste von Frequenzen und deren Stärken zurück. Es antwortet: **Welche Frequenzen sind vorhanden und wie viel von jedem? **

Was tatsächlich passiert

Ein Signal, das über die Zeit abgetastet wird, ist eine Liste von Zahlen: die Amplitude an jedem Abtastpunkt. Eine 1-Sekunden-Aufzeichnung bei 44.100 Hz ist 44.100 Zahlen. Diese Zahlen beschreiben das Signal im Zeitbereich - Amplitude als Funktion der Zeit.

Die FFT wandelt dies in den Frequenzbereich - Amplitude als Funktion der Frequenz um. Gleiche Informationen, unterschiedliche Repräsentation. Wie das Umschalten zwischen kartesischen und polaren Koordinaten: Nichts wird geschaffen oder zerstört, nur wieder ausgedrückt.

Der mathematische Kern: Jedes periodische Signal kann als Summe von Sinus- und Kosinuswellen mit unterschiedlichen Frequenzen geschrieben werden. Das ist Fouriers Theorem (1807). Die FFT berechnet die Koeffizienten dieser Summe - wie viel von jeder Frequenz im Signal ist.

Warum "schnell"

Der naive Weg, eine Fourier-Transformation zu berechnen, erfordert N2-Verfahren für N Proben. Für 1024 Proben sind das etwa 1 Million Operationen. Der Cooley-Tukey-Algorithmus (1965) reduziert dies auf N·log2(N) - etwa 10.000 Operationen für den gleichen Eingang. Ein 100x Speedup. Für eine Million Samples ist die Beschleunigung 50.000x.

Der Trick: Teilen Sie die N-Punkt-Transformation in zwei N/2-Punkt-Transformationen, rekursiv. Dies erfordert, dass N eine Potenz von 2 ist (oder Sie Pad mit Nullen). Jeder Split halbiert das Problem. Die "Butterfly" -Operation kombiniert die Hälften:

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

Wobei W ein komplexes Exponential ist (eine Rotation in der komplexen Ebene). Die gleichen zwei Sub-Ergebnisse geben Ihnen zwei Ausgabepunkte. Deshalb ist der Algorithmus "schnell" - er verwendet jede Berechnung zweimal.

Die Implementierung von PinePaper ist ein Lehrbuch Cooley-Tukey radix-2 DIT (Dezimierung in der Zeit). 40 Zeilen JavaScript. Wir haben es von Grund auf neu geschrieben, anstatt eine Bibliothek zu importieren, weil wir wollten, dass die Schüler die Quelle lesen und jede Zeile verstehen können.

Was diese Bars bedeuten

Wenn Sie einen Spektrumanalysator sehen - Balken, die zur Musik springen - stellt jeder Balken einen Frequenzbinder dar. Die Höhe ist die Größe (Stärke) dieser Frequenz im Stromsignal.

• ** Eine reine Sinuswelle** erzeugt einen hohen Balken in seiner Frequenz und nichts anderes.
• ** Eine quadratische Welle erzeugt Balken an der fundamentalen und jeder ungeraden Harmonischen (3., 5., 7. ...), abnehmend als 1/n. Deshalb klingen Rechteckwellen "buzzy" - sie enthalten hochfrequente Energie, die reine Sinus nicht enthalten.
• ** Weißes Rauschen** erzeugt überall Balken von ungefähr gleicher Höhe. Jede Frequenz ist mit gleicher Wahrscheinlichkeit vorhanden.
• ** Eine menschliche Stimme ** erzeugt eine grundlegende (die Tonhöhe, die Sie hören) plus Formanten - resonante Spitzen aus der Form Ihres Stimmtrakts, die Vokale unterscheiden.

Fenster: Warum die Kanten wichtig sind

Es gibt einen Haken. Die FFT nimmt an, dass sich das Signal für immer wiederholt. Aber unsere Stichprobe ist endlich - sie beginnt und stoppt. Wenn das Signal an beiden Endpunkten nicht auf Null liegt, erzeugt der abrupte Cutoff künstlichen Hochfrequenzinhalt. Das nennt man spektrale Leckage.

Der Fix: Multiplizieren Sie das Signal mit einer ** Fensterfunktion**, die sich an den Rändern glatt auf Null verjüngt. Gemeinsame Fenster:

• Hann (Cosinusglocke): guter allgemeiner Zweck, verliert einige Frequenzauflösung
• Hamming: ähnlich wie Hann, erreicht aber an Kanten nicht Null, etwas bessere Seitenlappenunterdrückung
• Blackman: schmaler Hauptlappen, bessere Sidelobe Unterdrückung, verliert mehr Frequenzauflösung

Die Wahl ist immer ein Kompromiss zwischen Frequenzauflösung (wie genau Sie eine Frequenz identifizieren können) und spektraler Leckage (wie viel Energie in benachbarte Bins blutet). Es gibt kein perfektes Fenster. Dies ist eine Folge des Ungewissheitsprinzips - Sie können nicht willkürlich genaue Kenntnis von Zeit und Häufigkeit gleichzeitig haben.

Wo die FFT lebt

Sie interagieren ständig mit FFT-Ergebnissen:

• MP3 und AAC-Komprimierung: Umwandlung von Audio in Frequenzbereich, Verwerfen von Frequenzen unterhalb der Hörschwelle, Komprimieren von Resten. Die Transformation ist die gesamte Basis der verlustbehafteten Audiokomprimierung.
• JPEG-Komprimierung: Die 2D-Version (DCT) transformiert 8 × 8 Pixelblöcke in den Frequenzbereich, quantisiert Hochfrequenzkomponenten. Deshalb erscheinen JPEG-Artefakte als Blöcke.
• WiFi und 5G: Die OFDM-Kodierung teilt Daten auf viele Frequenz-Subträger. Die FFT konvertiert zwischen Zeitdomänenübertragung und Frequenzdomänendatensymbolen.
• MRT-Bildgebung: Das Rohsignal eines MRT-Scanners befindet sich im Frequenzraum. Die inverse FFT rekonstruiert das räumliche Bild. Wörtlich: Jede MRT, die Sie jemals gesehen haben, ist eine inverse Fourier-Transformation.
• Shazam: berechnet das Spektrogramm (FFT über Schiebefenster), extrahiert Peaks, vergleicht das Muster mit einer Datenbank. Die FFT ist der erste Schritt, um jeden Song zu erkennen.

Ein 60 Jahre alter Algorithmus in Ihrer Tasche, der Milliarden Mal pro Tag läuft.

Versuchen Sie es

Öffnen Sie PinePaper, wählen Sie den Spectrum Analyzer Generator. Generieren Sie eine quadratische Welle. Schauen Sie sich die Balken an - Sie werden die ungeraden Harmonischen als 1 / n abfallen sehen. Wechseln Sie zu einem Sägezahn - jetzt sind alle Harmonischen vorhanden und fallen als 1 / n ab. Wechseln Sie zu Rauschen - flaches Spektrum, jede Frequenz gleich wahrscheinlich.

Ändern Sie die Fensterfunktion. Beobachten Sie, wie Hann das Spektrum auf Kosten breiterer Spitzen glättet. Wechseln Sie zu Blackman - schmalere Spitzen, aber niedrigere Seitenlappen.

Sie lesen nicht über die FFT. Sie messen Signale und beobachten, was die Transformation offenbart. Das ist der Unterschied zwischen Wissen und Verstehen.

Referenzen

• Brigham, E.O. (1988). Die schnelle Fourier-Transformation und ihre Anwendungen. Prentice Hall.
• Cooley, J.W. & Tukey, J.W. (1965). Ein Algorithmus zur Maschinenberechnung komplexer Fourier-Serien. Mathematik der Berechnung, 19(90), 297-301.
• Fourier, J. (1822). Théorie analytique de la chaleur. Paris: Firmin Didot.
• Harris, F.J. (1978). Über die Verwendung von Windows für die harmonische Analyse mit der diskreten Fourier-Transformation. Verfahren der 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 in Anwesenheit von Lärm. Verfahren des IRE, 37(1), 10-21.
• Smith, S.W. (1997). *Der Leitfaden für Wissenschaftler und Ingenieure zur digitalen Signalverarbeitung *. California Technical Publishing.
• Wang, A., et al. (2003). Ein Industrial-Strength Audio Search Algorithmus. Verfahren von ISMIR 2003. (Shazams Audio-Fingerabdruck-Algorithmus.)
• Wallace, G.K. (1991). Der JPEG Still Picture Compression Standard. Mitteilungen der ACM, 34(4), 30-44.

---

• Die FFT von PinePaper ist eine Cooley-Tukey Radix-2-Implementierung mit Hann-, Hamming- und Blackman-Fenstern sowie Tiefpass- und Hochpassfiltern. Probieren Sie es kostenlos unter pinepaper.studio/editor.*