FFT-Algorithmus (PHP)

Fastest Fourier Transform in the West 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:

Signaldatei s:

oder Signal s:


Ihr Ergebnis:



Fatal error:  Uncaught Error: Call to undefined function ereg_replace() in /www/data-lst3/signal/hochmuth/.public_html/php/fftw.php:141
Stack trace:
#0 {main}
  thrown in /www/data-lst3/signal/hochmuth/.public_html/php/fftw.php on line 141