fft

Hey everyone,

I just want to know why we use fft in matlab to compute DFT? and can anyone recommend good DSP books or manuals.

Thanks inadvance

Answer 1

[Wayne King]

I think that is covered in just about any textbook. The DFT is computationally intensive to implement as a matrix-vector multiplication.

The NxN DFT matrix times a Nx1 signal vector involves N^2 multiplications and N additions.

By exploiting certain symmetries the fft() reduces that significantly.

If you just read the wikipedia page, you'll find references:

http://en.wikipedia.org/wiki/Fast_Fourier_transform