FAST FOURIER TRANSFORM (FFT)

An algorithm for fast computation of DFT is FFT(Fast Fourier Transform).The FFT algorithm divides the N-point DFT input signal into 2 parts-even and odd signal values of the input. The even signal values can be directly found out whereas the odd signal values is just multiplied by an appropriate twiddle factor which overall reduces the complex multiplications for FFT. This happens because the signal is divided into 2 parts, so the computation is carried out only for N/2 signal values. This increases the speed of computations and makes FFT faster than other algorithms.