Signal Processing in C

CHAPTER 9

Discrete Fourier Transforms

Fourier transforms, explained in Chapter 8, are useful for theoretical work and practical calculations. However, the continuous-time Fourier transform cannot be used directly for digital signal processing. The values of discrete-time signals are known only at the discrete sample times, and only finitely many such sample points can be used or known at any time. The discrete Fourier transform (DFT for short) must work within these restrictions, yet still provide knowledge of the frequency domain analogous to the information provided by the continuous-time, infinite-duration Fourier transform of Chapter 8.

The mathematics behind Fourier transforms, and discrete Fourier transforms in particular, is called harmonic analysis. Harmonic analysis is the study of functions defined on groups. The name for this branch of mathematics is derived from the very cases needed for signal processing. It is the study of the harmonic content of functions or signals. Harmonic analysis shows how every function defined on a group can be written in terms of a distinguished set of functions on the group, called its characters. In Chapter 8, the group was, the real numbers, and the characters were the exponentials, exp(jωt). In all cases required for digital signal processing, the characters turn out to be exponentials.

This chapter presents the central ideas behind the ...