Asee peer logo

Unfolding The Wings Of The Butterfly: An Alternative Explanation For Ffts

Download Paper |

Conference

2006 Annual Conference & Exposition

Location

Chicago, Illinois

Publication Date

June 18, 2006

Start Date

June 18, 2006

End Date

June 21, 2006

ISSN

2153-5965

Conference Session

Electrical ET Curriculum

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

89

Request a correction

Paper Authors

biography

Kathleen Ossman University of Cincinnati

visit author page

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.

visit author page

Download Paper |

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