Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren auf dem Ãœberlagerungssatz der DFT auf und funktioniert nur dann, wenn die Stützstellenzahl N eine Zweierpotenz ist. Das nachfolgende Bild verdeutlicht die von Cooley und Tukey entwickelte Methode – siehe auch[CT65]– für das Beispiel N = 8, wobei die Transformation vom Zeit– in den Frequenzbereich dargestellt ist.
Man erkennt aus dieser Darstellung:
Vor dem eigentlichen FFT-Algorithmus müssen die komplexen Eingangswerte d(0), …, d(N–1) umsortiert werden. Dies geschieht im grau hinterlegten Block Bitumkehroperation, der auf der nächsten Seite im Detail beschrieben wird.
Die Berechnung erfolgt in ld N = 3 Stufen, wobei in jeder Stufe genau N/2 = 4 prinzipiell gleiche Berechnungen mit unterschiedlichem Parameter μ (= Exponent des komplexen Drehfaktors) ausgeführt werden. Eine solche Basisoperation bezeichnet man auch als Butterfly.
Jeder Butterfly berechnet aus zwei Eingangsgrößen A und B, die im Allgemeinen komplex sind, die beiden Ausgangsgrößen A + B · wμ sowie A – B · wμ entsprechend der nachfolgenden Skizze.
Die komplexen Spektralkoeffizienten D(0), … , D(N–1) erhält man am Ausgang der letzten Stufe nach Division durch N. Wie in Aufgabe Z5.4 noch gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit – zum Beispiel für N = 1024 um mehr als den Faktor 100.
Die inverse DFT zur Berechnung der Zeitkoeffizienten aus den Spektralkoeffizienten lässt sich mit dem gleichen Algorithmus und nur geringfügigen Modifizierungen bewerkstelligen.
