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 x 0 , … , x N − 1 {\displaystyle x_{0},\dots ,x_{N-1}} będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem:

X k = ∑ n = 0 N − 1 x n e − 2 π i N n k k = 0 , … , N − 1. {\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 O ( N 2 ) {\displaystyle \mathrm {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 {\displaystyle N=N_{1}N_{2}} na transformaty wielkości N 1 {\displaystyle N_{1}} i N 2 {\displaystyle N_{2}} z wykorzystaniem O ( N ) {\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ść N = 2 k , {\displaystyle N=2^{k},} gdzie k {\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 O ( N log 2 ⁡ N ) , {\displaystyle \mathrm {O} (N\log _{2}N),} w odróżnieniu od O ( N 2 ) {\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ż

Przypisy

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

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, Wolfram Research [dostęp 2020-12-12]  (ang.).
Encyklopedia internetowa: