Szybka transformacja Fouriera

Szybka transformacja Fouriera (Szablon:Ang., FFT) – algorytm wyznaczania dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej.

Czasem, w odniesieniu do tej metody, używane jest też określenie szybka transformata Fouriera, które jednak nie jest prawidłowe, gdyż pojęcie transformacja oznacza przekształcenie, a transformata jest wynikiem tego przekształcenia.

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

Obliczanie sum za pomocą powyższego wzoru wymaga wykonania $O(N^2)$ operacji (zob. asymptotyczne tempo wzrostu).

Algorytmy (przede wszystkim algorytm Cooleya-Tukeya) obliczające szybką transformację Fouriera bazują na metodzie dziel i zwyciężaj, rekurencyjnie dzieląc transformatę wielkości $N=N_1{N}_2$ na transformaty wielkości $N_1$ i $N_2$ z wykorzystaniem $O(N)$ operacji mnożenia.

Najpopularniejszą wersją algorytmu FFT jest FFT o podstawie 2. Jest on bardzo efektywny pod względem czasu realizacji, 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 na tak zwanych strukturach motylkowych.

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

Zobacz też

• FFTW
• kwantowa transformata Fouriera
• transformacja Fouriera

Bibliografia

• Szablon:Cytuj książkę

Linki zewnętrzne

• Szablon:MathWorld