Does the fft automatically use a dft algorithm?

Hello everybody, Matlab has only the fft command. The fft algorithm is based on a signal of power of 2. If your signal length differs, you can perfomr zero-padding or a cut-off. Well, what is not clear for me: if the signal does not fit the power of 2 condition, does matlab then automatically perform a dft or does it automatically zero-padding/truncating? thanks for your help! Peter

Answer 1

[Wayne King]

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.

Answer 2

[David Young]

The DFT isn't an algorithm: it's a mathematical formula that defines the transform. You can find the formula in textbooks and in the documentation for the fft function.

The FFT is an algorithm: it's a set of instructions for carrying out the computations needed to perform the DFT on data. The general modern formulation is not restricted to data lengths that are powers of 2, though it requires less computation if the length has many small factors, and a power of 2 is such a case.

The fft function in MATLAB is an implementation of the FFT; it therefore also implements the DFT. This is true regardless of the length of the data. The function does not do any automatic zero-padding, though you can specify padding to a specific length if you need to try to reduce run-time.