Signal Processing in C

CHAPTER 12

The Fast Fourier Transform

The discrete Fourier transform (DFT) is a powerful tool for digital signal processing. The only problem is its large computational burden. Calculating a DFT on N points requires on the order of N² multiplications and additions. There is a technique called the fast Fourier transform (FFT) that reduces this to the order of N log(N) operations of each kind. The FFT was already used by C. F. Gauss in 1805! However, knowledge of Gauss's work was not widespread, and in 1965 the FFT was reinvented and became known for a time as the Cooley-Tukey DFT. (See [3] for a survey of numerical transforms including the FFT. The reference to Gauss himself is [5].)

12.1 THE BRUTE FORCE METHOD

The discrete Fourier transform is a linear map from the set of functions on a finite Abelian group G to the set of functions on the group of characters . The set of complex-valued functions on a group G with N elements is an N-dimensional vector space with the vector elements indexed by the group elements. In other words, the Fourier transform is a linear map from one N-dimensional vector space to another. It is therefore expressible as an N × N matrix. If the group is G = /N