Schnelle Fourier-Transformation

Eine schnelle Fourier-Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier-Transformation (DFT). Bei solchen Algorithmen handelt es sich um Teile-und-herrsche-Verfahren. Im Gegensatz zur direkten Berechnung verwendet eine schnelle Fourier-Transformation zuvor berechnete Zwischenergebnisse und spart arithmetische Rechenoperationen ein. Das bekannteste Verfahren wird James Cooley und John W. Tukey zugeschrieben, die es 1965 veröffentlichten. Genau genommen wurde eine Form des Algorithmus bereits 1805 von Carl Friedrich Gauß entworfen, der ihn zur Berechnung der Flugbahnen der Asteroiden (2) Pallas und (3) Juno verwendete. Zum ersten Male publiziert wurde eine Variante des Algorithmus von Carl Runge im Jahre 1903 und 1905. Darüber hinaus wurden eingeschränkte Formen des Algorithmus mehrfach vor Cooley und Tukey entwickelt, so z. B. von Irving John Good (1960). Nach Cooley und Tukey hat es darüber hinaus zahlreiche Verbesserungsvorschläge und Variationen gegeben, so etwa von Georg Bruun, C. M. Rader und Leo I. Bluestein.

Analog gibt es für die diskrete inverse Fourier-Transformation einen schnellen Algorithmus (inverse FFT – iFFT). Es kommen bei der iFFT identische Algorithmen mit anderen Koeffizienten in der Berechnung zur Anwendung.

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. Da die Anzahl solcher Punkte im Rahmen von Messverfahren jedoch im Allgemeinen frei gewählt werden kann, handelt es sich dabei nicht um eine gravierende Einschränkung.

Die Idee hinter dem Algorithmus ist es nun, dass die Berechnung einer DFT der Größe 2n nun zunächst in zwei Berechnungen der DFT der Größe n aufgeteilt – den Vektor mit den Einträgen der geraden bzw. der ungeraden Indizes – und die beiden Teilergebnisse nach der Transformation wieder zu einer Fouriertransformation der Größe 2n zusammengefügt werden können.

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 $\mathcal{O}(n \log n)$ Zeit; Zur Einsparung von trigonometrischen Rechenoperationen können bei der FFT zusätzlich die Eigenschaften der Einheitswurzeln aus der Fouriermatrix ausgenutzt werden.

Formelle Beschreibung des Algorithmus (Cooley und Tukey)

Zunächst sei in Erinnerung gerufen, dass die diskrete Fouriertransformation (im Folgenden DFT genannt) der Größe 2n durch folgende Formel definiert ist:

$f_m = \sum_{k=0}^{2n-1} x_k \;e^{-\frac{2\pi i}{2n} mk } \qquad m = 0,\dots,2n-1.$

Notieren wir die Einträge zu geraden Indizes als

x'₀ = x₀, x'₁ = x₂, …, x'_n-1 = x_2n-2

und bezeichnen deren Transformierte nach DFT der Größe n mit

f'₀, …, f'_n-1;

die Einträge zu ungeraden Indizes notieren wir entsprechend als

x"₀ = x₁, x"₁ = x₃, …, x"_n-1 = x_2n-1

und bezeichnen deren Transformierte nach DFT der Größe n mit

f"₀, …, f"_n-1.

Dann folgt:

$\begin{align} f_m & = \sum_{k=0}^{n-1} x_{2k } e^{-\frac{2\pi i}{2n} m(2k )} + \sum_{k=0}^{n-1} x_{2k+1} e^{-\frac{2\pi i}{2n} m(2k+1)} \\[0.5em] & = \sum_{k=0}^{n-1} x' _k e^{-\frac{2\pi i}{n} mk} + e^{-\frac{\pi i}{n}m} \sum_{k=0}^{n-1} x''_k e^{-\frac{2\pi i}{n} mk}\\[0.5em] & = \begin{cases} f'_m + e^{-\frac{\pi i}{n} m } f''_m & \text{ falls } m<n \\[0.5em] f'_{m-n} - e^{-\frac{\pi i}{n}(m-n)} f''_{m-n} & \text{ falls } m \geq n \end{cases} \end{align}$

Mathematische Beschreibung (allgemeiner Fall)

In der Mathematik wird die schnelle diskrete Fouriertransformation in einem wesentlich allgemeineren Kontext behandelt:

