Skip to content

Read more about Fast Fourier Transforms

Fast Fourier Transforms

(0 reviews)

No ratings

C. Sidney Burrus, Rice University

Copyright Year: 2012

Publisher: OpenStax CNX

Language: English

Formats Available

Conditions of Use

Attribution Attribution
CC BY

Table of Contents

  • 1 Preface: Fast Fourier Transforms
  • 2 Introduction: Fast Fourier Transforms
  • 3 Multidimensional Index Mapping
  • 4 Polynomial Description of Signals
  • 5 The DFT as Convolution or Filtering
  • 6 Factoring the Signal Processing Operators
  • 7 Winograd's Short DFT Algorithms
  • 8 DFT and FFT: An Algebraic View
  • 9 The Cooley-Tukey Fast Fourier Transform Algorithm
  • 10 The Prime Factor and Winograd Fourier Transform Algorithms
  • 11 Implementing FFTs in Practice
  • 12 Algorithms for Data with Restrictions
  • 13 Convolution Algorithms
  • 14 Comments: Fast Fourier Transforms
  • 15 Conclusions: Fast Fourier Transforms
  • 16 Appendix 1: FFT Flowgraphs
  • 17 Appendix 2: Operation Counts for General Length FFT
  • 18 Appendix 3: FFT Computer Programs
  • 19 Appendix 4: Programs for Short FFTs

Ancillary Material

Submit ancillary resource

About the Book

This book focuses on the discrete Fourier transform (DFT), discrete convolution, and, particularly, the fast algorithms to calculate them. These topics have been at the center of digital signal processing since its beginning, and new results in hardware, theory and applications continue to keep them important and exciting. This book uses an index map, a polynomial decomposition, an operator factorization, and a conversion to a filter to develop a very general and efficient description of fast algorithms to calculate the discrete Fourier transform (DFT). The work of Winograd is outlined, chapters by Selesnick, Pueschel, and Johnson are included, and computer programs are provided.

About the Contributors

Author

C. Sidney Burrus received the PhD degree from Stanford University in 1965 after which he joined the faculty at Rice University where he is now Research Professor in ECE, Senior Strategist for Connexions, the Maxfield and Oshman Professor Emeritus of Electrical and Computer Engineering, and Dean Emeritus of the George R. Brown School of Engineering. From 1972 to 1978 he was master of Lovett College and from 1984 to 1992 he was chairman of the ECE Department at Rice. From 1992 to 1998 he was director of the Computer and Information Technology Institute (CITI). From 1998 to 2005 he was dean of Engineering. He has been part of the Connexions Project since 1999. In 1975-76 and again in 1979-80 he was a Guest Professor at the University of Erlangen in Germany, and during the academic year 1989-90 he was a Visiting Professor in the Electrical Engineering and Computer Science Department at MIT.

Contribute to this Page

Suggest an edit to this book record