Unfolding The Wings Of The Butterfly: An Alternative Explanation For Ffts
- Conference
- Location
-
Chicago, Illinois
- Publication Date
-
June 18, 2006
- Start Date
-
June 18, 2006
- End Date
-
June 21, 2006
- ISSN
-
2153-5965
- Conference Session
- Tagged Division
-
Engineering Technology
- Page Count
-
11
- Page Numbers
-
11.1365.1 - 11.1365.11
- DOI
-
10.18260/1-2--900
- Permanent URL
-
https://peer.asee.org/900
- Download Count
-
473
Paper Authors
Kathleen Ossman University of Cincinnati
Dr. Kathleen Ossman is an assistant professor in the Electrical and Computer Engineering Technology Department at the University of Cincinnati. She received a BSEE and MSEE from Georgia Tech in 1982 and a Ph.D. from the University of Florida in 1986. Her interests include feedback control systems and digital signal processing.
Abstract
NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract
Unfolding the Wings of the Butterfly: An Alternative Explanation for FFTs
Abstract
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.
Introduction
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