Sei R ein kommutativer unitärer Ring. In R sei die Zahl 2 = 1 + 1 eine Einheit (d. h. invertierbar); ferner sei $w \in R$ eine 2ⁿ-te Einheitswurzel mit $w^{2^{n-1}}=-1$. Zum Beispiel ist im Restklassenring

$R=\Z/N\Z$ mit $N=2^{d2^n}+1$, $d,n\in\N$, d ungerade (das ist gleichbedeutend mit der Forderung „teilerfremd zu 2ⁿ“),

das Element w = 2^2d eine solche Einheitswurzel, die entsprechende FFT wird im Schönhage-Strassen-Algorithmus verwendet.

Dann lässt sich im Modul $R^{2^n}$ zu $a\in R^{2^n}$ die diskrete Fouriertransformierte $\hat a$ mit

$\hat a_k = \sum_{j=0}^{2^n-1} a_j\cdot w^{j\cdot k}\qquad (k=0,\ldots, 2^n-1)$

wie folgt optimiert berechnen:

Zunächst stellen wir die Indizes j und k wie folgt dual dar:

$k = \sum_{\nu=0}^{n-1} k_\nu 2^\nu,\quad j = \sum_{\nu=0}^{n-1} j_\nu 2^{n-1-\nu}$.

Damit haben wir folgende Rekursion:

$A_0(j_0,\ldots,j_{n-1}) = a_j\qquad (j=0,\ldots,2^n-1)$,

$A_{r+1}(k_0,\ldots, k_r, j_{r+1},\ldots,j_{n-1}) = \sum_{j_r=0}^1 A_r(k_0,\ldots,k_{r-1},j_r,\ldots, j_{n-1})\cdot w^{j_r\cdot 2^{n-1-r}\cdot (k_r 2^r+\ldots+k_0 2^0)}$.

Wegen

$A_n(k_0,\ldots,k_{n-1}) = \hat a_k$

erhalten wir hieraus die diskrete Fouriertransformierte $\hat a\in R^{2^n}$.

Komplexität

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 1, 2, 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:

$T \left( N \right)= 2T \left( N/2 \right) + f (N)$

Hierbei beschreibt der Term f(N) 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:

$T \left( N \right)= 2T \left( N/2 \right) + \mathcal{O} \left(N\right)$

Mit dem Master-Theorem ergibt sich eine Laufzeit von:

$T \left( N \right)=\mathcal{O}(N \cdot \log(N))$

Die Struktur des Datenflusses kann durch einen Schmetterlingsgraphen beschrieben werden, der die Reihenfolge der Berechnung festlegt.

Implementierung als rekursiver Algorithmus

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 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 1 Punkt langen FFTs, die sie zurückerhält, die Funktion, die diese wiederum aufgerufen hat, die beiden 2-Punkte-FFTs, und so weiter.

$\mathrm{function}\ \operatorname{fft}(n,\vec f):$

$\mathrm{if}\ (n = 1)$

$\mathrm{return}\ \vec f$

$\mathrm{else} \$

$\vec g = \operatorname{fft}\left(\tfrac{n}{2},( f_0, f_2, \ldots ,f_{n-2})\right)$

$\vec u = \operatorname{fft}\left(\tfrac{n}{2}, (f_1, f_3, \ldots ,f_{n-1})\right)$

$\mathrm{for} \ k = 0 \ \mathrm{to} \ \tfrac{n}{2}-1$

$\begin{align} c_k = g_k + u_k \cdot e^{-2 \pi i k/n} \\ c_{k+n/2} = g_k - u_k \cdot e^{-2 \pi i k/n} \end{align}$

$\mathrm{return}\ \vec c$

Der Geschwindigkeitsvorteil der FFT gegenüber der DFT kann anhand dieses Algorithmus gut abgeschätzt werden:

• Um die FFT eines 2^N Elemente langen Vektors zu berechnen, sind bei Verwendung dieses Algorithmus n 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 n komplexe Multiplikationen und Additionen notwendig sind. Die Gesamtzahl der Additionen und Multiplikationen beträgt also $N\cdot2^N$
• Im Gegensatz benötigt die DFT für denselben Eingangsvektor (2^N)² komplexe Multiplikationen und Additionen.

Implementierung als nichtrekursiver Algorithmus

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 wenn alle Elemente des Felds von 0 aufsteigend nummeriert werden - und dann die Reihenfolge der Bits der Nummern der Felder umgekehrt wird.
• 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 Ebene durch (von 0 bis N-1).
  • Die nächste Schleife zählt die 2^{N − Ebene − 1} FFT-Abschnitte durch, in der die FFT in dieser Rekursionsebene noch aufgeteilt ist. Der Zähler dieser Schleife wird im Folgenden als „Abschnitt“ bezeichnet.
  • Die innerste Schleife zählt das Element innerhalb eines FFT-Abschnittes (im Folgenden ElementDesAbschnitts genannt) durch (von 0 bis 2^Ebene − 1)
  • In der innersten dieser Schleifen werden nun immer die beiden Samples mit den folgenden beiden Indizes:

$\scriptstyle links=2^{\mathrm{Ebene}+1}\cdot\mathrm{Abschnitt}+\mathrm{ElementDesAbschnitts}$

rechts = links + 2^Ebene

über einen Schmetterlingsgraph kombiniert:

$\begin{array}{rcl} x_{\mathrm{links,neu}}&=&x_{\mathrm{rechts}}-e^{-i\pi\frac{\mathrm{ElementDesAbschnitts}}{\mathrm{2^{\mathrm{Ebene}}}}}\cdot x_{\mathrm{links}}\\ x_{\mathrm{rechts,neu}}&=&x_{\mathrm{rechts}}+e^{-i\pi\frac{\mathrm{ElementDesAbschnitts}}{\mathrm{2^{\mathrm{Ebene}}}}}\cdot x_{\mathrm{links}}\end{array}$

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

Der Radix-4-Algorithmus ist, analog dazu der Radix-8-Algorithmus oder allgemein Radix-2^N-Algorithmus, eine Weiterentwicklung des obigen Radix-2-Algorithmus. Der Hauptunterschied besteht darin, dass die Anzahl der zu verarbeitenden Datenpunkte eine Potenz von 4 bzw. 4^N darstellen muss. Die Verarbeitungstruktur bleibt dabei gleich, nur dass in dem Schmetterlingsgraph pro Element statt zwei Datenpfade vier bzw. acht und allgemein 4^N 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 aufwendiger 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. Wäre in einer bestimmten Anwendung eine Blocklänge von beispielsweise 2048 Stützstellen ideal und damit auch der Speicherplatz gering zu halten, können diese schnelleren Algorithmen daher nicht eingesetzt werden. Es müsste dann ein größerer Speicher eingesetzt werden und der Rechenaufwand gesteigert werden.

Winograd-Algorithmus

Bei diesem Algorithmus ist nur eine bestimmte, endliche Anzahl von Stützstellen der Anzahl N möglich, nämlich:

$N = \prod^{m}_{j=1}N_j \qquad N_j \in \{2,3,4,5,7,8,9,16\}$

wobei alle Kombinationen von N_j zulässig sind, bei denen die verwendeten N_j relativ prim sind. Dadurch ist nur eine maximale Blocklänge von 5040 möglich. Die möglichen Werte für N liegen aber in dem Bereich bis 5040 dichter auf der Zahlengeraden als die Zweierpotenzen. Es ist damit eine bessere Feinabstimmung der Blocklänge möglich. Aufgebaut wird der Algorithmus aus Basisblöcken der DFT, deren Längen mit N_j korrespondieren. Bei diesem Verfahren wird zwar die Anzahl der Multiplikationen gegenüber dem Radix-2-Algorithmus reduziert, gleichzeitig steigt aber die Anzahl der notwendigen Additionen. Außerdem ist am Eingang und Ausgang jeder DFT eine aufwendige Permutation der Daten notwendig, die nach den Regeln des Chinesischen Restsatzes gebildet wird.

Diese Art der schnellen Fourier-Transformation besitzt in praktischen Implementierungen dann Vorteile gegenüber der Radix-2-Methode, wenn der für die FFT verwendete Mikrocontroller keine eigene Multipliziereinheit besitzt und für die Multiplikationen sehr viel Rechenzeit aufgewendet werden muss. In heutigen Signalprozessoren mit eigenen Multipliziereinheiten hat dieser Algorithmus keine wesentliche Bedeutung mehr.

Primfaktor-Algorithmus

