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