Infos Home | Impressum | Original Artikel & Autoren Liste

Schnelle Fourier-Transformation

Die schnelle Fourier-Transformation (englisch fast Fourier transform, daher häufig FFT) ist ein Algorithmus zur schnellen Berechnung der Werte aus der diskreten Fourier-Transformation (DFT). Die Beschleunigung gegenüber der direkten Berechnung beruht auf der Vermeidung mehrfacher Berechnung sich gegenseitig aufhebender Terme.

Inhalt
1 Algorithmus
2 Anwendung
3

Algorithmus

Die Voraussetzung zur Anwendung einer FFT (im Gegensatz zur DFT) ist, dass der Eingangsvektor, auf den die FFT angewendet werden soll, der Länge einer Potenz von zwei entspricht (Radix-2-FFT).

Der Rechenaufwand reduziert sich von

auf

Bei gilt für die Effizienz der FFT n*ld(n)=64, das heißt die FFT ist schon für kurze Folgen schneller als DFT (n*n=256). Bei n=2^12=4096 benötigt die DFT schon 341 mal mehr Zeit, als die FFT.

Die Struktur des Datenflusses kann dabei durch einen Butterfly-Graphen beschrieben werden, der die Reihenfolge der Berechnung festlegt.

Zur Abschätzung der Rechenleistung für die Berechnung eines Algorithmus siehe auch Komplexitätstheorie.

Anwendung


Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz.