how is FFT efficient?

[bhupala]

hi,

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.

i will be indebted to u

thank u

sri hari

 

[kazemi]

There is an example in Openhim's book " Descrit signal prossesing" in related chapter.

 

[Kral]

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

 

[Nazgul]

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.

 

[mnegm82]

because FFTis summation whill DFT is integration
therefore saves computation time

 

[Nazgul]

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.

 

[van_gift]

Because FFT changes the order of operations by grouping the same kind...