FFT-Algorithmus (PHP)
Fastest Fourier Transform in the West (FFTW)
ist eine in C verfasste Bibliothek zur schnellen Berechnung der Diskreten Fouriertransformation (DFT)
und verwandter Transformationen (DCT, ...)
in einer oder mehreren Dimensionen für reellwertige oder komplexwertige Signale. Die Bibliothek wurde
am MIT Laboratory for Computer Science
von M. Frigo und St. G. Johnson entwickelt.
Das Algebraprogramm MATLAB nutzt ab Version 6 mit FFTW
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].
Abb. 2 aus [3] zeigt eine DCT für ein Signal
der Länge 256. In Zeile 12 wird der oben genannte Plan initialisiert. Der Parameter
FFTW_MEASURE
veranlasst einen Test, bei dem mehrere verschiedene DCT-Algorithmen durchgerechnet werden. So wird
vor
der Laufzeit ein optimaler Algorithmus ermittelt. Da dieser Test etwas Zeit benötigt, sollte der Plan
nur ein einziges Mal beim Programmstart initialisiert werden. Um die Transformationen auszuführen (Zeile 17),
muss lediglich der Eingangsvektor mit aktuellen Abtastwerten gefüllt werden (Zeile 15). Der eingangs ermittelte
Plan dct wird dann immer wieder ausgeführt [3].
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: