Direkt zum Inhalt

Lexikon der Mathematik: schnelle Fourier-Transformation

FFT, eine Klasse numerischer Algorithmen zur Auswertung der diskreten Fourier-Transformation (vgl. auch diskrete Fourier-Analyse).

Es sei f : ℝ ↠ ℂ L-periodisch und an den Stützstellen xn = nL/N, n = 0,…,N − 1, bekannt. Die diskrete Fourier-Transformation liefert mit \begin{eqnarray}\begin{array}{cc}{c}_{k}=\frac{1}{N}\displaystyle \sum _{n=0}^{N-1}{f}_{n}{e}^{-2i\pi nk/N},\end{array}\end{eqnarray}k = 0,…,N − 1, Näherungen für die FourierKoeffizienten von f. Für N = N1N2 gilt \begin{eqnarray}{c}_{k}=\frac{1}{{N}_{1}}\displaystyle \sum _{n=0}^{{N}_{1}-1}{\gamma }_{mn}{e}^{-2i\pi nk/N}\end{eqnarray} falls \begin{eqnarray}\begin{array}{cc}{\gamma }_{mn}=\frac{1}{{N}_{2}}\displaystyle \sum _{j=0}^{{N}_{2}-1}{f}_{n+j{N}_{1}}{e}^{-2i\pi jm/{N}_{2}}\end{array}\end{eqnarray} und 0 ≤ m < N2, 0 ≤ n < N1, k = m + nN2. Diese Zerlegung ist Grundlage verschiedener effizienter Berechnungsverfahren, die als schnelle FourierTransformationen bezeichnet werden.

Ist N2 = N21N22, so läßt sich dieses Verfahren erneut zur Bestimmung von (2) anwenden. Dies führt für N = 2s = 2 · 2s−1 = 2 · (2 · 2s−2) = … zu folgendem rekursiven Algorithmus: \begin{eqnarray}\begin{array}{rll}{\gamma }_{0,n}^{s} & = & {f}_{n}\,\,\text{f}\mathrm{\ddot{u}}\text{r}\,\,\,0\le n\le N-1,\\ {\gamma }_{m,n}^{r-1} & = & \frac{1}{2}({\gamma }_{m,n}^{r}+{\alpha }_{mr}{\gamma }_{m,n+{2}^{r-1}}^{r})\,\,\text{f}\mathrm{\ddot{u}}\text{r}\,0\le n\le {2}^{r-1},\\ {\gamma }_{m+{2}^{s-r},n}^{r-1} & = & \frac{1}{2}({\gamma }_{m,n}^{r}-{\alpha }_{mr}{\gamma }_{m,n+{2}^{r-1}}^{r})\,\,\text{f}\mathrm{\ddot{u}}\text{r}\,0\le m\le {2}^{s-r},\end{array}\end{eqnarray} wobei αmr = exp(−imπ2r−s). Dieser Algorithmus erfordert ungefähr N log2(N/2) Rechenoperationen, während eine Berechnung mit Formel (1) etwa N2 Operationen verlangt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos