FFT-Algorithmus (PHP)

FFTW ist eine in C verfasste Bibliothek zur schnellen Berechnung der Diskreten Fouriertransformation (DFT) in einer oder mehreren Dimensionen für reellwertige oder komplexe Signale. Die Bibliothek wurde am MIT Laboratory for Computer Science von M. Frigo und St. G. Johnson entwickelt. Das Algebraprogramm MATLAB enthält ab Version 6 mit FFTW (Fastest Fourier Transform in the West) das zurzeit beste FFT-Programmpaket. In FFTW sind erste Ansätze zu einer architekturadaptiven FFT-Berechnung realisiert. In einer Initialisierungsphase wird ein „Berechnungsplan“ ermittelt, der die FFT-Berechnung an die Speicherhierarchie des jeweiligen Rechners anpasst. Abb. 1 zeigt einen Vergleich der normierten Laufzeiten der FFT-Berechnung von MATLAB 6 mit MATLAB 5.3 und der in C geschriebenen FFTW-Version. Wie man sieht, ist MATLAB 6 für lange Vektoren mehr als doppelt so schnell wie MATLAB 5.3. Der durch die Integration von FFTW in MATLAB entstandene Overhead ist dafür verantwortlich, dass die „reine“ C-Implementierung ein etwas besseres Laufzeitverhalten aufweist [1].

Exemplarisch sei hier der Algorithmus von Cooley und Tukey aus dem Jahre 1965 genannt. Der Algorithmus arbeitet in-place, das heißt, es wird nur ein Feld erforderlich sein. Anfangs befinden sich dort die Elemente des Signalvektors s, und im selben Feld sind nach Beendigung der Transformation die Fourierkoeffizienten s' zu finden.

s' = DFT· s

Eigentlich werden im Butterfly die Koeffizienten gar nicht normiert. Um aber zum selben Ergebnis wie mit Gleichung (1) zu gelangen, wird hier die symmetrische Normierung voreingestellt.

Ihre Eingabe:

Ihr Ergebnis (01:29:56):

FFT, symmetrische Normierung

Eingabe:
 0.000

Resultat:
 0.000

Rechenzeit:

zirka 0.571 s

Literatur:

Ernst Haunschmid, Herbert Karner, Stefan Katzenbeisser, Christoph Überhuber: Effizientes Lösen numerischer Probleme mit MATLAB 6. Institut für Angewandte und Numerische Mathematik an der TU Wien, 2000
C-Bibliothek

Dr. O. Hochmuth
Rainer Schnabel
20.10.2008, 18:19:10