Video

Quiz

Hier geht's zum Video „DFT - Diskrete Fourier-Transformation “

FFT (Fast Fourier Transformation)

Wichtige Inhalte in diesem Video

Komplexität der DFT

Struktur der Fourier-Matrix

FFT einfach erklärt

Komplexität der FFT (Fast Fourier Transformation)

Die FFT (englisch: Fast Fourier Transformation) oder auch schnelle Fourier Transformation verringert den Rechenaufwand der diskreten Fourier Transformation. Dieses Vorgehen erklären wir dir anhand des Algorithmus von Cooley und Tukey zur Berechnung der DFT. Des Weiteren Vergleichen wir die Komplexität dieses Algorithmus zur Komplexität des herkömmlichen Verfahrens und zeigen dies anhand eines konkreten Beispiels.

Wenn du dir allerdings Zeit sparen willst und das Wichtigste zum Thema FFT in unter 5 Minuten erklärt haben möchtest, dann ist unser Video hierzu genau das Richtige für dich. Schau dir zum besseren Verständnis auch den Artikel zur Fourier Transformation an.

Inhaltsübersicht

Komplexität der DFT

im Videozur Stelle im Video springen

Die FFT (Fast Fourier Transformation) ist ein Algorithmus zur Berechnung der DFT (Diskreten Fourier Transformation) . Als Teile-und-herrsche-Verfahren reduziert die FFT die Zahl der Rechenoperationen im Vergleich zur herkömmlichen Berechnung der DFT enorm, weshalb sie zu Deutsch auch als Schnelle Fourier Transformation bezeichnet wird.

Diskrete Fourier Transformation (DFT)

Merke

Die DFT behandelt im Vergleich zur Theorie der Fourier-Reihen und der kontinuierlichen Fourier Transformation nicht die Spektralanalyse einer kontinuierlichen Funktion sondern die Analyse N diskreter Messwerte $a_0,a_1,\ldots,a_{N-1}$ , welche zu einem Vektor $\left(a_0,a_1,\ldots,a_{N-1}\right)=:a\in\mathbb{C}^N$ zusammengefasst werden.

Die Koeffizienten der Diskreten Fourier Transformierten $\hat{a}=\left({\hat{a}}_0,{\hat{a}}_1,\ldots,{\hat{a}}_{N-1}\right)$ dieses Vektors a berechnen sich nach folgender Vorschrift:

${\hat{a}}_n=\frac{1}{N}\sum_{k=0}^{N-1}{e^{-2\pi i\cdot\frac{k\cdot n}{N}}\cdot a_k}$

Diese Gleichung lässt sich auch in Matrix-Schreibweise formulieren. Zur Vereinfachung soll hierbei die Abkürzung $\zeta_N=e^{-2\pi i\cdot\frac{1}{N}}$ für die N-te Einheitswurzel eingeführt werden. Es ergibt sich folgende Gleichung:

$\left(\begin{matrix}{\hat{a}}_0\\{\hat{a}}_1\\{\hat{a}}_2\\\vdots\\{\hat{a}}_{N-1}\\\end{matrix}\right)=\frac{1}{N}\cdot\left(\begin{matrix}1&1&1&\ldots&1\\1&\zeta_N^1&\zeta_N^2&\ldots&\zeta_N^{N-1}\\1&\zeta_N^2&\zeta_N^4&\ldots&\zeta_N^{2(N-1)}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&\zeta_N^{N-1}&\zeta_N^{2(N-1)}&\ldots&\zeta_N^{(N-1)(N-1)}\\\end{matrix}\right)\left(\begin{matrix}a_0\\a_1\\a_2\\\vdots\\a_{N-1}\\\end{matrix}\right)$

Die Matrix

$Z:=\left(\begin{matrix}1&1&1&\ldots&1\\1&\zeta_N^1&\zeta_N^2&\ldots&\zeta_N^{N-1}\\1&\zeta_N^2&\zeta_N^4&\ldots&\zeta_N^{2(N-1)}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&\zeta_N^{N-1}&\zeta_N^{2(N-1)}&\ldots&\zeta_N^{(N-1)(N-1)}\\\end{matrix}\right)$

der Gleichung wird als Fourier-Matrix bezeichnet.

Die Inverse Diskrete Fourier Transformierte berechnet sich wie folgt:

$a_n=\sum_{k=0}^{N-1}{\hat{a}}_k\cdot e^{2\pi i\cdot\frac{k\cdot n}{N}}$

Für den Vorfaktor $\frac{1}{N}$ der DFT gibt es unterschiedliche Konventionen. Manchmal tritt er auch in der Inversen DFT statt in der DFT auf.

Komplexität

