Abstract
This lecture overviews Fast Fourier Transform that has many applications in digital signal processing and analysis and in power spectrum estimation. It covers the following topics in detail: Transition from DFT to FFT, Decimation in Time (DIT) FFT, Decimation in Frequency (DIF) FFT, FFT Computation issues, Goertzel Algorithm, Bluestein Algorithm.
FFT butterfly.
DIT FFT
Fast-Fourier-Transform-v2.2.1-Summary