Dieser FFT-Algorithmus basiert auf ähnlichen Ideen wie der Winograd-Algorithmus, allerdings ist die Struktur einfacher und damit der Aufwand an Multiplikationen höher als beim Winograd-Algorithmus. Der wesentliche Vorteil bei der Implementierung liegt in der effizienten Ausnutzung des zur Verfügung stehenden Speichers durch optimale Anpassung der Blocklänge. Wenn in einer bestimmten Anwendung zwar eine schnelle Multipliziereinheit verfügbar ist und gleichzeitig der Speicher knapp, kann dieser Algorithmus optimal sein. Die Ausführungszeit ist bei ähnlicher Blocklänge mit der des Algorithmus von Cooley und Tukey vergleichbar.

Goertzel-Algorithmus

Der Goertzel-Algorithmus stellt eine besondere Form zur effizienten Berechnung einzelner Spektralkomponenten dar und ist bei der Berechnung von nur einigen wenigen Spektralanteilen (engl. Bins) effizienter als alle blockbasierenden FFT-Algorithmen, welche immer das komplette diskrete Spektrum berechnen.

Chirp-z-Transformation

Bluestein-FFT-Algorithmus für Datenmengen beliebiger Größe (einschließlich Primzahlen).

Interpretation der Ergebnisse

Allgemein

Die FFT generiert aus n komplexen Eingangswerten n komplexe Ergebniswerte.

Der Betrag jedes dieser Ausgangswerte entspricht der Länge, und das Argument jedes Ausgangswerts dem Winkel eines Vektors zum Zeitpunkt t=0. Wenn man nun alle Vektoren mit den richtigen Geschwindigkeiten um den Nullpunkt kreisen lässt, - und sie zueinander addiert, erhält man wieder die Eingangswerte.

Die Frequenz, mit der der m-te Vektor des errechneten Spektrums dafür gegen den Uhrzeigersinn gedreht werden muss, ergibt sich durch die Formel

$f_{\mathrm{Drehung}}=\left\{\begin{array}{ll} f_{\mathrm{Sample}}\cdot \frac{m}{n}&;\ m\leq\frac{n}{2}\\[.5em] f_{\mathrm{Sample}}\cdot \frac{n-m}{n}&;\ m>\frac{n}{2} \end{array}\right.$

Vektoren müssen sich also mit einer um so höheren Frequenz drehen, je näher sie zur Mitte des Ergebnisses der FFT liegen, und jeder Vektor aus der oberen Hälfte des Ergebnisses dreht sich mit derselben Frequenz, aber in die umgekehrte Richtung, wie ein Vektor aus der unteren Hälfte des Ergebnisses dies tut. Zu erklären ist dies beispielsweise über das Nyquist-Shannon-Abtasttheorem, das besagt, dass Frequenzen über der halben Abtastfrequenz durch die Abtastung in den Frequenzbereich darunter gespiegelt werden; Zu beachten ist, dass aus zwei sich in unterschiedlicher Richtung, aber mit der gleichen Geschwindigkeit drehenden Vektoren alle Kreisbewegungen, Elliptischen Bewegungen, Sinus- oder Kosinusschwingungen mit der entsprechenden Frequenz zusammengesetzt werden können.

Für Eingangsdaten ohne Imaginärteil

Acht-Punkt FFT auf reellen Eingangsdaten

Damit aus den beiden mit derselben Frequenz kreisenden Vektoren ein Signal mit dem Imaginärteil 0 zusammengesetzt werden kann, muss der Realteil der beiden mit derselben Frequenz rotierenden Vektoren identisch sein, - und müssen die beiden Imaginärteile der Vektoren zusammen stets Null ergeben.

Hieraus folgt:

$\left.\begin{array}{rcr} \mathrm{Re}(f_m)&=&\mathrm{Re}(f_{n-m})\\ \mathrm{Img}(f_m)&=&-\mathrm{Img}(f_{n-m}) \end{array}\right\}\ \Longrightarrow\ f_m=f_{n-m}^*$

Ist bekannt, dass das Eingangssignal der FFT rein reell war, lohnt es sich daher nur, eine (im Regelfall die untere) Hälfte des Spektrums zu betrachten, wo der Betrag jedes Vektors der halben Amplitude einer Frequenz, und das Argument jedes Vektors der Phasenverschiebung einer Frequenz entspricht, aus der sich das Eingangssignal zusammensetzt.

