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 na tak zwanych strukturach motylkowych.

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.).

• FFTW
• kwantowa transformata Fouriera
• transformacja Fouriera

• Zenon Fortuna, Bohdan Macukow, Janusz Wąsowski: Metody numeryczne. Warszawa: Wydawnictwa Naukowo-Techniczne, 1993. ISBN 83-204-1551-9. Brak numerów stron w książce

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