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 N2 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].)


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 images. 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 = images/Nimages

Get Signal Processing in C 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.