Szybka transformacja Fouriera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 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ść gdzie 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 zamiast 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ż[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]