Fast-Fourier-Transformation

Author: Hans Lohninger

Der große Nachteil der diskreten Fourier-Transformation (DFT) ist deren Langsamkeit. DFT ist so langsam, dass eine Fourier-Transformation in Echtzeit unrealistisch ist, ausgenommen sehr leistungsstarke Computer. Die Entdeckung des Algorithmus zur Fast-Fourier-Transformation (FFT) durch Cooley und Tukey brachte eine grundlegende Änderung mit sich. Während die DFT ungefähr N² Multiplikationen (N ist die Anzahl der Datenpunkte) benötigt, braucht die FFT nur 0.5*N*log₂ (N) Schritte. Das führt zum Beispiel für 1024 Datenpunkte zu einer Verbesserung der Konversionsgeschwindigkeit um den Faktor(!) 200.

Beachten Sie, dass die FFT keine Näherung ist sondern nur eine sehr viel schnellere Art der Ausführung einer DFT ist. Die FFT liefert also die selben Ergebnisse mit der selben Präzision wie die DFT.

Das Grundprinzip hinter der FFT ist, eine N-Punkte-DFT in zwei N/2-Punkte-DFTs aufzuspalten. Das ist wegen der Periodizität der komplexen Exponentialfunktion möglich. Die Aufspaltung einer Transformation in zwei kleinere kann so lange ausgeführt werden, bis nur noch zwei Datenpunkte übrig sind (wenn man als Zahl der Datenpunkte eine ganzzahlige Potenz von zwei voraussetzt). Mehr Details über diesen Algorithmus finden Sie in zahlreichen Publikationen.