Spectrum Analyzer: Introduction to Fast Fourier Transform 2.19 2001/06/01 2003/08/01 11:21:39.062 GMT-5 Swaroop Appadwedula appadwed@uiuc.edu Douglas L. Jones dl-jones@uiuc.edu Michael L. Kramer kramer@ifp.uiuc.edu Dima Moussa dmoussa@uiuc.edu Brian Wade bwade@uiuc.edu Jake Janevitz jake@janevitz.com Daniel Grobe Sachs sachs@uiuc.edu Matthew J. Berry mjberry@uiuc.edu Mark A. Haun markhaun@uiuc.edu Swaroop Appadwedula appadwed@uiuc.edu Douglas L. Jones dl-jones@uiuc.edu Daniel Grobe Sachs sachs@uiuc.edu Matthew J. Berry mjberry@uiuc.edu Mark D. Butala butala@uiuc.edu Ricardo Anthony Radaelli-Sanchez ricky@alumni.rice.edu Robert L. Morrison rlmorris@uiuc.edu discrete Fourier transform DFT fast Fourier transform FFT discrete time Fourier transform DTFT spectral analysis block-based algorithms boxcar hamming mainlobe sidelobe twiddle-factor bit-reversed DSP The Fast Fourier transform (FFT) is an efficient algorithm for computing the Discrete Fourier Transform. The FFT is a block-based algorithm.

Introduction The Fast Fourier Transform (FFT) can be used to analyze the spectral content of a signal. Recall that the FFT is an efficient algorithm for computing the Discrete Fourier Transform (DFT), a frequency-sampled version of the DTFT.

DFT X k n 0 N 1 x n 2 N n k where n k 0 1 … N 1

Because the FFT is a block-based algorithm, its computation is performed at the block I/O rate, in contrast to other exercises in which processing occurred on a sample-by-sample basis.