Practical implementations of the DFT are usually based on one of the
Cooley-Tukey ``Fast Fourier Transform'' (FFT) algorithms
[17].^{8.1} For
this reason, the matlab DFT function is called ``fft`', and the
actual algorithm used depends primarily on the transform length
.^{8.2} The fastest FFT algorithms
generally occur when
is a power of 2. In practical audio signal
processing, we routinely zero-pad our FFT input buffers to the next
power of 2 in length (thereby interpolating our spectra somewhat) in
order to enjoy the power-of-2 speed advantage. Finer spectral
sampling is a typically welcome side benefit of increasing
to the
next power of 2. Appendix A provides a short overview of some of the
better known FFT algorithms, and some pointers to literature and
online resources.

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University