Besondere Beachtung verdienen allenfalls in einigen Fällen der Gleichanteil, und das Element, das der höchsten im errechneten Spektrum möglichen Frequenz entspricht.

Genauigkeit

Tendenziell ist das Quantisierungsrauschen bei der schnellen Fouriertransformation in den Fällen, in denen sie effektiver als die DFT ist, aufgrund der geringeren Zahl an fehlerbehafteten Rechenoperationen geringer^[1], als bei der diskreten Faltung.

Die inverse FFT

Die enge Verwandtschaft zwischen FFT und iFFT lässt sich bereits aufgrund der folgenden Überlegungen erahnen:

• Ist das Eingangssignal der FFT ein mit einer konstanten Geschwindigkeit um den Nullpunkt rotierender Vektor, dann ist das Ergebnis der FFT bestimmungsgemäß ein Ausgangssignal, das bis auf den der Frequenz der Rotation entsprechenden Punkt, dessen Betrag der Amplitude und dessen Argument der Phase der Rotation zum Zeitpunkt t=0 entspricht – konstant 0.
• Ist das Eingangssignal der FFT konstant 0 mit Ausnahme eines einzigen Punktes, so ergibt die Grundgleichung der DFT in diesem Fall einen Vektor, der mit einer konstanten Geschwindigkeit um den Nullpunkt kreist.

Für einen Vektor, in dem nur ein einziger Punkt eine Amplitude ungleich 0 besitzt, ähnelt also die zweimalige FFT des Ergebnisses dem Ausgangswert.

• Zusätzlich besteht die FFT nur aus linearen Gleichungen. Dies bedeutet unter Anderen, dass, wenn verschiedene Ausgangsvektoren addiert und dann zwei Mal durch die FFT transformiert werden, das Ergebnis dieser Aktion identisch sein muss, wie, wenn die einzelnen Signale erst zweimal transformiert und dann addiert werden.

Zusammen lässt dies vermuten, dass das Ergebnis einer zweimal hintereinander ausgeführten FFT für beliebige Signale dem Original ähneln wird.

Allerdings ist die Amplitude des Ergebnisses der zweimaligen FFT eines Signals offensichtlich von dessen Länge L abhängig, und ist in den obigen Überlegungen die Richtung der Rotation der Vektoren um den Nullpunkt nicht berücksichtigt worden.

Tatsächlich gilt für jegliche Art der Fouriertransformation:

$\frac{1}{\mathrm{L}}\left(\mathcal{F}\left\{\left(\mathcal{F}\left\{f(x)\right\}\right)^*\right\}\right)^*=f(x)$

Anwendung

Die Anwendungsgebiete der FFT sind so vielseitig, dass hier nur eine Auswahl gegeben werden kann:

• Computeralgebra
  • Implementierung schneller, Polynome verarbeitender Algorithmen (z. B. Polynommultiplikation in $O(n\, \log{n})$)
• Finanzmathematik
  • Die Berechnung von Optionspreisen (vgl. Carr / Madan 1999)
• Signalanalyse
  • Akustik (Audiomessungen). Eine triviale Anwendung sind viele Gitarrenstimm- oder ähnliche Programme, die von ihrer hohen Geschwindigkeit profitieren.
  • Berechnung vom Spektrogrammen (Diagramme mit der Darstellung der Amplituden von den jeweiligen Frequenzanteilen)
  • Rekonstruktion des Bildes beim Kernspintomographen oder der Analyse von Kristallstrukturen mittels Röntgenstrahlen, bei denen jeweils die Fouriertransformierte des gewünschten Bildes, bzw. das Quadrat dieser Fouriertransformierten entsteht.
• Messtechnik/ allgemein
  • Digitale Netzwerkanalysatoren, die das Verhalten einer Schaltung, eines Bauelementes oder einer Leitung auf einer Leiterbahn bei Betrieb mit beliebigen Frequenzgemischen zu ermitteln versuchen.
