Comprehensive review on fast Fourier transform types and their applications

Here in this paper a review of some Fast Fourier Transform (FFT) algorithms are presented. FFT employs the idea of dividing the Discreet Fourier Transform (DFT) to smaller ones and compute each transform separately, in addition to transform the signals in time domain to frequency domain. There are several types of FFT, some of them deals with even samples (Radix II), while the other deals with any even samples. Off course there are types that deal with odd samples, but they are somehow complicated. Than we introduce other algorithm Sparse Fast Fourier Transform (SFT) which outperform the old FFT and have better performance when we have very large input sequence. Than the multidimensional FFT is reviewed. In addition to summarized some FFT's applications.