Szybka transformacja Fouriera

Szybka Transformacja Fouriera (FFT)

Szybka transformacja Fouriera (FFT) to algorytm stosowany do obliczania dyskretnej transformaty Fouriera oraz jej odwrotności. Chociaż często używa się terminu „szybka transformata Fouriera”, poprawniejsze jest odniesienie się do tego jako do „szybkiej transformacji”, ponieważ transformata odnosi się do wyniku przekształcenia.

Definicja i Złożoność Obliczeniowa

Dla liczb zespolonych $x\_0,\; \backslash dots,\; x\_\{N-1\}$, dyskretna transformata Fouriera definiowana jest wzorem:

$X\_k\; =\; \backslash sum\_\{n=0\}^\{N-1\}\; x\_n\; e^\{-\backslash frac\{2\backslash pi\; i\}\{N\}\; nk\; \}\; \backslash qquad\; k\; =\; 0,\backslash dots,N-1.$

Obliczanie tego wzoru w prosty sposób wymaga $\backslash Omicron(N^2)$ operacji. W przeciwieństwie do tego, algorytmy takie jak algorytm Cooleya-Tukeya stosują metodę dziel i zwyciężaj, co pozwala na obliczenie transformacji w $\backslash Omicron(N\; \backslash log\_2\; N)$ operacji.

Wersje Algorytmu FFT

Najbardziej znaną wersją jest FFT o podstawie 2, która jest szczególnie wydajna, pod warunkiem, że długość wektora próbek wejściowych wynosi $N=2^k$, gdzie $k$ jest liczbą naturalną. Wynik obliczeń uzyskuje się za pomocą struktur motylkowych.

Zastosowania

• Cyfrowe przetwarzanie sygnałów (DSP)
• Kompresja danych audio-wideo (np. JPEG, MP3, XviD)

Dzięki zastosowaniu FFT, cyfrowe przetwarzanie sygnałów stało się bardziej efektywne i powszechne, co miało znaczący wpływ na różne dziedziny technologii i inżynierii.