• Signalverarbeitung
  • Synthese von Audiosignalen aus einzelnen Frequenzen über die inverse FFT
  • Zur Reduzierung des Berechnungsaufwandes bei der zirkularen Faltung im Zeitbereich von FIR-Filtern und Ersatz durch die schnelle Fouriertransformation und einfache Multiplikationen im Frequenzbereich. (siehe auch Schnelle Faltung). Die Schnelle Faltung bietet z. B. die Möglichkeit, beliebige Audio- oder ähnliche Signale mit wenig Rechenaufwand durch auch sehr komplexe Filter (Equalizer, etc.) zu transportieren.
  • Kompressionsalgorithmen verwenden oft die FFT oder, wie das bekannte MP3-Format, die mit ihr verwandte diskreten Kosinustransformation: Die FFT von Bildern oder Tönen ergibt oft nur relativ wenige Frequenzanteile mit hohen Amplituden (Was, wenn ein Verfahren zur Speicherung der Ergebnisse verwendet wird, das für die Darstellung niedriger Zahlen weniger Bits benötigt, wie z. B. die Huffman-Kodierung, von Vorteil ist). In anderen Fällen wird ausgenutzt, dass einige der Frequenzen weggelassen werden können, ohne das Ergebnis stark zu beeinträchtigen, so dass die Menge der zu speichernden Daten auf diese Weise reduziert werden kann.
• Telekommunikation
  • Längstwellenempfang mit dem PC
  • Breitbanddatenübertragung per OFDM, die Grundlage für ADSL und WLAN (Internet), DVB-T (Fernsehen), DRM, DAB (Radio) und LTE (Mobilfunk der 4. Generation) ist. Hier wird die hohe Geschwindigkeit dadurch erreicht, dass viele relativ langsame Datenübertragungen auf vielen Trägerfrequenzen gleichzeitig betrieben werden. Das komplexe Signal, das durch Überlagerung der einzelnen Signale entsteht, wird dann von der Gegenstelle mittels der FFT wieder in einzelne Signalträger zerlegt.

Literatur

Zeitschriftenartikel

• James W. Cooley, John W. Tukey: An algorithm for the machine calculation of complex Fourier series. In: Math. Comput. 19, 1965, S. 297–301.
• C. M. Rader: Discrete Fourier transforms when the number of data samples is prime. In: Proc. IEEE. 56, 1968, S. 1107–1108.
• Leo I. Bluestein: A linear filtering approach to the computation of the discrete Fourier transform. In: Northeast Electronics Research and Engineering Meeting Record. 10, 1968, S. 218–219.
• Georg Bruun: z-Transform DFT filters and FFTs. In: IEEE Trans. on Acoustics, Speech and Signal Processing (ASSP). 26, Nr. 1, 1978, S. 56-63.
• M. T. Heideman, D. H. Johnson, C. S. Burrus : Gauss and the History of the Fast Fourier Transform. In: Arch. Hist. Sc. 34, Nr. 3, 1985.

Bücher

• Alan V. Oppenheim, Ronald W. Schafer: Zeitdiskrete Signalverarbeitung. 3. Auflage. R. Oldenbourg Verlag, München/Wien 1999, ISBN 3-486-24145-1.
• E. Oran Brigham: FFT. Schnelle Fourier-Transformation. R. Oldenbourg Verlag, München/Wien 1995, ISBN 3-486-23177-4.
• Steven W. Smith: The Scientist and Engineer's Guide to Digital Signal Processing. 1 Auflage. Elsevier Ltd, Oxford, 2002, ISBN 978-0750674447, 18 (www.dspguide.com).

Weblinks

• www.inf.fh-flensburg.de/lang/algorithmen/fft/fft.htm – Beschreibung der Fourier-Transformation und Einheitswurzeln (Deutsch)
• [1] – Bedeutung der FFT-Analyse in der Audiotechnik (Beispiel-Grafik: Rechtecksignal) (Deutsch)
• www.sprut.de/electronic/pic/16bit/dsp/fft/fft.htm – Einführung in die FFT für Nichtstudierte, z. B. Auszubildende (Deutsch)
• www.fftw.org (Englisch)
• www.nr.com – Buch Numerical Recipes, englisch, auch online verfügbar (Englisch)
• local.wasp.uwa.edu.au/~pbourke/other/dft/ (schöner FFT-Code in C, in 1D und 2D) (Englisch)
• Kevin McGee: An introduction to signal processing and fast fourier transform (FFT). Abgerufen am 27. April 2010. 

Einzelnachweise

1. ↑ Steven W. Smith, Ph.D. The Scientist and Engineer's Guide to Digital Signal Processing. Buch in der Online-Ausgabe. Abgerufen am 8. Dezember 2009.