• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar

ALLSIGNALPROCESSING.COM

Learn signal processing online

  • Home
  • Courses
  • Courses
  • About
  • FAQ
  • My Account
  • Blog
  • News
  • Contact
  • Login
  • Logout
  • Get All Access

Fast Fourier Transform (FFT) Algorithm

February 8, 2019 by 3200 Creative

fast Fourier transform diagram

In this lesson you will learn the principles at the core of the decimation-in-time fast Fourier transform algorithm. The (re)discovery of the fast Fourier transform  algorithm by Cooley and Tukey in 1965 was perhaps the most significant event in the history of signal processing. There is evidence that Gauss first developed a fast Fourier transform-type algorithm in 1805.

Fourier analysis and the discrete Fourier transform (DFT) are central players in signal processing. The fast Fourier transform algorithm (FFT) reduces the computation of a length  N DFT from order  N^2 to order  N \log_2 N operations when  N is a power of 2. The FFT  achieves a very large reduction in the cost of computation as  N becomes large. There are FFT algorithms for many different factorizations of  N.

Understanding the principles behind the fast Fourier transform  algorithm will position you to effectively apply the FFT and appreciate its significance in signal processing. Furthermore, the general approach for reducing computation in the FFT  – breaking a large problem up into a combination of smaller problems – also applies in many other algorithms.

Prerequisites

  • Important Discrete Fourier Transform Properties

Key Concepts and Screenshots

Concepts and Screenshots for The Fast Fourier Transform (FFT) Algorithm

Supplementary Information

  • A.V. Oppenheim and R.W. Schafer, Discrete-Time Signal Processing. 3rd Edition, Pearson Higher Education, 2010. Chapter 9.
  • M.T. Heideman, D.H. Johnson, C.S. Burrus, “Gauss and the history of the fast Fourier transform,” IEEE ASSP Magazine, pp. 14-21, October 1984.
  • J.W. Cooley and J.W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Math. Comput., vol. 19, no. 2, pp. 297-301, April 1965.
  • J.W. Cooley, “How the FFT gained acceptance,” IEEE Signal Processing Magazine, vol. 9, pp. 10-13, January 1992.
  • E.O. Brigham, The Fast Fourier Transform and Its Applications. Prentice Hall, 1988.
QuizzesStatus
1

The Fast Fourier Transform Algorithm


← Previous Lesson Next Lesson →

Filed Under: Uncategorized

Primary Sidebar

Course Lessons

  • Discrete Fourier Transform: Sampling the Discrete-Time Fourier Transform

  • Important Discrete Fourier Transform Properties

  • Fast Fourier Transform (FFT) Algorithm

  • Introduction to Circular Convolution and Filtering with the Discrete Fourier Transform

  • Circular Convolution Property of the Discrete Fourier Transform

  • Filtering with the Discrete Fourier Transform

  • The Discrete Fourier Transform Approximation to the Fourier Transform

  • The Effect of Windowing on the Discrete Fourier Transform Approximation to the Fourier Transform

  • Windows and the Discrete-Time Fourier Transform: Trading Resolution for Dynamic Range

  • An Example of Approximating the Fourier Transform with the Discrete Fourier Transform

  • Jupyter Notebook: Explore the Windowed DFT

  • The Short-Time Fourier Transform and the Spectrogram

  • Jupyter Notebook: Explore the Spectrogram

  • A Matrix Interpretation of the Discrete Fourier Transform

  • A Matrix Interpretation of the Fast Fourier Transform Algorithm

Courses

  • Foundations

  • Time Domain LTI Systems

  • Fourier Series and Transforms

  • Sampling and Reconstruction

  • The DFT and Applications

  • The Z-Transform

  • Intro to Filter Design

  • IIR Filter Design

  • FIR Filter Design

  • Random Signal Characterization

  • Basis Representations of Signals

  • Estimation of Power Spectra and Coherence

  • Introduction to Signal Estimation and Detection Theory

  • MMSE Filtering and Least-Squares Problems

Copyright © 2023 ALLSIGNALPROCESSING.COM | Site Design by 3200 Creative

  • Terms of Service
  • Privacy Policy
  • Contact