Szybka transformacja Fouriera
Z Wikipedii
Szybka transformacja Fouriera (ang. FFT od Fast Fourier Transformation) to 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 x0, ...., xN-1 będą liczbami zespolonymi, wtedy DFT jest określona wzorem
Obliczanie tych sum za pomocą powyższego wzoru zajęłoby O(N2) 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 = N1N2 na transformaty wielkości N1 i N2 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 = 2k, 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(Nlog2N), zamiast O(N2) algorytmu wynikającego wprost ze wzoru określającego DFT. Dzięki istnieniu takiego algorytmu praktyczne możliwe stało się cyfrowe przetwarzanie sygnałów (DSP), a także zastosowanie dyskretnych transformat kosinusowych (DCT) (JPEG, MP3 itd.) do kompresji.
