Fast Fourier Transforms

Fast Fourier Transforms

By C. Sidney Burrus (editor)
Book Description

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.

As far as we can tell, Gauss was the first to propose the techniques that we now call the fast Fourier transform (FFT) for calculating the coefficients in a trigonometric expansion of an asteroid's orbit in 1805. However, it was the seminal paper by Cooley and Tukey in 1965 that caught the attention of the science and engineering community and, in a way, founded the discipline of digital signal processing (DSP).

The impact of the Cooley-Tukey FFT was enormous. Problems could be solved quickly that were not even considered a few years earlier. A flurry of research expanded the theory and developed excellent practical programs as well as opening new applications. In 1976, Winograd published a short paper that set a second flurry of research in motion. This was another type of algorithm that expanded the data lengths that could be transformed efficiently and reduced the number of multiplications required. The ground work for this algorithm had be set earlier by Good and by Rader. In 1997 Frigo and Johnson developed a program they called the FFTW (fastest Fourier transform in the west) which is a composite of many of ideas in other algorithms as well as new results to give a robust, very fast system for general data lengths on a variety of computer and DSP architectures. This work won the 1999 Wilkinson Prize for Numerical Software.

It is hard to overemphasis the importance of the DFT, convolution, and fast algorithms. With a history that goes back to Gauss and a compilation of references on these topics that in 1995 resulted in over 2400 entries, the FFT may be the most important numerical algorithm in science, engineering, and applied mathematics. New theoretical results still are appearing, advances in computers and hardware continually restate the basic questions, and new applications open new areas for research. It is hoped that this book will provide the background, references, programs and incentive to encourage further research and results in this area as well as provide tools for practical applications.

Studying the FFT is not only valuable in understanding a powerful tool, it is also a prototype or example of how algorithms can be made efficient and how a theory can be developed to define optimality. The history of this development also gives insight into the process of research where timing and serendipity play interesting roles.

Several chapters or sections are written by authors who have extensive experience and depth working on the particular topics. Ivan Selesnick had written several papers on the design of short FFTs to be used in the prime factor algorithm (PFA) FFT and on automatic design of these short FFTs. Markus Püschel has developed a theoretical framework for “Algebraic Signal Processing" which allows a structured generation of FFT programs and a system called “Spiral" for automatically generating algorithms specifically for an architicture. Steven Johnson along with his colleague Matteo Frigo created, developed, and now maintains the powerful FFTW system: the Fastest Fourier Transform in the West. I sincerely thank these authors for their significant contributions.

Table of Contents
  • Chapter 1. Preface: Fast Fourier Transforms
    • 1.1.
  • Chapter 2. Introduction: Fast Fourier Transforms
  • Chapter 3. Multidimensional Index Mapping
    • 3.1.
      • The Index Map
  • Chapter 4. Polynomial Description of Signals
    • 4.1.
  • Chapter 5. The DFT as Convolution or Filtering
    • 5.1.
      • Goertzel's Algorithm (or A Better DFT Algorithm)
  • Chapter 6. Factoring the Signal Processing Operators
    • 6.1.
  • Chapter 7. Winograd's Short DFT Algorithms
    • 7.1.
      • The Automatic Generation of Winograd's Short DFTs
        • The Polynomial Product Stage
  • Chapter 8. DFT and FFT: An Algebraic View
    • 8.1.
      • Polynomial Algebras and the DFT
      • Algebraic Derivation of the Cooley-Tukey FFT
      • Discussion and Further Reading
  • Chapter 9. The Cooley-Tukey Fast Fourier Transform Algorithm
    • 9.1.
      • The Quick Fourier Transform, An FFT based on Symmetries
  • Chapter 10. The Prime Factor and Winograd Fourier Transform Algorithms
    • 10.1.
  • Chapter 11. Implementing FFTs in Practice
    • 11.1.
      • FFTs and the Memory Hierarchy
      • Adaptive Composition of FFT Algorithms
        • The problem to be solved
        • The space of plans in FFTW
          • Rank-1 plans
      • Generating Small FFT Kernels
  • Chapter 12. Algorithms for Data with Restrictions
    • 12.1.
  • Chapter 13. Convolution Algorithms
    • 13.1.
      • Fast Convolution by the FFT
      • Block Signal Processing
      • Number Theoretic Transforms for Convolution
  • Chapter 14. Comments: Fast Fourier Transforms
    • 14.1.
  • Chapter 15. Conclusions: Fast Fourier Transforms
  • Chapter 16. Appendix 1: FFT Flowgraphs
    • 16.1.
  • Chapter 17. Appendix 2: Operation Counts for General Length FFT
    • 17.1.
  • Chapter 18. Appendix 3: FFT Computer Programs
    • 18.1.
  • Chapter 19. Appendix 4: Programs for Short FFTs
    No review for this book yet, be the first to review.
      No comment for this book yet, be the first to comment
      Also Available On
      App store smallGoogle play small
      Curated Lists
      • Pattern Recognition and Machine Learning (Information Science and Statistics)
        by Christopher M. Bishop
        Data mining
        by I. H. Witten
        The Elements of Statistical Learning: Data Mining, Inference, and Prediction
        by Various
        See more...
      • CK-12 Chemistry
        by Various
        Concept Development Studies in Chemistry
        by John Hutchinson
        An Introduction to Chemistry - Atoms First
        by Mark Bishop
        See more...
      • Microsoft Word - How to Use Advanced Algebra II.doc
        by Jonathan Emmons
        Advanced Algebra II: Activities and Homework
        by Kenny Felder
        See more...
      • The Sun Who Lost His Way
        Tania is a Detective
        by Kanika G
        See more...
      • Java 3D Programming
        by Daniel Selman
        The Java EE 6 Tutorial
        by Oracle Corporation
        See more...