Using the FFT

A brute force calculation of a length N DFT requires a number of operations roughly proportional to N2. Thus, a 1024-point DFT would require about a million multiplications and about a million additions. Luckily, the DFT algorithm can be simplified to a form in which the required number of calculations is proportional to $N \log(N)$. This simplified algorithm is referred to as the Fast Fourier Transform or FFT. A 1024-point FFT can be calculated with only about 10,000 operations.

McGill ©2004-2019 McGill University. All Rights Reserved.
Maintained by Gary P. Scavone.