On fast Fourier transform

Fast Fourier transform (FFT) is an efficient algorithm for computing the discrete Fourier transform. The discovery of the FFT algorithm paved the way for widespread use of digital methods of spectrum estimation which influenced the research in almost every field of engineering and science. In this article, we will first introduce the continuous-time Fourier transform (CFT), discretetime Fourier transform and discrete Fourier transform (DFT) and then present an example to illustrate the relation between CFT and DFT. In particular, we bring out the fact that the DFT is a tool to estimate the samples of the CFT at uniformly spaced frequencies. Next, we introduce the FFT algorithm giving certain key steps in its development.