17. The Fast Fourier Transform (FFT)
Frequency analysis is a crucial part of many computational tasks, from communications to oil exploration to code breaking. Speed is critical: The faster a radar system can analyze the frequencies of a reflected signal, the faster it can respond to impending threats.
The fast Fourier transform (FFT) is the most common method of analyzing frequency information in signals. When a new digital signal processor enters the market, one of the first benchmarks engineers look at is how quickly it can compute an FFT. There have been many variations of this algorithm since J.W. Cooley and John Tukey wrote their famous 1965 paper, but the Cooley-Tukey FFT is still the most widely used.
This chapter is concerned with implementing ...
Get Programming the Cell Processor: For Games, Graphics, and Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
