Does the fft automatically use a dft algorithm?

Question

Peter 2011-11-7

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/20527-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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Wayne King 2011-11-7

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/20527-does-the-fft-automatically-use-a-dft-algorithm#answer_27124

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

David Young 2011-11-7

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/20527-does-the-fft-automatically-use-a-dft-algorithm#answer_27122

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.