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 będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem:

Obliczanie sum za pomocą powyższego wzoru wymaga wykonania 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 na transformaty wielkości i z wykorzystaniem 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ść 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 w odróżnieniu od 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ż

Przypisy

  1. Fouriera szybka transformata, [w:] Encyklopedia PWN [dostęp 2021-10-10].

Bibliografia

Linki zewnętrzne

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

Witaj

Uczę się języka hebrajskiego. Tutaj go sobie utrwalam.

Źródło

Zawartość tej strony pochodzi stąd.

Odsyłacze

Generator Margonem

Podziel się