i have a doubt like why is and how is FFT algorithm an efficient wat of computing DFT a sequence.
i have read so many books on DSP but i only got that the number of computations get reduced to Nlog(N) fron N^(2). But how will it get reduced to that?
Can anyone help me in that aspect by giving an example.
The FFT divides the n data samples into 2 sets of n/2 samples. Each resultant set is again split into 2 parts, etc. The result is that you do multiple FFTs on small data sets. This a gross simplification.
Regards,
Kral
For an N-length signal, the DFT requires N^2 number of computations.
FFT divides the signal into its odd and even components and takes the FT of each; this reduces the number of computations in the FT to 2*(N/2)^2 = (N^2)/2.
If you continue spliting the signal in two you'll effectively reduce the number of computations required in the DFT.
I hope this helps, let me know if you need a more elaborate response.
The Discrete Fourier Transform (DFT) is not an integration it is a summation just like the FFT. In fact, the FFT is just a fast way of computing the DFT, from there its name Fast-Fourier Transform.