Efficient Realization of Fast Fourier Transform based on Distributed Arithmetic

Abstract

Global positioning system (GPS) plays a major role in real time communications and our spotlight is to calculate the communication delay in GPS system. The backend operation of GPS navigation system is convolution. GPS devices convolve two signals, one from satellite and other is shifted version of time. Fast Fourier Transform (FFT) is recognized as one of the most efficient building-block in performing convolution between two real time signals. Some of the applications includes Signal Processing, Data Analysis, Medical Imaging and digital formats like JPEG, MP3, H.264. Since Distributed Arithmetic (DA) takes the values in bit-serial fashion it suits for real time signal processing applications. DA is a method that can be employed to perform inner dot product between two signals: Fixed and varying signal by using shifters and adders. This project reveals a new integration approach for computing using DA. The proposed design will be implemented for 8-bit butterfly structure by incorporating DA technique. Finally, the results of proposed butterfly structure will be composed with existing butterfly structure for equal length. The performance evaluation of LUT and LUT-less based FFT butterfly structure designs can be evaluated using Xlinix ISE.