Signals, Systems, and Signal Processing

This chapter introduces the discrete Fourier transform (DFT), which is different from the discrete-time Fourier transform (DTFT) introduced earlier. The DFT transforms an N-point sequence x[n] in the time domain to an N-point sequence X[k] in the frequency domain by sampling the DTFT of x[n]. A matrix representation for this transformation is introduced, and the properties of the DFT matrix are studied. The fast Fourier transform (FFT), which is a fast algorithm to compute the DFT, is also introduced. The FFT makes the computation of the Fourier transforms of large sets of data practical. The digital signal processing revolution of the 1960s was possible because of the FFT. This chapter introduces the simplest form of FFT, called the radix-2 FFT, and a number of its properties. The chapter also introduces circular or cyclic convolution, which has a special place in DFT theory, and explains the connection to ordinary convolution. Circular convolution paves the way for fast algorithms for ordinary convolution, using the FFT. The chapter also summarizes the relationships between the four types of Fourier transform studied in this book: CTFT, DTFT, DFT, and Fourier series.