• 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

September 10, 2019 by

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.

Sign up now to access this and more than 30 other free lessons!

Primary Sidebar

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