Szybka transformata Fouriera
Z Wikipedii
Szybka transformata Fouriera (ang. FFT od fast Fourier transformation) to algorytm liczenia dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej.
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 transformaty Fouriera wynosi O(nlogn), zamiast O(n2) naiwnego algorytmu. Dzięki istnieniu takiego algorytmu praktyczne możliwe stało się cyfrowe przetwarzanie sygnałów (DSP), a także zastosowanie dyskretnych transformat cosinusowych (DCT) (JPEG, MP3 itd.) do kompresji.
Zobacz też: FFTW.
