Szybka transformacja Fouriera (
ang.
FFT od Fast Fourier Transform) 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
dyskretna transformata Fouriera
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
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ż