Die Fast Fourier Transform (FFT) ist ein effizienter Algorithmus zur Berechnung der Diskreten Fourier Transform (DFT). Der Cooley-Tukey-Algorithmus ist die gängigste Methode zur Implementierung von FFT, die auf der rekursiven Zerlegung der DFT beruht.

Mathematische Basis von FFT

Die DFT wandelt eine Folge komplexer Zahlen in Frequenzkomponenten um und ist definiert als:

X(k) = Σn=0N-1 x(n) e-2πi kn/N

Dabei ist x(n) die Eingangssequenz, X(k) die Frequenzkomponente und N die Sequenzlänge.

Ableitung des Cooley-Tukey-Algorithmus

Der Cooley-Tukey-Algorithmus zerlegt die DFT in kleinere DFTs, indem er die Sequenz in gerade und ungerade Teile unterteilt:

X(k) = Σn=0N-1 x(n) e-2πi kn/N

die umgeschrieben werden können als:

X(k) = Σn=0N/2-1 x(2n) e-2πi 2n k/N + e-2πi k/N Σn=0N/2-1x(2n+1) e-2πi 2n k/N

Diese Trennung ermöglicht die rekursive Berechnung kleinerer DFTs, wodurch die Rechenkomplexität von O(N2) zu O(N log N) reduziert wird.

Anwendung des Algorithmus

Der FFT-Algorithmus wendet die rekursive Zerlegung wiederholt an, bis der Basisfall der Größe 1 erreicht ist.

WN(k) = e-2πi k/N

Diese Faktoren passen die Phase der kleineren DFTs während der Rekombination an, was eine effiziente Berechnung der vollständigen Transformation ermöglicht.