Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]

Mathematik-Online-Lexikon:

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)$.

Beispiel:


[Erläuterungen] [Verweise]

  automatisch erstellt am 19.  8. 2013