Soll für ein gemessenes Signal eine Spektralanalyse von einem Computer durchgeführt werden, so muss dieser die Diskrete Fourier Transformation durchführen. Hierbei ist von großer Bedeutung, wie viele Rechenoperationen der Computer dazu ausführen muss. Führt der Computer die Berechnung mittels herkömmlicher Matrixmultiplikation durch, so benötigt er hierfür $N\cdot\left(N+\left(N-1\right)\right)=2N^2-N$ Rechenoperationen. Für die Berechnung einer Komponente ${\hat{a}}_n$ fallen nämlich N Multiplikationen und N-1 Additionen an und dies muss dann noch mit der Anzahl N der Komponenten von $\hat{a}$ multipliziert werden. Die 2N^2-N Rechenoperationen entsprechen somit einer Komplexität von

$\mathcal{O}\left(N\right)=N^2$

Das bedeutet, dass der Rechenaufwand zur herkömmlichen Berechnung der DFT schnell ansteigt, wenn die Anzahl N an Messwerten des Signals erhöht wird.

FFT Erklärung

im Videozur Stelle im Video springen

Die FFT – einfach erklärt – stellt eine Berechnungsmethode der DFT dar, mit welcher der Rechenaufwand reduziert wird. Dies ist möglich, da in der Fourier-Matrix nur die N-te Einheitswurzel $\zeta_N=e^{-2\pi i\cdot\frac{1}{N}}$ in verschiedenen Potenzen auftritt, welche folgende Eigenschaften besitzt:

${{(\zeta}_N)}^N=\left(e^{-2\pi i\cdot\frac{1}{N}}\right)^N=e^{-2\pi i\cdot\frac{N}{N}}=e^{-2\pi i}=1$

${{(\zeta}_N)}^{N/2}=\left(e^{-2\pi i\cdot\frac{1}{N}}\right)^{N/2}=e^{-2\pi i\cdot\frac{N/2}{N}}=e^{-\pi i}=-1$

Dadurch lässt sich die Struktur der Fourier-Matrix vereinfachen, falls die Anzahl N der Messwerte eine Zweierpotenz ist, und letztendlich lässt sich die Zahl der Rechenoperationen dadurch reduzieren.

FFT Algorithmus von Cooley und Tukey

Die FFT ist ein Algorithmus, der das Verfahren hierzu beschreibt. Dieser Algorithmus wurde zwar bereits von Carl Friedrich Gauß entworfen, wird heute aber nach James Cooley und John W. Tukey benannt, welche diesen im Jahr 1965 veröffentlichten. Wie bereits erwähnt macht sich die FFT die Struktur der Fourier-Matrix zunutze, welche im Folgenden analysiert werden soll.

Struktur der Fourier-Matrix

im Videozur Stelle im Video springen

Als Voraussetzung des Algorithmus von Cooley und Tukey, muss die Anzahl der Messwerte N einer Zweierpotenz entsprechen:

N=2^n $n\in\mathbb{N}$

Um die nun folgenden Überlegungen zur FFT besser veranschaulichen zu können, wird das Beispiel N=8=2^3 gewählt.

In der ursprünglichen Form besitzt die Fourier-Matrix dann folgende Struktur:

$Z=\left(\begin{matrix}1&1&1&1&1&1&1&1\\1&\zeta_8^1&\zeta_8^2&\zeta_8^3&\zeta_8^4&\zeta_8^5&\zeta_8^6&\zeta_8^7\\1&\zeta_8^2&\zeta_8^4&\zeta_8^6&\zeta_8^8&\zeta_8^{10}&\zeta_8^{12}&\zeta_8^{14}\\1&\zeta_8^3&\zeta_8^6&\zeta_8^9&\zeta_8^{12}&\zeta_8^{15}&\zeta_8^{18}&\zeta_8^{21}\\1&\zeta_8^4&\zeta_8^8&\zeta_8^{12}&\zeta_8^{16}&\zeta_8^{20}&\zeta_8^{24}&\zeta_8^{28}\\1&\zeta_8^5&\zeta_8^{10}&\zeta_8^{15}&\zeta_8^{20}&\zeta_8^{25}&\zeta_8^{30}&\zeta_8^{35}\\1&\zeta_8^6&\zeta_8^{12}&\zeta_8^{18}&\zeta_8^{24}&\zeta_8^{30}&\zeta_8^{36}&\zeta_8^{42}\\1&\zeta_8^7&\zeta_8^{14}&\zeta_8^{21}&\zeta_8^{28}&\zeta_8^{35}&\zeta_8^{42}&\zeta_8^{49}\\\end{matrix}\right)$

Diejenigen Einträge, die gleich 1 sind, können durch ${1=\zeta}_8^0$ ersetzt werden und es ergibt sich:

