mini|Zeit-basierte Darstellung (oben) und Frequenz-basierte Darstellung (unten) desselben Signals, wobei die untere Darstellung aus der oberen durch Fouriertransformation gewonnen werden kann Die schnelle Fourier-Transformation (, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der diskreten Fourier-Transformation (DFT). Mit ihr kann ein zeitdiskretes Signal in seine Frequenzanteile zerlegt und dadurch analysiert werden.
Analog gibt es für die diskrete inverse Fourier-Transformation die inverse schnelle Fourier-Transformation (IFFT). Es kommen bei der IFFT die gleichen Algorithmen, aber mit konjugierten Koeffizienten zur Anwendung.
Die FFT hat zahlreiche Anwendungen im Bereich der Ingenieurwissenschaften, der Naturwissenschaften und der angewandten Mathematik. Außerdem kommt sie in Mobilfunktechnologien wie UMTS und LTE und bei der drahtlosen Datenübertragung zum Einsatz, etwa in der WLAN-Funknetztechnik.
Die FFT gehört zu den Teile-und-herrsche-Verfahren, sodass – im Gegensatz zur direkten Berechnung – zuvor berechnete Zwischenergebnisse wiederverwendet und dadurch arithmetische Rechenoperationen eingespart werden können.
Historisch wurde die erste Form des Algorithmus 1805 von Carl Friedrich Gauß entdeckt und zur Berechnung der Flugbahnen der Asteroiden (2) Pallas und (3) Juno verwendet. Zum ersten Mal publiziert wurde eine Variante des Algorithmus von Carl Runge im Jahre 1903 und 1905. Es folgten weitere Adaptionen, beispielsweise von Irving John Good um 1960. Das heute bekannteste Verfahren der Fouriertransformation wird James Cooley und John W. Tukey zugeschrieben, die es auf der Suche nach einem Algorithmus, um Kernwaffentests in seismografischen Daten schnell und effizient aufzuspüren, entdeckten und 1965 veröffentlichten.Ein Algorithmus für den WeltfriedenThe re-discovery of the fast Fourier transform algorithm Nach Cooley und Tukey hat es darüber hinaus zahlreiche weitere Verbesserungsvorschläge und Variationen gegeben, so etwa von Georg Bruun, C. M. Rader und Leo I. Bluestein.
Informelle Beschreibung des Algorithmus (Cooley und Tukey) Der Algorithmus von Cooley und Tukey ist ein klassisches Teile-und-herrsche-Verfahren. Voraussetzung für seine Anwendung ist, dass die Anzahl der Stützstellen bzw. Abtastpunkte eine Zweierpotenz ist.
Der Algorithmus basiert auf der Beobachtung, dass die Berechnung einer DFT der Größe 2n in zwei Berechnungen einer DFT der Größe n zerlegbar ist (über den Vektor mit den Einträgen der geraden bzw. der ungeraden Indizes), wobei die beiden Teilergebnisse nach der Transformation wieder zu einer Fouriertransformation der Größe 2n zusammenzufassen sind.
Da die Berechnung einer DFT der halben Länge nur ein Viertel der komplexen Multiplikationen und Additionen der originalen DFT benötigt und je nach Länge des Ausgangsvektors diese Vorschrift mehrfach hintereinander anwendbar ist, erlaubt die rekursive Anwendung dieser Grundidee schließlich eine Berechnung in Zeit; zur Einsparung von trigonometrischen Rechenoperationen können bei der FFT zusätzlich die Eigenschaften der Einheitswurzeln aus der Fouriermatrix ausgenutzt werden.
Algorithmus von Cooley und Tukey Die diskrete Fouriertransformation (DFT) eines Vektors der Dimension lautet
.
Die Einträge mit geraden Indizes werden notiert als
und deren DFT der Dimension als .
Entsprechend seien die Einträge mit ungeraden Indizes notiert als
mit DFT .
Dann folgt
Mit der Berechnung von und () ist sowohl als auch bestimmt. Der Rechenaufwand hat sich durch diese Zerlegung also praktisch halbiert.
Mathematische Beschreibung (allgemeiner Fall) In der Mathematik wird die schnelle diskrete Fouriertransformation in einem wesentlich allgemeineren Kontext behandelt:
Sei ein kommutativer unitärer Ring. In sei die Zahl eine Einheit (d. h. invertierbar); ferner sei eine -te Einheitswurzel mit . Zum Beispiel ist im Restklassenring mit , , d ungerade (das ist gleichbedeutend mit der Forderung „teilerfremd zu “), das Element eine solche Einheitswurzel, die entsprechende FFT wird im Schönhage-Strassen-Algorithmus verwendet.
Dann lässt sich im Modul zu die diskrete Fouriertransformierte mit
wie folgt optimiert berechnen:
Zunächst stellen wir die Indizes und wie folgt dyadisch dar: .
Damit haben wir folgende Rekursion: , .
Wegen
erhalten wir hieraus die diskrete Fouriertransformierte .
Eigenschaften Diese klassische Variante der FFT nach Cooley und Tukey ist im Gegensatz zur DFT nur durchführbar, wenn die Länge des Eingangsvektors einer Zweierpotenz entspricht. Die Anzahl der Abtastpunkte kann also beispielsweise 4, 8, 16, 32 usw. betragen. Man spricht hier von einer Radix-2-FFT. Andere Längen sind mit den unten angeführten alternativen Algorithmen möglich.
Aus obiger Rekursion ergibt sich folgende Rekursionsgleichung für die Laufzeit der FFT:
Hierbei beschreibt der Term den Aufwand, um die Ergebnisse mit einer Potenz der Einheitswurzel zu multiplizieren und die Ergebnisse zu addieren. Es werden N Paare von Zahlen addiert und N/2 Zahlen mit Einheitswurzeln multipliziert. Insgesamt ist f(N) also linear beschränkt:
Mit dem Master-Theorem ergibt sich eine Laufzeit von:
Die Struktur des Datenflusses kann durch einen Schmetterlingsgraphen beschrieben werden, der die Reihenfolge der Berechnung festlegt.
Die Aussage hinsichtlich der Höhe der Amplitude eines Signalanteils und dessen Frequenz unterliegt einer Unschärfe: Je enger man die Frequenzbetrachtung fasst, desto weniger ist der Wert der FFT für diese Frequenz genau. Eine Präzisierung ist nur mittels Ausdehnung der FFT mit mehr Stützstellen möglich. Eine Interpretation der Amplituden für Zwischenfrequenzen ist mittels Umrechnungen möglich.
Implementierung als rekursiver Algorithmus mini|hochkant=1.6|Rekursive Reduktion der FFT (hier Länge N=8) in zwei FFTs der Länge N/2. Die direkte Implementierung der FFT in Pseudocode nach obiger Vorschrift besitzt die Form eines rekursiven Algorithmus: Das Feld mit den Eingangswerten wird einer Funktion als Parameter übergeben, die es in zwei halb so lange Felder (eins mit den Werten mit geradem und eins mit den Werten mit ungeradem Index) aufteilt. Diese beiden Felder werden nun an neue Instanzen dieser Funktion übergeben. Am Ende gibt jede Funktion die FFT des ihr als Parameter übergebenen Feldes zurück. Diese beiden FFTs werden nun, bevor eine Instanz der Funktion beendet wird, nach der oben abgebildeten Formel zu einer einzigen FFT kombiniert und das Ergebnis wird an den Aufrufer zurückgegeben. Dies wird nun fortgeführt, bis das Argument eines Aufrufs der Funktion nur noch aus einem einzigen Element besteht (Rekursionsabbruch): Die FFT eines einzelnen Wertes ist (er besitzt sich selbst als Gleichanteil und keine weiteren Frequenzen) er selbst. Die Funktion, die nur noch einen einzigen Wert als Parameter erhält, kann also ganz ohne Rechnung die FFT dieses Wertes zurückliefern; die Funktion, die sie aufgerufen hat, kombiniert die beiden jeweils einen Punkt langen FFTs, die sie zurückerhält, die Funktion, die diese wiederum aufgerufen hat, die beiden 2-Punkte-FFTs, und so weiter.
Der Geschwindigkeitsvorteil der FFT gegenüber der DFT kann anhand dieses Algorithmus gut abgeschätzt werden: Um die FFT eines Elemente langen Vektors zu berechnen, sind bei Verwendung dieses Algorithmus Rekursionsebenen nötig. Dabei verdoppelt sich in jeder Ebene die Anzahl der zu berechnenden Vektoren, während sich deren Länge jeweils halbiert, so dass am Ende in jeder bis auf die letzte Rekursionsebene genau komplexe Multiplikationen und Additionen notwendig sind. Die Gesamtzahl der Additionen und Multiplikationen beträgt also . Im Gegensatz benötigt die DFT für denselben Eingangsvektor komplexe Multiplikationen und Additionen.
Implementierung als nichtrekursiver Algorithmus mini|hochkant=1.6|Beispiel einer (Radix-2) FFT der Länge N=8. In jeder der drei Ebenen wird zu jedem Element ein zweites (mit Vorfaktor) addiert. Die Implementierung eines rekursiven Algorithmus ist im Regelfall vom Ressourcenverbrauch her nicht ideal, da die vielen dabei notwendigen Funktionsaufrufe Rechenzeit und Speicher für das Merken der Rücksprungadressen benötigen. In der Praxis wird daher meist ein nichtrekursiver Algorithmus verwendet, der gegenüber der hier abgebildeten, auf einfaches Verständnis optimierten Form je nach Anwendung noch optimiert werden kann: Wenn im obigen Algorithmus zuerst die beiden Hälften des Feldes miteinander vertauscht werden, und dann die beiden Hälften dieser Hälften usw., dann ist das Ergebnis am Ende dasselbe, als würden alle Elemente des Feldes von 0 aufsteigend nummeriert werden und anschließend die Reihenfolge der Bits der Nummern der Felder umgekehrt. Nachdem die Eingangswerte solchermaßen umsortiert sind, bleibt nur noch die Aufgabe, die einzelnen kurzen FFTs von der letzten Rekursionsebene nach außen zu längeren FFTs zu kombinieren, z. B. in Form dreier ineinandergeschachtelter Schleifen: Die äußerste Schleife zählt die Rekursionsebene durch (von 0 bis N − 1). Die nächste Schleife zählt die FFT-Abschnitte durch, in der die FFT in dieser Rekursionsebene noch aufgeteilt ist. Der Zähler dieser Schleife wird im Folgenden als bezeichnet. Die innerste Schleife zählt das Element innerhalb eines FFT-Abschnittes (im Folgenden genannt) durch (von 0 bis ) In der innersten dieser Schleifen werden nun immer die beiden Samples mit den folgenden beiden Indizes:
über einen Schmetterlingsgraphen kombiniert:
Alternative Formen der FFT Neben dem oben dargestellten FFT-Algorithmus von Cooley und Tukey, auch Radix-2-Algorithmus genannt, existieren noch eine Reihe weiterer Algorithmen zur schnellen Fourier-Transformation. Die Varianten unterscheiden sich darin, wie bestimmte Teile des „naiven“ Algorithmus so umgeformt werden, dass weniger (Hochpräzisions-)Multiplikationen notwendig sind. Dabei gilt meist, dass die Reduktion in der Anzahl der Multiplikationen eine erhöhte Anzahl von Additionen sowie von gleichzeitig im Speicher zu haltenden Zwischenergebnissen hervorruft.
Im Folgenden sind übersichtsartig einige weitere Algorithmen dargestellt. Details und genaue mathematische Beschreibungen samt Herleitungen finden sich in der unten angegebenen Literatur.
Radix-4-Algorithmus mini|hochkant=1.8|Radix-4 Algorithmus (rechts) im Vergleich zum Radix-2 Algorithmus (links) auf N=16 Elementen. Der Radix-4-Algorithmus, und analog dazu der Radix-8-Algorithmus oder allgemein Radix-2N-Algorithmus, ist eine Weiterentwicklung des obigen Radix-2-Algorithmus. Der Hauptunterschied besteht darin, dass die Anzahl der zu verarbeitenden Datenpunkte 4, 8 bzw. 2N beträgt. Die Verarbeitungstruktur bleibt dabei gleich, nur dass in dem Schmetterlingsgraphen pro Element statt zweier Datenpfade vier bzw. acht und allgemein 2N Datenpfade miteinander verknüpft werden müssen. Der Vorteil besteht in einem weiter reduzierten Rechenaufwand und damit Geschwindigkeitsvorteil. So sind, verglichen mit dem obigen Algorithmus von Cooley und Tukey, bei dem Radix-4-Algorithmus ca. 25 % weniger Multiplikationen notwendig. Bei dem Radix-8-Algorithmus reduziert sich die Anzahl der Multiplikationen um ca. 40 %.
Nachteil dieser Verfahren ist die gröbere Struktur und ein aufwendigerer Programmcode. So lassen sich mit Radix-4-Algorithmus nur Blöcke der Längen 4, 16, 64, 256, 1024, 4096, … verarbeiten. Bei dem Radix-8-Algorithmus sind die Einschränkungen analog zu sehen.
Winograd-Algorithmus Bei diesem Algorithmus ist nur eine bestimmte, endliche Anzahl von Stützstellen der Anzahl möglich, nämlich: