3582418580

Szybka transformata Fouriera - FFT

DFT cztero-punktowa wymaga 16 mnożeń na liczbach zespolonych Ogólnie DFT wymaga N² mnożeń na liczbach zespolonych

X(0) = x(0)W₄° + x(lW₄° + +

Jf(l) = x(Q)W_t° + xiX)W₄ + x + xO)IV₄'

X(2) = x(0)fV₄° +x(l)W₄² +xi2)W₄^Ą +x(3)W₄⁶ X(3) = x(0)W₄° +x(1)W₄^s +x(2W₄⁶ +x0 )W₄

Szybka transformata Founera (ang Fast Fourier Transform - FFT) jest tylko uproszczonym algorytmem DFT wykorzystującym następujące właściwości współczynnika W

symetryczności W_N*^m = -W_N^r,

Podstawową operacją upraszczającą algorytm obliczania

transformaty Fouriera jest 2 punktowa DFT    okresowości W •*" = W ^r