$Z=\left(\begin{matrix}\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0\\\zeta_8^0&\zeta_8^1&\zeta_8^2&\zeta_8^3&\zeta_8^4&\zeta_8^5&\zeta_8^6&\zeta_8^7\\\zeta_8^0&\zeta_8^2&\zeta_8^4&\zeta_8^6&\zeta_8^8&\zeta_8^{10}&\zeta_8^{12}&\zeta_8^{14}\\\zeta_8^0&\zeta_8^3&\zeta_8^6&\zeta_8^9&\zeta_8^{12}&\zeta_8^{15}&\zeta_8^{18}&\zeta_8^{21}\\\zeta_8^0&\zeta_8^4&\zeta_8^8&\zeta_8^{12}&\zeta_8^{16}&\zeta_8^{20}&\zeta_8^{24}&\zeta_8^{28}\\\zeta_8^0&\zeta_8^5&\zeta_8^{10}&\zeta_8^{15}&\zeta_8^{20}&\zeta_8^{25}&\zeta_8^{30}&\zeta_8^{35}\\\zeta_8^0&\zeta_8^6&\zeta_8^{12}&\zeta_8^{18}&\zeta_8^{24}&\zeta_8^{30}&\zeta_8^{36}&\zeta_8^{42}\\\zeta_8^0&\zeta_8^7&\zeta_8^{14}&\zeta_8^{21}&\zeta_8^{28}&\zeta_8^{35}&\zeta_8^{42}&\zeta_8^{49}\\\end{matrix}\right)$

Wird in den Zeilen 3,5 und 7 der rechten Hälfte die Tatsache $\zeta_8^0=\zeta_8^8=\ \zeta_8^{16}=\ \zeta_8^{24}=1$ ausgenutzt, so ergibt sich:

$Z=\left(\begin{matrix}\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0\\\zeta_8^0&\zeta_8^1&\zeta_8^2&\zeta_8^3&\zeta_8^4&\zeta_8^5&\zeta_8^6&\zeta_8^7\\\zeta_8^0&\zeta_8^2&\zeta_8^4&\zeta_8^6&\zeta_8^8&\zeta_8^8\cdot\zeta_8^2&\zeta_8^8\cdot\zeta_8^4&\zeta_8^8\cdot\zeta_8^6\\\zeta_8^0&\zeta_8^3&\zeta_8^6&\zeta_8^9&\zeta_8^{12}&\zeta_8^{15}&\zeta_8^{18}&\zeta_8^{21}\\\zeta_8^0&\zeta_8^4&\zeta_8^8&\zeta_8^{12}&\zeta_8^{16}&\zeta_8^{16}\cdot\zeta_8^4&\zeta_8^{16}\cdot\zeta_8^8&\zeta_8^{16}\cdot\zeta_8^{12}\\\zeta_8^0&\zeta_8^5&\zeta_8^{10}&\zeta_8^{15}&\zeta_8^{20}&\zeta_8^{25}&\zeta_8^{30}&\zeta_8^{35}\\\zeta_8^0&\zeta_8^6&\zeta_8^{12}&\zeta_8^{18}&\zeta_8^{24}&\zeta_8^{24}\cdot\zeta_8^6&\zeta_8^{24}\cdot\zeta_8^{12}&\zeta_8^{24}\cdot\zeta_8^{18}\\\zeta_8^0&\zeta_8^7&\zeta_8^{14}&\zeta_8^{21}&\zeta_8^{28}&\zeta_8^{35}&\zeta_8^{42}&\zeta_8^{49}\\\end{matrix}\right)$

$=\left(\begin{matrix}\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0\\\zeta_8^0&\zeta_8^1&\zeta_8^2&\zeta_8^3&\zeta_8^4&\zeta_8^5&\zeta_8^6&\zeta_8^7\\\zeta_8^0&\zeta_8^2&\zeta_8^4&\zeta_8^6&\zeta_8^0&\zeta_8^2&\zeta_8^4&\zeta_8^6\\\zeta_8^0&\zeta_8^3&\zeta_8^6&\zeta_8^9&\zeta_8^{12}&\zeta_8^{15}&\zeta_8^{18}&\zeta_8^{21}\\\zeta_8^0&\zeta_8^4&\zeta_8^8&\zeta_8^{12}&\zeta_8^0&\zeta_8^4&\zeta_8^8&\zeta_8^{12}\\\zeta_8^0&\zeta_8^5&\zeta_8^{10}&\zeta_8^{15}&\zeta_8^{20}&\zeta_8^{25}&\zeta_8^{30}&\zeta_8^{35}\\\zeta_8^0&\zeta_8^6&\zeta_8^{12}&\zeta_8^{18}&\zeta_8^0&\zeta_8^6&\zeta_8^{12}&\zeta_8^{18}\\\zeta_8^0&\zeta_8^7&\zeta_8^{14}&\zeta_8^{21}&\zeta_8^{28}&\zeta_8^{35}&\zeta_8^{42}&\zeta_8^{49}\\\end{matrix}\right)$

