Think DSP

Chapter 7. Discrete Fourier Transform

We’ve been using the Discrete Fourier Transform (DFT) since Chapter 1, but I haven’t explained how it works. Now is the time.

If you understand the Discrete Cosine Transform (DCT), you will understand the DFT. The only difference is that instead of using the cosine function, we’ll use the complex exponential function. I’ll start by explaining complex exponentials, then we’ll follow the same progression as in Chapter 6:

1. We’ll start with the synthesis problem: given a set of frequency components and their amplitudes, how can we construct a signal? The synthesis problem is equivalent to the inverse DFT.

2. Then we’ll rewrite the synthesis problem in the form of matrix multiplication using NumPy arrays.

3. Next we’ll solve the analysis problem, which is equivalent to the DFT: given a signal, how do we find the amplitude and phase offset of its frequency components?

4. Finally, we’ll use linear algebra to find a more efficient way to compute the DFT.

The code for this chapter is in chap07.ipynb, which is in the repository for this book (see “Using the Code”). You can also view it at http://tinyurl.com/thinkdsp07.

Complex Exponentials

One of the more interesting moves in mathematics is the generalization of an operation from one type to another. For example, a factorial is a function that operates on integers; the natural definition for the factorial of n is the product of all integers from 1 to n.

If you are of a certain inclination, ...