Was ist Schnelle Fourier-Transformation (FFT)?

Familie von Algorithmen, die die diskrete Fourier-Transformation (DFT) mit wenigen Operationen exakt berechnen. Das bekannteste Verfahren (der Cooley-Tukey-Algorithmus) zerlegt eine N-Punkt-DFT wiederholt in DFTs halber Größe und fasst gemeinsame Berechnungen zusammen; die Zahl der Operationen sinkt dadurch von etwa N² nach der Definition auf etwa N log₂N. Für N = 1024 ist das etwa 1/100. Am einfachsten ist der Algorithmus, wenn die Punktzahl eine Zweierpotenz ist, es gibt aber auch Verfahren für andere Größen. Neben der Spektralanalyse wird sie für Modulation und Demodulation bei OFDM und für die schnelle Berechnung langer Faltungen verwendet.

Japanische Bezeichnung: 高速フーリエ変換(FFT)

„Schnelle Fourier-Transformation (FFT)“ kommt in 4 Übungsfragen aus 2 Themen vor, z. B. Grundlagen der digitalen Signalverarbeitung, Grundlagen der Funkkommunikation.

Fachgebiet: Grundlagen der digitalen Signalverarbeitung

Warum sie schnell ist

Zerlegt man eine N-Punkt-DFT in zwei N/2-Punkt-DFTs der Abtastwerte mit geraden und ungeraden Nummern, lässt sich das ursprüngliche Ergebnis allein durch Multiplikation mit Drehfaktoren e^(−j2πk/N) sowie Addition und Subtraktion zusammensetzen. Wiederholt man dies, entstehen log₂N Stufen mit jeweils etwa N Operationen, insgesamt also eine Größenordnung von N log₂N. Wegen seiner Form heißt dieses Paar aus Addition und Subtraktion Butterfly-Operation.

Wie viel schneller

Das Verhältnis ist N/log₂N: 1024 ÷ 10 = 102,4 für N = 1024 und 65.536 ÷ 16 = 4096 für N = 65.536. Je größer die Punktzahl, desto größer der Gewinn; das macht die FFT unverzichtbar für Echtzeit-Spektrumanzeigen und für Anwendungen wie Kommunikationsempfänger, die viele DFTs hintereinander berechnen.

Faltung mit der FFT

Die Faltung zweier Folgen wird im Frequenzbereich zu einer Multiplikation. Transformiert man beide mit der FFT, multipliziert sie und transformiert mit der inversen FFT zurück, lässt sich die Faltung eines langen FIR-Filters mit weniger Operationen berechnen als direkt. Die Multiplikation von DFTs entspricht jedoch einer zyklischen Faltung; die Längen müssen deshalb durch Zero-Padding angepasst werden, damit an den Enden nichts auf die andere Seite umläuft.

Jetzt üben: Fragen zu Schnelle Fourier-Transformation (FFT)

Eine N-Punkt-DFT erfordere nach ihrer Definition etwa N² Operationen, mit der FFT (schnelle Fourier-Transformation) etwa N log₂N Operationen. Welcher Wert kommt für N = 1024 der Verringerung der Operationszahl durch die FFT am nächsten?

AEtwa auf 1/10
BEtwa auf 1/100
CEtwa auf 1/1000

Antwort und Erläuterung anzeigen

Antwort: B. Etwa auf 1/100

N² = 1024² ≈ 1,05 Millionen und N log₂N = 1024 × 10 = 10.240; das Verhältnis ist N/log₂N = 1024 ÷ 10 = 102,4, also etwa 1/100. Mit wachsendem N wird der Unterschied größer; bei N = 65.536 beträgt die Verringerung etwa 1/4096. Die FFT senkt den Aufwand, indem sie eine DFT wiederholt in DFTs halber Größe zerlegt und gemeinsame Berechnungen zusammenfasst.

Häufige Fragen

Muss die Punktzahl der FFT eine Zweierpotenz sein?

Nein. Eine Zweierpotenz ist oft der einfachste und schnellste Fall, es gibt aber auch Mixed-Radix-FFTs, die die Größe in Faktoren wie 3 oder 5 zerlegen, und Verfahren für Primzahlgrößen; gängige Bibliotheken berechnen beliebige Größen. Wird eine Zweierpotenz bevorzugt, kann die Punktzahl durch Zero-Padding erhöht werden.

Liefert die FFT dieselben Ergebnisse wie die DFT?

Sie berechnet dieselben Werte, daher stimmen die Ergebnisse bis auf Rundungsfehler überein. Die FFT ist keine Näherung, sondern ein Algorithmus, der die Berechnung so umordnet, dass dasselbe Ergebnis schneller entsteht.

„Schnelle Fourier-Transformation (FFT)“ in den Erläuterungen

Die FFT senkt den Aufwand, indem sie eine DFT wiederholt in DFTs halber Größe zerlegt und gemeinsame Berechnungen zusammenfasst.
Eine N-Punkt-DFT erfordere nach ihrer Definition etwa N² Op…
Zero-Padding dient dazu, die Lage von Spitzen leichter ablesbar zu machen oder die Punktzahl für die FFT auf eine Zweierpotenz zu bringen.
An ein Signal mit 256 Punkten werden 768 Nullen angehängt (…
Die Verarbeitung erfolgt effizient mit einer inversen schnellen Fourier-Transformation (IFFT) im Sender und einer schnellen Fourier-Transformation (FFT) im Empfänger; OFDM wird in WLAN, 4G LTE, 5G NR, beim digitalen terrestrischen Rundfunk und anderswo eingesetzt.
Welche Beschreibung von OFDM (orthogonales Frequenzmultiple…
Da der CP eine Kopie des Symbolendes ist, erscheinen außerdem auch verspätete Wellen im von der FFT verarbeiteten Intervall als periodisches Signal, sodass die Orthogonalität der Unterträger erhalten bleibt.
Was ist bei OFDM der Hauptzweck des zyklischen Präfixes (CP…