Szybka transformacja Fouriera

Szybka transformacja Fouriera (ang. Fast Fourier Transform, 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^[1], które jednak nie jest prawidłowe, gdyż pojęcie transformacja oznacza przekształcenie, a transformata jest wynikiem tego przekształcenia.

Niech ${\displaystyle x_{0},\dots ,x_{N-1}}$ będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem:

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}$

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

Algorytmy (jak algorytm Cooleya-Tukeya) obliczające szybką transformację Fouriera bazują na metodzie dziel i zwyciężaj, rekurencyjnie dzieląc transformatę wielkości ${\displaystyle N=N_{1}N_{2}}$ na transformaty wielkości ${\displaystyle N_{1}}$ i ${\displaystyle N_{2}}$ z wykorzystaniem ${\displaystyle \mathrm {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ść ${\displaystyle N=2^{k},}$ gdzie ${\displaystyle 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 ${\displaystyle \mathrm {O} (N\log _{2}N),}$ w odróżnieniu od ${\displaystyle \mathrm {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

Przypisy

Bibliografia

• Zenon Fortuna, Bohdan Macukow, Janusz Wąsowski: Metody numeryczne. Warszawa: Wydawnictwa Naukowo-Techniczne, 1993. ISBN 83-204-1551-9.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Fast Fourier Transform, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12]  (ang.).