IMPLEMENTATION OF FFT ALGORITHM

Fast Fourier Transform (FFT) is a fast and efficient way of computing Discrete Fourier Transform (DFT). FFT is one of the exquisite and ubiquitous operations in the field of digital signal processing. Moreover, it is one of the critical components in Orthogonal Frequency Division Multiplexing (OFDM) [5] systems. FFT can be of two types, namely: Decimation in time (DIT) FFT and Decimation in frequency (DIF) FFT. For most of the real life situations like audio/image/video processing etc., DIT-FFT has an advantage over DIF-FFT since it does not require any output recording. In this paper, an efficient algorithm to compute 8 point FFT has been devised in which a butterfly unit (stage-I) computes the output and then feeds those outputs as inputs to the next butterfly units (stage-II/III) so as to compute the overall FFT.