ABSTRACT
FFT is a very efficient method for computing the DFT coefficients. It reduces the number of complex multiplications from N2 in case of DFT to simply N/2log2(N) In the case of FFT. The only restriction on the algorithm is that the sequence x(ne) should consist of 2m Samples, where m is a positive integer – in other words, the number N of samples in the sequence should be a power of 2, i.e., N = 2,4,8,16,... etc. If x(n) does not contain 2m samples, then we append it with zeros until the number of samples in the resulting sequence becomes a power of 2.
There are several ways in which the FFT could ). We shall study radix-2 FFT algorithms, namely,
Decimation-in-Frequency method.
Decimation-in-Time method.
Other types include radix-4 and split-radix methods.
