Szybka transformacja Fouriera

Szybka transformacja Fouriera (ang. fast Fourier transform, FFT) – algorytm liczenia dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej.

Czasem używana jest też forma szybka transformata Fouriera w odniesieniu do tej metody. Ściśle jednak transformacja jest przekształceniem, a transformata wynikiem tego przekształcenia.

Niech x₀, ...., 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^{-{2\pi i \over N}nk}\qquad k=0,\dots ,N-1.$

Obliczanie tych sum za pomocą powyższego wzoru zajęłoby O(N²) operacji.

Algorytmy (jak algorytm Cooleya-Tukeya) obliczające szybką transformację Fouriera bazują na metodzie dziel i zwyciężaj, rekurencyjnie dzieląc transformatę wielkości N = N₁N₂ na transformaty wielkości N₁ i N₂ z wykorzystaniem O(N) operacji mnożenia.

Najpopularniejszą wersją FFT jest FFT o podstawie 2. Jest to bardzo efektywna operacja, 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 o tak zwane struktury motylkowe.

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

Zobacz też

• FFTW
• transformacja Fouriera
• kwantowa transformata Fouriera

Bibliografia

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