Somit wiederholen sich schon einmal die Zeilen 1,3,5 und 7 immer nach 4 Einträgen. Nun kann in den Zeilen 2,4,6 und 8 zunächst mithilfe der Identität $\zeta_8^8=1$ geschickt vereinfacht werden und anschließend die Tatsache $\zeta_8^4=-1$ ausgenutzt werden:

$Z=\left(\begin{matrix}\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}\\\zeta_8^0&\zeta_8^1&\zeta_8^2&\zeta_8^3&\zeta_8^4&\zeta_8^5&\zeta_8^6&\zeta_8^7\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{2}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{2}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}\\\zeta_8^0&\zeta_8^3&\zeta_8^6&\zeta_8^9&\zeta_8^{12}&\zeta_8^{15}&\zeta_8^{18}&\zeta_8^{21}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{8}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{8}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}\\\zeta_8^0&\zeta_8^5&\zeta_8^{10}&\zeta_8^{15}&\zeta_8^{20}&\zeta_8^{25}&\zeta_8^{30}&\zeta_8^{35}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{18}}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{18}}\\\zeta_8^0&\zeta_8^7&\zeta_8^{14}&\zeta_8^{21}&\zeta_8^{28}&\zeta_8^{35}&\zeta_8^{42}&\zeta_8^{49}\\\end{matrix}\right)$

$=\left(\begin{matrix}\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}\\\zeta_8^0&\zeta_8^1&\zeta_8^2&\zeta_8^3&\zeta_8^4&\zeta_8^5&\zeta_8^6&\zeta_8^7\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{2}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{2}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}\\\zeta_8^0&\zeta_8^3&\zeta_8^6&\zeta_8^9&\zeta_8^4&\zeta_8^7&\zeta_8^{10}&\zeta_8^{13}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{8}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{8}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}\\\zeta_8^0&\zeta_8^5&\zeta_8^{10}&\zeta_8^{15}&\zeta_8^4&\zeta_8^9&\zeta_8^{14}&\zeta_8^{19}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{18}}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{18}}\\\zeta_8^0&\zeta_8^7&\zeta_8^{14}&\zeta_8^{21}&\zeta_8^4&\zeta_8^{11}&\zeta_8^{18}&\zeta_8^{25}\\\end{matrix}\right)$

$=\left(\begin{matrix}\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&\ \ \ \ \ \ \ \mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}\\\zeta_8^0&{\zeta_8^1\cdot\zeta}_8^0&{\zeta_8^2\cdot\zeta}_8^0&{\zeta_8^3\cdot\zeta}_8^0&\zeta_8^4\cdot\zeta_8^0&{\zeta_8^4\cdot\zeta_8^1\cdot\zeta}_8^0&{\zeta_8^4\cdot\zeta_8^2\cdot\zeta}_8^0&{\zeta_8^4\cdot\zeta_8^3\cdot\zeta}_8^0\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{2}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{2}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}\\\zeta_8^0&{\zeta_8^1\cdot\zeta}_8^2&{\zeta_8^2\cdot\zeta}_8^4&\zeta_8^3\cdot\zeta_8^6&{\zeta_8^4\cdot\zeta}_8^0&{\zeta_8^4\cdot\zeta_8^1\cdot\zeta}_8^2&{\zeta_8^4\cdot\zeta_8^2\cdot\zeta}_8^4&{\zeta_8^4\cdot\zeta_8^3\cdot\zeta}_8^6\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{8}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{8}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}\\\zeta_8^0&\zeta_8^1\cdot\zeta_8^4&{\zeta_8^2\cdot\zeta}_8^8&{\zeta_8^3\cdot\zeta}_8^{12}&{\zeta_8^4\cdot\zeta}_8^0&{\zeta_8^4\cdot\zeta_8^1\cdot\zeta}_8^4&{\zeta_8^4\cdot\zeta_8^2\cdot\zeta}_8^8&{\zeta_8^4\cdot\zeta_8^3\cdot\zeta}_8^{12}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{18}}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{18}}\\\zeta_8^0&\zeta_8^1\cdot\zeta_8^6&{\zeta_8^2\cdot\zeta}_8^{12}&{\zeta_8^3\cdot\zeta}_8^{18}&{\zeta_8^4\cdot\zeta}_8^0&{\zeta_8^4\cdot\zeta_8^1\cdot\zeta}_8^6&{\zeta_8^4\cdot\zeta_8^2\cdot\zeta}_8^{12}&{\zeta_8^4\cdot\zeta_8^3\cdot\zeta}_8^{18}\\\end{matrix}\right)$

