Eine Algorithmusfamilie, die die diskrete Fourier-Transformation (DFT) einer Folge effizient berechnet, indem Symmetrien, Periodizitäten und rekursive Faktorisierung der DFT-Matrix ausgenutzt werden, wodurch die Rechenkomplexität in typischen Fällen von O(N^2) auf O(N log N) sinkt.

Prinzip

Verwende Divide-and-Conquer-Faktorisierung (Radix-Zerlegungen, Butterfly-Operationen) und Symmetrien der komplexen Exponentialfunktionen, um Zwischenresultate (Twiddle-Faktoren) wiederzuverwenden und redundante Berechnungen der DFT zu minimieren.

Demonstration

Berechnung des Frequenzspektrums eines gleichmäßig abgetasteten Signals der Länge N=2^k mittels einer Radix-2-FFT-Implementierung, die O(N log N) komplexe Operationen ausführt und Echtzeitspektralanalyse ermöglicht.

Fehlanwendung

Anwendung einer Standard-FFT auf nichtgleichmäßig abgetastete Daten ohne Resampling oder auf Sequenzen mit großer numerischer Dynamik ohne Skalierung, was Aliasing oder starke Rundungsfehler und irreführende spektrale Schätzungen verursachen kann.

Konsequenz

Ermöglicht schnelle Faltung durch Multiplikation im Frequenzbereich, Echtzeitspektralschätzung und großskalige Signal- und Bildverarbeitung, die mit naiver DFT unpraktisch wäre.

Umkehrung

Direkte Auswertung der diskreten Fourier-Transformation durch Summation von N^2 komplexen Exponentialen (naive DFT), dies ist zwar konzeptionell einfach, aber für große N rechentechnisch unpraktisch.

Abgrenzung

Setzt gleichmäßig abgetastete Daten voraus und erfordert typischerweise faktorierbare Längen (Potenz von zwei für optimale Radix-Implementierungen); numerische Stabilität und Genauigkeit hängen von Implementierungsdetails und Datenskalierung ab; spezialisierte Algorithmen (NFFT) existieren für nichtgleichmäßige Abtastung.

Semantische Spannung

Spannung zu spezialisierten Transformationen (Wavelets, kurzzeitige Fourier-Transformation, NFFT): Die FFT ist optimal für globale Frequenzanalyse bei gleichmäßiger Abtastung, eignet sich jedoch weniger, wenn lokale Zeit-Frequenz-Auflösung oder nichtgleichmäßige Abtastung erforderlich ist.

Synthese

Eine Klasse von Algorithmen, die gleichmäßig abgetastete Zeit-/Raumsequenzen durch rekursive Nutzung der DFT-Struktur effizient in Frequenzkoeffizienten überführen und dabei den Rechenaufwand drastisch reduzieren.