Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

### 14.2. The discrete Fourier transform

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

In 1822, the French physicist Joseph Fourier published The Analytic Theory of Heat, which presented a method of decomposing a complex mathematical function into a sum of simple functions. Over the centuries, this method has been applied to many more applications than the analysis of heat, and though Fourier focused on continuous functions, our goal is to decompose discrete signals, such as the digitized song from the previous section. We’ll call these discrete signals sequences, and the procedure that implements Fourier’s method on sequences is the discrete Fourier transform.

It’s important to understand that the discrete Fourier transform (DFT) and the fast Fourier transform (FFT) both accomplish the same operation. They both convert time-domain sequences, such as the one depicted on the right-hand side of figure 14.1, into frequency-domain sequences, such as that shown on the right-hand side of figure 14.2. The FFT is faster but the DFT is easier to understand, so we’ll start with this first. This section will present the mathematical theory behind the DFT, work through an example of its computation, and then show how it can be implemented in OpenCL.