MATLAB: Fft

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

Best Answer

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

Related Solutions

MATLAB: DFT

Hi Lisa, you had a couple problems with your code:

N= 4; 
x=1:4;
for k=0:3
    for n = 0:3;
y(n+1) = x(n+1).*exp(-(1j*2*pi*k*n)/N);
    end
    xdft(k+1)= sum(y);
end

compare to

fft(x)

MATLAB: Does the fft automatically use a dft algorithm

Hi Peter, MATLAB has multiple FFT algorithms. The transform is the discrete Fourier transform (DFT). FFT algorithms are just implementations of the DFT that reduce the computational complexity. You don't want to implement the DFT by a brute force matrix-vector product.

All these algorithms, the classic radix-2 FFT that you refer to, the chirp Z-transform evaluated on the unit circle contour, the Goerzel algorithm are ways of obtaining the DFT.

In particular, the FFTW library implemented in both MATLAB and SIMULINK supports both power of two and non-power of two signal lengths. Please see:

http://www.fftw.org/

So in short: There is no single FFT algorithm. FFT algorithms are implementations of the mathematical transform, the DFT.

Best Answer

Related Solutions

MATLAB: DFT

MATLAB: Does the fft automatically use a dft algorithm

Related Question