Fast Fourier Transform

Fast Fourier Transform 

The discrete Fourier transform (DFT) of the polynomial A(x) or equivalently the vector of coefficients (a0,a1,...,an-1) is defined as the values of the polynomial at the points x=wn,k,i.e it is the vector:

The fast Fourier transform is a method that allows computing the DFT in  O(nlog⁡n) time. The basic idea of the FFT is to apply divide and conquer. We divide the coefficient vector of the polynomial into two vectors, recursively compute the DFT for each of them, and combine the results to compute the DFT of the complete polynomial.

Working of Recursive FFT Procedure :

The FFT operates by decomposing an N point time domain signal into N time domain signals each composed of a single point.The second step is to calculate the N frequency spectra corresponding to these N time domain signals. Lastly, the N spectra are synthesized into a single frequency spectrum.