Chapter 14. Signal processing and the fast Fourier transform
This chapter covers
- The theory of frequency analysis
- Analyzing frequencies with the discrete Fourier transform
- Accelerating frequency analysis with the fast Fourier transform
Throughout the world of engineering, there is no escaping the fast Fourier transform (FFT). Cellular phones, audio players, X-ray scanners, radar receivers, and biometric scanning systems all depend on the FFT to extract frequency information from signals that vary over time and space. And in each case, speed is of the essence—the faster the frequency data is obtained, the more analysis can be performed.
The goal of this chapter is to present the theory behind the fast Fourier transform and show how it can be implemented in OpenCL. In particular, we’ll focus on the Cooley-Tukey algorithm, which is the most popular of the algorithms used to compute the FFT. This requires that the size of the data set be a power of 2, but many algorithms exist for analyzing data sets of different sizes.
In my opinion, the simplest way to understand the FFT is to study the discrete Fourier transform (DFT) first, and see how this simple algorithm can be accelerated by taking advantage of the DFT’s mathematical properties. But before exploring the DFT, this chapter will discuss the theory behind frequency analysis.