Schnelle Fourier-Transformation
Die Fast-Fourier-Transformation (FFT) ist ein Algorithmus zur schnellen Berechnung der Werte aus der diskreten Fourier-Transformation. Die Beschleunigung gegenüber der direkten Berechnung beruht auf der Vermeidung mehrfacher Berechnung sich gegenseitig aufhebender Terme.
Der Rechenaufwand reduziert sich somit von
zu
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle O(N)=\frac{N}{2}\cdot log_{2}(N) }
Die Struktur des Datenflusses kann dabei durch einen Butterfly-Graphen beschrieben werden, der die Reihenfolge der Berechnung festlegt.
Die Vorraussetzung 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).