##  [Schnelle Fourier-Transformation (FFT)](/de/node/60672) 

 Definition

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

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

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

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

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

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

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

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

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.