71087

Algorytm FFT

Aby obliczyć jedną próbkę widma DFT X(k) trzeba wykonać N mnożeń,

N-l dodawań. Obliczenie wszystkich N próbek DFT wymaga więc Ni mnożeń oraz N(N -1) dodawań. Całkowita liczba obliczeń N punktowego DFT jest więc proporcjonalna do Ni. Dwukrotne wydłużenie N powoduje czterokrotny wzrost nakładu obliczeniowego. Dla dużych wartości N obliczanie DFT wg. wzoru (2.1) jest praktycznie niemożliwe w czasie rzeczywistym. Rozwiązaniem problemu jest algorytm FFT (Fast Fourier Transform).

Wynik otrzymany poprzez FFT jest dokładnie taki sam jak wynik DFT obliczanego na podstawie definicji (2.1). W praktyce stosuje się rożne odmiany FFT. Poniżej przedstawiono zasadę działania popularnego algorytmu z podziałem w dziedzinie czasu, o podstawie 2 (DIT radix-2 FFT). Liczba operacji mnożenia i dodawania dla N punktowego DFT przy użyciu tego algorytmu jest proporcjonalna do N log2 N. Dla dużych wartości N liczba operacji wymaganych przez algorytm FFT jest znacząco mniejsza niż liczba operacji wymaganych do obliczenia DFT wg. definicji. Aby można było użyć algorytmu FFT długość DFT musi być liczbą w postaci N = 2?, gdzie P=l, 2, 3,....