Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon: Erläuterung zu

Schnelle Fourier-Transformation

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Die diskrete Fourier-Transformation,

$\displaystyle f_j = \sum_{k=0}^{n-1} c_k w_n^{jk}\,, \quad j = 0,\dots,n-1\,, $

$ (w_n = \exp(2\pi \mathrm{i} / n))$, kann für $ n = 2^\ell$ mit der so genannten schnellen Fourier-Transformation (FFT, Fast Fourier Transform) mit $ 2 n \ell$-Operationen berechnet werden. In der rekursiven Version hat der Algorithmus die folgende Form:

\begin{tabbing} \qquad \= $f = \operatorname{FFT}(c)$\ \\ \> \qquad \= $n = \op... ... \> $f = (g+p\,.\!*\,h,\,g-p\,.\!*\,h)$\\ \> \> {\bf end}\\ \par \end{tabbing}

Dabei bezeichnet $ .*$ die komponentenweise Multiplikation von Vektoren, d.h. $ (a\,.\!*\,b)_j = a_jb_j$.

Die inverse diskrete Fourier-Transformation

$\displaystyle c_k = \frac{1}{n} \sum_{j=0}^{n-1} f_j w_n^{-jk} $

kann vollkommen analog berechnet werden. Man bezeichnet den entsprechenden Algorithmus mit $ c = \operatorname{IFFT}(f)$.
Die induktive Herleitung des Algorithmus ist verblüffend einfach. Man spaltet die Summen

$\displaystyle f_j = \sum_{k=0}^{n-1} c_k w^{kj},\quad j=0,\ldots,n-1 \,, $

in gerade und ungerade Summanden auf:

$\displaystyle \sum_{k=0}^{m-1} c_{2k} \tilde w^{kj} \ + \ \sum_{k=0}^{m-1} c_{2k+1} w^j \tilde w^{kj} $

mit $ m=n/2$ und $ \tilde w=\exp(2\pi\mathrm{i}/m)=w^2$. Bis auf den Faktor $ w^j$ entsprechen die Summen den im Algorithmus rekursiv berechneten diskreten Fourier-Transformationen der Länge $ m$:

$\displaystyle f_j = g_j + w^j h_j,\quad j=0,\ldots,m-1 \,. $

Ersetzt man in den Summen $ j$ durch $ j+m$ so ändert sich wegen $ \tilde w^m=1$ lediglich das Vorzeichen der zweiten Summe $ w^{j+m} = -w^j$. Damit folgt

$\displaystyle f_{j+m} = g_j - w^j h_j,\quad j=0,\ldots,m-1 \,, $

das heißt die Vektoren $ g$ und $ h$ lassen sich auch zur Berechnung von $ (f_m,f_{m+1},...,f_{n-1})^\mathrm{t}$ verwenden.

Die Anzahl $ \operatorname{op}(n)$ der vom FFT-Algorithmus benötigten komplexen Additionen und Multiplikationen lässt sich rekursiv bestimmen. Durch Addition der zur Berechnung von $ g$, $ h$, $ p$ und $ f$ benötigten Operationen erhält man

$\displaystyle \operatorname{op}(n) = \operatorname{op}(n/2) + \operatorname{op}(n/2) + (n/2) + 3(n/2) = 2\operatorname{op}(n/2) + 2n \,. $

Iteriert man diese Gleichung, so folgt
$\displaystyle \operatorname{op}(n)$ $\displaystyle =$ $\displaystyle 2\left(2\operatorname{op}(n/4) + 2(n/2)\right)+2n = 4\operatorname{op}(n/4) + 2n+2n$  
  $\displaystyle =$ $\displaystyle \cdots$  
  $\displaystyle =$ $\displaystyle 2^\ell\operatorname{op}(1) + \underbrace{2n + \cdots + 2n}_{\ell\text{-mal}} \,,$  

und wegen $ \operatorname{op}(1)=0$ die behauptete Gesamtoperationenzahl.
[Zurück]
  automatisch erstellt am 8. 11. 2013