$=\left(\begin{matrix}\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&\ \ \ \ \ \ \ \mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}\\\zeta_8^0&{\zeta_8^1\cdot\zeta}_8^0&{\zeta_8^2\cdot\zeta}_8^0&{\zeta_8^3\cdot\zeta}_8^0&-\zeta_8^0&{-\zeta_8^1\cdot\zeta}_8^0&{-\zeta_8^2\cdot\zeta}_8^0&{-\zeta_8^3\cdot\zeta}_8^0\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{2}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{2}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}\\\zeta_8^0&{\zeta_8^1\cdot\zeta}_8^2&{\zeta_8^2\cdot\zeta}_8^4&\zeta_8^3\cdot\zeta_8^6&{-\zeta}_8^0&{-\zeta_8^1\cdot\zeta}_8^2&{-\zeta_8^2\cdot\zeta}_8^4&{-\zeta_8^3\cdot\zeta}_8^6\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{8}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{8}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}\\\zeta_8^0&\zeta_8^1\cdot\zeta_8^4&{\zeta_8^2\cdot\zeta}_8^8&{\zeta_8^3\cdot\zeta}_8^{12}&{-\zeta}_8^0&{-\zeta_8^1\cdot\zeta}_8^4&{-\zeta_8^2\cdot\zeta}_8^8&{-\zeta_8^3\cdot\zeta}_8^{12}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{18}}&{\ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{18}}\\\zeta_8^0&\zeta_8^1\cdot\zeta_8^6&{\zeta_8^2\cdot\zeta}_8^{12}&{\zeta_8^3\cdot\zeta}_8^{18}&{-\zeta}_8^0&{-\zeta_8^1\cdot\zeta}_8^6&{-\zeta_8^2\cdot\zeta}_8^{12}&{-\zeta_8^3\cdot\zeta}_8^{18}\\\end{matrix}\right)$

Nun lässt sich erkennen, dass in den Zeilen 1,3,5 und 7 die Einträge sich nach der Hälfte wiederholen und sie sich in den Zeilen 2,4,6 und 8 ebenfalls nach der Hälfte allerdings mit negativem Vorzeichen wiederholen. Des Weiteren entspricht jede zweite Zeile der darüberliegenden Zeile, wenn spaltenweise immer derselbe Vorfaktor eingefügt wird. Aufgrund dieser Eigenschaft der Fourier-Matrix Z kann die eine Vektormultiplikation mit jener Matrix aufgeteilt werden in 2 Multiplikationen mit 2 Matrizen.

$\frac{1}{N}\cdot\left(\begin{matrix}\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&\ \ \ \ \ \ \ \mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}\\\zeta_8^0&{\zeta_8^1\cdot\zeta}_8^0&{\zeta_8^2\cdot\zeta}_8^0&{\zeta_8^3\cdot\zeta}_8^0&-\zeta_8^0&{-\zeta_8^1\cdot\zeta}_8^0&{-\zeta_8^2\cdot\zeta}_8^0&{-\zeta_8^3\cdot\zeta}_8^0\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{2}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{2}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}\\\zeta_8^0&{\zeta_8^1\cdot\zeta}_8^2&{\zeta_8^2\cdot\zeta}_8^4&\zeta_8^3\cdot\zeta_8^6&{-\zeta}_8^0&{-\zeta_8^1\cdot\zeta}_8^2&{-\zeta_8^2\cdot\zeta}_8^4&{-\zeta_8^3\cdot\zeta}_8^6\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{8}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{8}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}\\\zeta_8^0&\zeta_8^1\cdot\zeta_8^4&{\zeta_8^2\cdot\zeta}_8^8&{\zeta_8^3\cdot\zeta}_8^{12}&{-\zeta}_8^0&{-\zeta_8^1\cdot\zeta}_8^4&{-\zeta_8^2\cdot\zeta}_8^8&{-\zeta_8^3\cdot\zeta}_8^{12}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{18}}&{\ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\ \ \ \ \ \ \ \ \ \ \mathbit{\zeta}}_\mathbf{8}^{\mathbf{18}}\\\zeta_8^0&\zeta_8^1\cdot\zeta_8^6&{\zeta_8^2\cdot\zeta}_8^{12}&{\zeta_8^3\cdot\zeta}_8^{18}&{-\zeta}_8^0&{-\zeta_8^1\cdot\zeta}_8^6&{-\zeta_8^2\cdot\zeta}_8^{12}&{-\zeta_8^3\cdot\zeta}_8^{18}\\\end{matrix}\right)\cdot\left(\begin{matrix}a_0\\a_1\\a_2\\a_3\\a_4\\a_5\\a_6\\a_7\\\end{matrix}\right)=\left(\begin{matrix}{\hat{a}}_0\\{\hat{a}}_1\\{\hat{a}}_2\\{\hat{a}}_3\\{\hat{a}}_4\\{\hat{a}}_5\\{\hat{a}}_6\\{\hat{a}}_7\\\end{matrix}\right)$

Da sich nämlich die Zeilen 1,3,5 und 7 wiederholen, werden für die eine Vektormultiplikation jeweils die Einträge a_0 und a_4, a_1 und a_5, a_2 und a_6 sowie a_3 und a_7 des Vektors a als Summe zusammengefasst. Für die andere Multiplikation werden sie als Differenz zusammengefasst, da sich die Einträge in den Zeilen 2,4,6 und 8 mit negativem Vorzeichen wiederholen:

$\frac{1}{N}\cdot\left(\begin{matrix}\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{2}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{8}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{18}}\\\end{matrix}\right)\left(\begin{matrix}a_0+a_4\\a_1+a_5\\a_2+a_6\\a_3+a_7\\\end{matrix}\right)=\left(\begin{matrix}{\hat{a}}_0\\{\hat{a}}_2\\{\hat{a}}_4\\{\hat{a}}_6\\\end{matrix}\right)$

$\frac{1}{N}\cdot\left(\begin{matrix}\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\zeta_8^1\cdot\mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\zeta_8^2\cdot\mathbit{\zeta}}_\mathbf{8}^\mathbf{0}&{\zeta_8^3\cdot\mathbit{\zeta}}_\mathbf{8}^\mathbf{0}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\zeta_8^1\cdot\mathbit{\zeta}}_\mathbf{8}^\mathbf{2}&{\zeta_8^2\cdot\mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\zeta_8^3\cdot\mathbit{\zeta}}_\mathbf{8}^\mathbf{6}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\zeta_8^1\cdot\mathbit{\zeta}}_\mathbf{8}^\mathbf{4}&{\zeta_8^2\cdot\mathbit{\zeta}}_\mathbf{8}^\mathbf{8}&{\zeta_8^3\cdot\mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&{\zeta_8^1\cdot\mathbit{\zeta}}_\mathbf{8}^\mathbf{6}&{\zeta_8^2\cdot\mathbit{\zeta}}_\mathbf{8}^{\mathbf{12}}&{\zeta_8^3\cdot\mathbit{\zeta}}_\mathbf{8}^{\mathbf{18}}\\\end{matrix}\right)\left(\begin{matrix}a_0-a_4\\a_1-a_5\\a_2-a_6\\a_3-a_7\\\end{matrix}\right)=\left(\begin{matrix}{\hat{a}}_1\\{\hat{a}}_3\\{\hat{a}}_5\\{\hat{a}}_7\\\end{matrix}\right)$

Hierbei taucht in der zweiten Matrix noch der Vorfaktor in jeder Spalte auf. Dieser lässt sich in den Vektor ziehen und so ergibt sich dieselbe Matrix wie bei der ersten Multiplikation:

$\frac{1}{N}\cdot\left(\begin{matrix}\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{0}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{2}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{4}&\mathbit{\zeta}_\mathbf{8}^\mathbf{8}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}\\\mathbit{\zeta}_\mathbf{8}^\mathbf{0}&\mathbit{\zeta}_\mathbf{8}^\mathbf{6}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{12}}&\mathbit{\zeta}_\mathbf{8}^{\mathbf{18}}\\\end{matrix}\right)\left(\begin{matrix}{\ \ \ \ \ \ \ \ (a}_0-a_4)\\{\zeta_8^1\cdot(a}_1-a_5)\\{\zeta_8^2\cdot(a}_2-a_6)\\\zeta_8^3\cdot{(a}_3-a_7)\\\end{matrix}\right)=\left(\begin{matrix}{\hat{a}}_1\\{\hat{a}}_3\\{\hat{a}}_5\\{\hat{a}}_7\\\end{matrix}\right)$

Teile-und-herrsche-Verfahren

