The Fast Fourier Transform (FFT) 2.4 2002/08/05 2004/06/02 10:07:40 GMT-5 Justin Romberg jrom@rice.edu Prashant Singh prash@ece.rice.edu Richard G. Baraniuk richb@rice.edu Mariyah Poonawala mariyah@rice.edu dft Fast Fourier Transform fft fourier Fourier Transform This module describes the fast Fourier Transform (FFT).

Introduction The Fast Fourier Transform (FFT) is an efficient O(NlogN) algorithm for calculating DFTs originally discovered by Gauss in the early 1800's rediscovered by Cooley and Tukey at IBM in the 1960's C.S. Burrus, Rice University's very own Dean of Engineering, literally "wrote the book" on fast DFT algorithms. The FFT exploits symmetries in the W matrix to take a "divide and conquer" approach. We won't talk about the actual FFT algorithm here, see these notes if you are interested in reading a little more on the idea behind FFT.

Speed Comparison How much better is O(NlogN) than O( N 2 )?

This figure shows how much slower the computation time of an O(NlogN) process grows.

N 10 100 1000 106 109 N2 100 104 106 1012 1018 NN 1 200 3000 6106 9109 Say you have a 1 MFLOP machine (a million "floating point" operations per second). Let N 1 million 10 6 . An O( N 2 ) algorithm takes 1012 flors → 10 6 seconds ≃ 11.5 days. An O( N N ) algorithm takes 6 10 6 Flors → 6 seconds. N 1 million is not unreasonable. 3 megapixel digital camera spits out 3 10 6 numbers for each picture. So for two N point sequences fn and hn. If computing ⊛ f n h n directly: O( N 2 ) operations. taking FFTs -- O(NlogN) multiplying FFTs -- O(N) inverse FFTs -- O(NlogN). the total complexity is O(NlogN). FFT + digital computer were almost completely responsible for the "explosion" of DSP in the 60's. Rice was (and still is) one of the places to do research in DSP.