FFT — Schnelle Fourier-Transformation einfach erklärt

Die FFT, also die schnelle Fourier-Transformation, ist eine schnelle Methode zur Berechnung der diskreten Fourier-Transformation (DFT). Wenn du mit gleichmäßig verteilten Stichproben beginnst, sagt dir die DFT, wie viel von jedem diskreten Frequenzmuster in diesen Stichproben enthalten ist.

Der wichtige Punkt ist: Die FFT verändert das Ergebnis nicht. Sie liefert dieselben DFT-Werte wie die direkte Formel, kommt aber mit deutlich weniger wiederholter Rechenarbeit dorthin.

FFT in einem Satz

Die FFT ist ein schnellerer Algorithmus für genau dieselben Werte im Frequenzbereich, die die DFT bereits definiert.

Was die DFT misst

Angenommen, du hast Stichproben $x_0, x_1, \dots, x_{N-1}$. Die DFT erzeugt Zahlen $X_0, X_1, \dots, X_{N-1}$, definiert durch

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

Jedes $X_k$ misst, wie stark die Daten zu einem diskreten Frequenzmuster passen.

Wenn die Stichproben bei einer Abtastrate $f_s$ gleichmäßig verteilt sind, dann beträgt der Abstand benachbarter Frequenz-Bins

$$\frac{f_s}{N}$$

Diese Bedingung ist wichtig. Ohne bekannte Abtastrate hast du zwar weiterhin DFT-Bins, aber du kannst sie nicht als physikalische Frequenzen wie Hertz beschriften.

Warum die FFT schneller ist

Eine FFT ist eine Familie von Algorithmen zur effizienten Berechnung der DFT. Der wichtigste Trick besteht darin, die Struktur in den komplexen Exponentialfaktoren wiederzuverwenden, statt fast identische Summen immer wieder von Grund auf neu zu berechnen.

Die am leichtesten vorstellbare Version ist die Radix-2-FFT. Sie funktioniert am natürlichsten, wenn $N$ eine Zweierpotenz ist, und zerlegt eine Transformation der Länge $N$ in zwei Transformationen der Länge $N/2$, bevor die Ergebnisse zusammengeführt werden.

Bei der direkten DFT wächst der Rechenaufwand in der Größenordnung von $N^2$. Bei gängigen FFT-Verfahren sinkt er auf ungefähr $N \log N$.

Genau dieser Unterschied macht FFTs in der Praxis so wichtig. Für kleine Eingaben können beide Methoden noch akzeptabel wirken. Für große Eingaben ist die FFT dramatisch schneller.

Wie die FFT die Arbeit aufteilt

Statt jede Stichprobe direkt mit jedem Frequenzmuster zu vergleichen, zerlegt die FFT das Problem in kleinere Transformationen und setzt sie dann mit Phasenfaktoren wieder zusammen.

Eine Standardzerlegung ist:

1. Lege die Stichproben mit geraden Indizes in eine Liste.
2. Lege die Stichproben mit ungeraden Indizes in eine andere Liste.
3. Berechne kleinere Transformationen für diese Listen.
4. Führe die beiden Hälften zusammen.

Das ist Divide-and-Conquer, angewendet auf die Frequenzanalyse.

4-Punkte-FFT-Beispiel

Betrachte das 4-Punkte-Signal

$$x = [1, 0, 1, 0]$$

Dieses Muster wechselt zwischen $1$ und $0$, daher erwarten wir eine gewisse Frequenzstruktur statt eines völlig flachen Ergebnisses.

Teile es in gerade und ungerade Indizes auf:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

Die 2-Punkte-DFT des geraden Teils ist

$$E = [2, 0]$$

und die 2-Punkte-DFT des ungeraden Teils ist

$$O = [0, 0]$$

Für eine 4-Punkte-FFT lautet der Kombinationsschritt

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

wobei

$$W_4 = e^{-i 2 \pi / 4}$$

Da $O_k = 0$ ist, ist die Kombination besonders einfach:

$$X = [2, 0, 2, 0]$$

Interpretieren wir nun das Ergebnis.

$X_0 = 2$ ist der Nullfrequenzterm und spiegelt daher den von null verschiedenen Mittelwert der Stichproben wider. Der von null verschiedene Wert bei $X_2$ erfasst in diesem 4-Punkte-Fall den alternierenden Teil des Musters. Wenn du zuerst den Mittelwert abziehst, verschwindet der Term $X_0$, und die alternierende Komponente tritt klarer hervor.

Dieses Beispiel ist klein, aber die Idee skaliert: Berechne kleinere Transformationen und kombiniere sie dann, statt jedes Mal die gesamte Summe neu aufzubauen.

Häufige FFT-Fehler

FFT und DFT als unterschiedliche Ergebnisse behandeln

Das sind sie nicht. Die FFT ist eine schnellere Methode zur Berechnung der DFT.

Bins zu früh als physikalische Frequenzen lesen

Die Bin-Positionen werden erst dann zu physikalischen Frequenzen, wenn der Stichprobenabstand bekannt ist. Wenn die Abtastrate $f_s$ ist, dann beträgt der Bin-Abstand bei gleichmäßig verteilten Stichproben $f_s/N$.

Annehmen, dass Zero-Padding neue Information hinzufügt

Zero-Padding kann ein Spektrum glatter aussehen lassen, weil es die zugrunde liegende Transformation feiner abtastet, aber es fügt keine neuen gemessenen Daten hinzu.

Signalvorbereitung ignorieren

Mittelwertentfernung, Fensterung und eine sorgfältige Wahl der Abtastung können sehr wichtig sein. Wenn diese Bedingungen ignoriert werden, kann die FFT-Ausgabe für die gegebenen Stichproben mathematisch korrekt sein, aber bei der Interpretation in die Irre führen.

Wo die FFT verwendet wird

Die FFT taucht überall dort auf, wo du schnelle Informationen aus dem Frequenzbereich aus abgetasteten Daten brauchst. Häufige Beispiele sind Spektralanalyse, Filterung, Bildverarbeitung, Schwingungsanalyse, das numerische Lösen von Differentialgleichungen und schnelle Berechnungen mit Polynomen oder Faltungen.

Der Grund ist praktisch: Viele Operationen werden einfacher oder schneller, nachdem man vom Stichprobenbereich in den Frequenzbereich gewechselt hat.

Probiere einen ähnlichen Fall aus

Nimm $8$ gleichmäßig verteilte Stichproben einer Sinuswelle über genau eine volle Periode und berechne die DFT mit einem Taschenrechner oder einem Skript. Füge dann einen konstanten Offset hinzu und vergleiche die neue Ausgabe. Der größere Wert bei $X_0$ ist eine einfache Möglichkeit zu sehen, was die FFT voneinander trennt.