Durch die Struktur der Fourier-Matrix lässt sich die für die DFT durchzuführende Vektormultiplikation mit einer $\mathbit{N}\times\mathbit{N}$ -Matrix in zwei Multiplikationen mit $\frac{\mathbit{N}}{\mathbf{2}}\times\frac{\mathbit{N}}{\mathbf{2}}$ -Matrizen aufteilen. Diese beiden Matrizen sind sogar identisch und besitzen jeweils nur ein Viertel an Einträgen der ursprünglichen Fourier-Matrix. Der wichtigste Vorteil ist allerdings, dass diese beiden Matrizen wieder die Form einer Fourier-Matrix besitzen. In dem gezeigten Beispiel entspricht nämlich $\zeta_8^2$ der vierten Einheitswurzel $\zeta_4$ und es ergibt sich dadurch eine Fourier-Matrix der Größe 4=2^2 :

$\left(\begin{matrix}\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0\\\zeta_8^0&\zeta_8^2&\zeta_8^4&\zeta_8^6\\\zeta_8^0&\zeta_8^4&\zeta_8^8&\zeta_8^{12}\\\zeta_8^0&\zeta_8^6&\zeta_8^{12}&\zeta_8^{18}\\\end{matrix}\right)=\left(\begin{matrix}\zeta_8^0&\zeta_8^0&\zeta_8^0&\zeta_8^0\\\zeta_8^0&\zeta_4^1&\zeta_4^2&\zeta_4^3\\\zeta_8^0&\zeta_4^2&\zeta_4^4&\zeta_4^6\\\zeta_8^0&\zeta_4^3&\zeta_4^6&\zeta_4^9\\\end{matrix}\right)$

Das bedeutet, dass dieses Verfahren rekursiv so lange fortgesetzt werden kann, bis sich zum Schluss $\mathbf{1}\times\mathbf{1}$ -Matrizen ergeben. Ein solches Verfahren wird in der Informatik als Teile-und-herrsche Verfahren bezeichnet. Wie die FFT konkret durchgeführt werden kann, wird im Folgenden gezeigt.

FFT einfach erklärt

im Videozur Stelle im Video springen

Soll die FFT für einen Vektor $\left(a_0,a_1,\ldots,a_{N-1}\right)=:a\in\mathbb{C}^N$ – wobei N einer Zweierpotenz entspricht – durchgeführt werden, so können die Einträge des Vektors in einer Spalte angeordnet werden. Diese Spalte kann gedanklich in eine obere und eine unter Hälfte unterteilt werden. Aus diesen beiden Hälften werden die Einträge für die nächste Spalte auf zwei Arten berechnet:

Aus gleichrangigen Einträgen der beiden Hälften wird die Summe gebildet
Aus gleichrangigen Einträgen der beiden Hälften wird die Differenz gebildet, welche mit $\mathbit{\zeta}_{\mathbit{N}/\mathbf{2}^\mathbit{l}}^\mathbit{k}$ multipliziert wird. Hierbei bezeichnet k den Rang der Einträge, beginnend bei und l bezeichnet die Nummer der aktuellen Spalte, beginnend bei

Die Ergebnisse des ersten Schrittes werden in der oberen Hälfte der nächsten Spalte notiert, die Ergebnisse des zweiten Schrittes entsprechend in der unteren Hälfte. Für die beiden Hälften der neu berechneten Spalte wird das Verfahren erneut angewandt. Dies wird bis zu derjenigen Spalte l durchgeführt, für die 2^l=N gilt. Die Werte in dieser Spalte sind dann bereits die Einträge der Diskreten Fourier Transformierten. Die FFT soll am Beispiel für N=8=2^3 einmal durchgeführt werden.

Dazu wird der Vektor $a=(1,\ 4,\ -6,\ 3,\ 2,\ 4,\ -10,\ 3)$ betrachtet, welcher in einer Spalte angeordnet und in eine obere und untere Hälfte unterteilt wird.

Nun werden die Berechnungen durchgeführt, in die nächste Spalte eingetragen und die beiden Hälften der Zweiten Spalte wiederum in zwei Hälften unterteilt.

Für diese beiden Hälften wird nun jeweils das gleiche Verfahren wieder durchgeführt und so fortgefahren:

FFT Beispiel Fast Fourier Transformation Beispiel, FFT bestimmen, FFT berechnen, Fast Fourier Transformation bestimmen, Fast Fourier Transformation berechnen — FFT Beispiel

Die Einträge der letzten Spalte sind also die Einträge der Diskreten Fourier Transformierten, müssen aber noch in die richtige Reihenfolge gebracht werden. Das erfolgt mit einem sogenannten Bit-Umkehrverfahren. Dazu wird die aktuelle Position als Binärzahl notiert und durch Umkehren der Reihenfolge der Ziffern in der Binärschreibweise ergibt sich die neue Position als Binärzahl. Für das Beispiel N=8 folgt damit:

Aktuelle Position		Neue Position
dezimal	binär	binär	dezimal
0	000	000	0
1	001	100	4
2	010	010	2
3	011	110	6
4	100	001	1
5	101	101	5
6	110	011	3
7	111	111	7

