Algorytm FFT - opracowanie

Algorytm FFT Aby obliczyć jedną probkę widma DFT X ( k ) trzeba wykonać N mnożeń, N − 1 dodawań. Obliczenie wszystkich N probek DFT wymaga więc N 2 mno-
żeń oraz N ( N − 1) dodawań. Całkowita liczba obliczeń N punktowego DFT
jest więc proporcjonalna do N 2. Dwukrotne wydłużenie N powoduje czte-
rokrotny 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 od-
miany 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ż licz-
ba 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 P , gdzie P = 1 , 2 , 3 , . . . .
... zobacz całą notatkę