## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 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  for a survey of numerical transforms including the FFT. The reference to Gauss himself is .)

## 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 ## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required