Szybka transformacja Fouriera

Szybka transformacja Fouriera (ang. Fast Fourier Transform, FFT) – algorytm wyznaczania dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej.

Czasem, w odniesieniu do tej metody, używane jest też określenie szybka transformata Fouriera, które jednak nie jest prawidłowe, gdyż pojęcie transformacja oznacza przekształcenie, a transformata jest wynikiem tego przekształcenia.

Niech $x_{0},\dots ,x_{N-1}$ będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem:

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.$

Obliczanie sum za pomocą powyższego wzoru wymaga wykonania $\mathrm {O} (N^{2})$ operacji (zob. asymptotyczne tempo wzrostu).

Algorytmy (przede wszystkim algorytm Cooleya-Tukeya) obliczające szybką transformację Fouriera bazują na metodzie dziel i zwyciężaj, rekurencyjnie dzieląc transformatę wielkości $N=N_{1}N_{2}$ na transformaty wielkości $N_{1}$ i $N_{2}$ z wykorzystaniem $\mathrm {O} (N)$ operacji mnożenia.

Najpopularniejszą wersją algorytmu FFT jest FFT o podstawie 2. Jest on bardzo efektywny pod względem czasu realizacji, jednak wektor próbek wejściowych (spróbkowany sygnał) musi mieć długość $N=2^{k},$ gdzie $k$ to pewna liczba naturalna. Wynik otrzymuje się na drodze schematycznych przekształceń, opartych na tak zwanych strukturach motylkowych.

Złożoność obliczeniowa szybkiej transformacji Fouriera wynosi $\mathrm {O} (N\log _{2}N),$ w odróżnieniu od $\mathrm {O} (N^{2})$ algorytmu wynikającego wprost ze wzoru określającego dyskretną transformatę Fouriera. Dzięki szybkiej transformacji Fouriera praktycznie możliwe stało się cyfrowe przetwarzanie sygnałów (DSP), a także zastosowanie dyskretnych transformat kosinusowych (DCT) do kompresji danych audio-wideo (JPEG, MP3, XviD itd.).

Zobacz też

• FFTW
• kwantowa transformata Fouriera
• transformacja Fouriera

Bibliografia

• Zenon Fortuna, Bohdan Macukow, Janusz Wąsowski: Metody numeryczne. Warszawa: Wydawnictwa Naukowo-Techniczne, 1993. ISBN 83-204-1551-9. Brak numerów stron w książce

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Fast Fourier Transform, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).