June 18, 2006
June 18, 2006
June 21, 2006
11.1365.1 - 11.1365.11
Unfolding the Wings of the Butterfly: An Alternative Explanation for FFTs
This paper discusses an approach to teaching Fast Fourier Transforms (FFTs) to engineering technology students using a set of graphics that not only illustrates how the FFT algorithm works but also gives students an idea of how an FFT algorithm might be programmed.
One of the most difficult topics to teach in an introductory course in Digital Signal Processing is Fast Fourier Transforms (FFTs) which are simply efficient algorithms for computing Discrete 1-6 Fourier Transforms (DFTs) in real-time. Most textbooks begin with an explanation of how the data points are divided into specific pairs followed by a set of complicated “subscript heavy” re- combining equations used to calculate larger FFTs from the smaller subset FFTs. These equations are typically followed with a Butterfly diagram designed to help visualize an FFT algorithm. The Butterfly diagram illustrates the progression of the re-ordered data through a series of interwoven multiply and add operations to reach the final FFT. In this paper, a quick summary of the traditional textbook approach to FFTs will be presented followed by a handout developed by the author to make the process easier for students to visualize.
Traditional Approach 2-6 Most digital signal processing textbooks present some variation of the following set of equations. An FFT algorithm simply breaks a DFT down into several 2-point DFTs by – j2π / N exploiting the symmetry properties of the twiddle factors: WN = e =cos(2π/N) – j sin(2π/N).
N−1 N/2 − 1 N/2 − 1
XDFT(k) = Σ x(n) (WN)nk = Σ x(2n) (WN)2nk + Σ x(2n+1) (WN)(2n+1)k n=0 n=0 n=0 Even Indices Odd Indices
N/2 − 1 N/2 − 1 XDFT(k) = Σ x(2n) (WN/2)nk + (WN)k Σ x(2n+1) (WN/2)nk = Two N/2-point DFTs n=0 n=0
Ossman, K. (2006, June), Unfolding The Wings Of The Butterfly: An Alternative Explanation For Ffts Paper presented at 2006 Annual Conference & Exposition, Chicago, Illinois. 10.18260/1-2--900
ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2006 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015