13. Fast Fourier Transform

By Sadasivan Puthusserypady, Technical University of Denmark, Denmark

Downloaded: 966 times

Published: 31 Mar 2021

© 2021 Sadasivan Puthusserypady

Abstract

Fast Fourier transforms (FFT) are widely used algorithms in digital signal processing for applications in several fields including almost all engineering disciplines, science, and mathematics. The basic ideas for the FFT algorithms were proposed by Cooley and Tukey in 1965 [13]. In 1994, Gilbert Strang described the FFT as the most important numerical algorithm of our lifetime1. In an article that was published in 2000 in the IEEE magazine on Computing in Science and Engineering, FFT algorithm was listed as one of the Top 10 Algorithms of 20th Century2.