Schnelle Fourier Transformation (FFT)
Die schnelle Fourier Transformation (engl. Fast Fourier Transform, FFT) ist in der Informatik (besonders in der Signalverarbeitung) ein sehr wichtiger Algorithmus zur schnellen Berechnung der diskreten Fourier Transformation (DFT). Um die FFT zu erklären muss vorher noch ein Wenig über die DFT gesagt werden. Ich setze in diesem Artikel außerdem grundlegende Kenntnisse der komplexen Zahlen voraus.
Diskrete Fourier Transformation
Die diskrete Fourier Transformation ist sehr schnell erklärt (wenn man sie nicht von der allgemeinen Fourier Transformation herleitet). Sie ist eine Abbildung . Sie bildet also komplexe Vektoren auf komplexe Vektoren ab. Wir definieren uns zunächst
Man nennt auch die primitive n-te Einheitswurzel. Zur Erinnerung: ist die Länge unseres „Eingabevektors“. OK, jetzt definieren wir uns noch eine Matrix . Dies geschieht ganz einfach:
Wir nennen die Fouriermatrix. Anders gesprochen ist dies gerade die Vandermonde-Matrix , aber das ist erstmal egal.
Schließlich definieren wir uns die diskrete Fourier Transformation. Haben wir einen Vektor , so ist die Fourier Transformation definiert durch
Sie ist also nichts weiter als eine Matrix-Vektor-Multiplikation der Fouriermatrix mit dem Vektor . In der Literatur findet man auch oft die Formel
Man sieht, dies ist nichts anderes als die ausgeschriebene Matrix-Vektor-Multiplikation.
Beispiel
Wie sieht sowas aus? Sagen wir, wir wollen den Vektor transformieren. Es ist also . Die 4-te primitive Einheitswurzel ist . Konstruktion der Fouriermatrix ergibt
Die Rechnung ist nun wirklich trivial und es ist . Dies ist schon unser transformierter Vektor!
Inverse Diskrete Fourier Transformation
Jetzt stellt sich die Frage wie wir den Vektor wieder zurücktransformiert bekommen. Klar dürfte sein, dass eine Multiplikation mit der inversen Fouriermatrix wieder den ursprünglichen Vektor liefern wird. Aufgrund der Eigenschaften der primitiven Einheitswurzeln und der Symmetrie von ist die Inverse Matrix gegeben durch
Dabei bezeichnet die konjugiert komplexe Zahl von . Die Rücktransformation ist also nun auch wieder nur eine Matrix-Vektor-Multiplikation, nämlich
That’s it! In unserem Beispiel von oben wechseln wir in der Matrix einfach das Vorzeichen vor dem Imaginärteil jeder komplexen Zahl, und ziehen vor die Matrix und erhalten
womit dann folgt.
Schnelle Fourier Transformation
Die Schnelle Fourier Transformation ist ein Teile & Herrsche Algorithmus zur Berechnung der DFT. Im O-Kalkül ergibt sich, dass die DFT wegen der Matrix-Vektor-Multiplikationen einen Aufwand von hat. Der Algorithmus der FFT schafft die gleichen Berechnungen in , was eine wesentliche Verbesserung darstellt! Kleiner Haken an der Sache ist jedoch, dass die Länge der zu transformierenden Vektoren eine Zweierpotenz sein muss. In den meisten Fällen ist das aber egal, da man einfach den Vektor mit Nullen auffüllen kann bis seine Länge gerade die einer Zweierpotenz entspricht.
Das Verfahren
Wie schon angesprochen handelt es sich bei der FFT um einen Teile & Herrsche Algorithmus, welcher sich am einfachsten rekursiv formulieren lässt. Wir möchten also den transformierten Vektor berechnen. Dabei sind und mit . Wir können den Vektor also aufspalten, und zwar in die Vektoren , der gerade die Komponenten von mit geradem Index und der die Komponenten von mit ungeradem Index enthält. Ausgeschrieben heißt das für
Uff, was wurde hier gemacht? Zunächst einmal berechnen sich die geraden Komponenten von ja dadurch, dass wir die geraden Zeilen der Matrix mit multiplizieren. Dies lässt sich als Summe schreiben. Die Summe können wir in der Mitte teilen und erhalten damit die dritte Zeile. Jetzt nutzen wir aus, dass eine primitive Einheitswurzel ist. Dann gilt nämlich
Damit kann man also die Summe zusammenziehen (wie oben in der letzten Zeile gezeigt)! Substituiere nun und ( ist also m-te primitive Einheitswurzel) und wir erhalten
Das ist also nichts anderes als die Fouriertransformation des Vektors . Der Vektor hat gerade die Länge .
Machen wir das gleiche Spiel mit den ungeraden Indizes von :
Die Umformungen von Zeile 3 nach 4 in der rechten Summe ausführlich:
Ok, wir können also wieder und substituieren und erhalten
Wieder ist dies nichts anderes als die Fouriertransformation des Vektors .
Diese Zerlegung lässt sich jetzt rekursiv weiter durchführen bis wir Vektoren der Länge 1 haben. Die Fouriertransformierte eines Vektors der Länge 1 ist jedoch der Vektor selbst (Es gilt ja bei dass ist), somit haben wir auch eine rekursive „Abbruchbedingung“.
Zusammengefasst geht man also so vor:
- Berechne temporäre Vektoren und aus . Diese haben jeweils nurnoch halbe Länge!
- Berechne rekursiv die Fouriertransformierten der Vektoren und . Sie seien mit und bezeichnet. Beachte dass wegen der halben Länge der Vektoren die -te primitive Einheitswurzel benutzt werden muss!
- Füge und reißverschlussartig zu zusammen, so dass die geraden Indizes von gerade und die ungeraden Indizes von gerade entsprechen.
Dieses Verfahren hat nun eine Komplexität von nurnoch !
Inverse Schnelle Fourier Transformation
Die Umkehrung der FFT ist wieder eine FFT. Wie wir jedoch im Kapitel der DFT gesehen haben muss diesmal die Matrix benutzt werden. Wir benutzen also die konjugiert komplexen Einheitswurzeln statt und müssen die Endergebnisse noch mit multiplizieren. Aufwand: Wieder .
Das Butterfly Schema
Das oben angegebene Verfahren lässt sich algorithmisch sehr schön implementieren, aber will man die FFT auf dem Papier durchführen ist es etwas umständlich, da man viele temporäre Vektoren ausrechnen muss. Abhilfe schafft da das hochbedenkliche Butterfly Schema. Als Butterfly bezeichnet man einen Graph bei dem jeder Knoten einen numerischen Wert enthält der sich als gewichtete Summe der eingehenden Kanten zusammensetzt. Beispiel:
Beim Butterfly Schema fängt man so an, dass man sich erst den Vektor jeweils in ungerade und gerade Komponenten aufspaltet bis man lauter Vektoren der Länge 1 erhält. Diese schreibt man dann untereinander. Nehmen wir zum Beispiel den Vektor
Aufspalten jeweils in gerade und ungerade Teilvektoren ergibt diesen Baum
Wir schreiben nun einfach die Blätter des Baums untereinander und erhalten somit den Anfang.
Im -ten Schritt des Schemas werden nun die Rechenoperationen wie folgt dargestellt durchgeführt:
Wir haben auf der rechten Seite den zusammengesetzten Vektor aus den beiden Vektoren halber Länge die sich auf der linken Seite befinden. Man sieht hier schön die reißverschlussartige Verschränkung. In unserem Beispiel sähe das komplette Schema folgendermaßen aus:
Da unser Vektor die Länge 4 hatte, haben wir folgende Werte für die Potenzen von benutzt:
Das Ergebnis ist also
That’s it!
Weiteres zur FFT
- http://de.wikipedia.org/wiki/DFT
Diskrete Fourier Transformation auf Wikipedia - http://de.wikipedia.org/wiki/Schnelle_Fourier-Transformation
Schnelle Fourier Transformation auf Wikipedia - http://www.iti.fh-flensburg.de/lang/algorithmen/fft/fft.htm
Schnelle Fourier Transformation - http://www.kgw.tu-berlin.de/statisch/lehre/skript/ds/node36.html
Schnelle Fourier Transformation mit guter Illustration des Butterfly Schemas - http://www.mathematik.uni-trier.de/~schulz/Prosem-0405/Arenz.pdf Etwas andere Einführung zur FFT