Häufig wird das Vorgehen der FFT in einem sogenannten Butterfly-Graphen, also einem Schmetterlings-Graphen, dargestellt:

Butterfly-Graphen Schmetterlings Graphen FFT Fast Fourier Transformation FFT einfach erklärt — Butterfly-Graphen

In dieser Darstellung der FFT laufen zwei durch einen Kreis symbolisierten Werte an einem Rechteck zusammen, welches die Verknüpfung dieser Werte angibt. Aus dieser Verknüpfung ergibt sich dann der neue Wert, welcher wieder durch einen Kreis symbolisiert wird, zu dem ein Strich vom Verknüpfungsrechteck läuft. Im letzten Schritt wird die Umsortierung der Werte an die richtige Position dargestellt.

Komplexität der FFT (Fast Fourier Transformation)

im Videozur Stelle im Video springen

Bei den vorangegangenen Ausführungen wurde der Vorfaktor $\frac{1}{N}$ vor der DFT außer Acht gelassen. Dies wird bei den folgenden Überlegungen zur Komplexität der FFT wieder so gehandhabt.

Ebenso werden die Operationen vernachlässigt, die am Ende zum Umsortieren der Einträge nötig sind.

Um die restlichen Rechenoperationen der FFT richtig zu zählen, wird zunächst der Rechenaufwand bestimmt, der nötig ist, um eine neue Spalte zu berechnen. Dazu wird für die Hälfte $\frac{N}{2}$ der neuen Einträge eine Summe gebildet und für die andere Hälfte $\frac{N}{2}$ eine Differenz gebildet sowie ein Produkt berechnet. Das bedeutet, dass zur Berechnung einer neuen Spalte $3\cdot\frac{N}{2}$ Operationen benötigt werden. Letztlich muss also nur noch geklärt werden, wie viele Spalten für die vollständige FFT denn berechnet werden müssen. Wie oben bereits erwähnt wird das Verfahren bis zur Spalte l mit 2^l=N durchgeführt. Das bedeutet die Anzahl l der zu berechnenden Spalten entspricht $l={log}_2{N}$ . Somit beläuft sich der Rechenaufwand der FFT unter Nichtberücksichtigung der Umsortierung auf $3\cdot\frac{N}{2}\cdot{log}_2{N}$ Rechenoperationen, was einer Komplexität von

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

entspricht. Durch den Vergleich mit der Komplexität $\mathcal{O}\left(N\right)=N^2$ der herkömmlichen Berechnung einer DFT wird der Vorteil der FFT ihr gegenüber deutlich.

Inverse FFT

Da die Inverse Diskrete Fourier Transformierte ähnlich definiert ist wie die Diskrete Fourier Transformierte, ist auf sie der Algorithmus der FFT ebenso anwendbar. Hier muss allerdings je nach Konvention der richtige Vorfaktor berücksichtigt werden und statt mit der Einheitswurzel $\zeta_N$ mit ihrer Inversen $\zeta_N^{-1}$ gearbeitet werden.

Quiz zum Thema FFT - Fast Fourier-Transformation

Implementierung der FFT (Fast Fourier Transformation)

Im Folgenden wird anhand eines Pseudocodes gezeigt, wie die FFT implementiert werden kann.

1 Algorithm FFT(a)

input: Vektor $a=(a0, a1, … , aN-1) \in C^N$ (N eine Zweierpotenz)

output: Lösungsvektor $b=(b0, b1, … , bN-1) \in C^N$ (DFT des Inputs)
2 if a.length = 1 then
3 return a;
4 else
5 N:=a.length;
6 c:=1;
7 $a_{gerade}:= (a_0, a_1, ...\ , a_N_-_2)$ ;
8 $a_{ungerade}:= (a_0, a_1, ...\ , a_N_-_1)$ ;
9 $b_{gerade}:=FFT(a_{gerade})$ ;
10 $b_{ungerade}:=FFT(a_{ungerade})$ ;
11 for k:=0 to N/2 – 1 do
12 $b[k]=b_{gerade}[k] + c \cdot b_{ungerade}[k]$ ;
13 $b[k + N/2]=b_{gerade}[k] - c \cdot b_{ungerade}[k]$ ;
14 $c≔c\cdot exp (-2\pi i/N)$ ;
15 return b;

zur Videoseite: FFT - Fast Fourier-Transformation

Beliebte Inhalte aus dem Bereich Höhere Analysis

Fourierreihen - Beispiel

Fourier Transformation

Fourier Transformation Übungsaufgabe I

Fourier Transformation Übungsaufgabe II

DFT - Diskrete Fourier-Transformation

FFT - Fast Fourier-Transformation

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte .