8. The Discrete Fourier Transform

In Chapter 5 we developed the Fourier transform, which converts a signal from the time domain into the frequency domain. It is a powerful and elegant tool, but the version we studied is a mathematical primitive, and it is riddled with assumptions that are impractical in the real world. This is a book on computer music: we want a tool we can actually run on digital audio.

In this chapter we address those incompatibilities one at a time to derive the discrete Fourier transform (DFT), a metamorphosis of the Fourier transform that a computer can actually evaluate on a finite array of samples. This practicality comes at a cost, and along the way we will learn about the consequences of discretizing the transform. Finally, we will introduce the fast Fourier transform (FFT), an algorithm that computes the DFT exactly but with superior asymptotic behavior relative to the naive implementation.