Practical implementations of the
DFT are usually based on one of the
Cooley-Tukey ``
Fast Fourier Transform'' (
FFT) algorithms
[
16].
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.

Next Section: FFT of a Simple SinusoidPrevious Section: Periodic Interpolation
(Spectral Zero Padding)