HARDWARE IMPLEMENTATION OF FFT ALGORITHM

Abstract

The study investigates hardware implementation of Fast Fourier Transform (FFT), considering hardware complexity and computational accuracy. The direct computation of FFT involves complex multiplications. Thus, hardware implementation of FFT results in high hardware complexity. This problem can be addressed by exploiting CORDIC (COrdinate Rotation Digital Computer) algorithm in FFT implementation. In FFT computation, the CORDIC algorithm is used to perform complex multiplications. This converts the complex multiplications into shift and adds operations which are very easy to implement in hardware. Hence, this approach reduces the hardware complexity of FFT implementation. Various CORDIC algorithms available in literature are discussed in detail. Two new CORDIC architectures are proposed. Both the proposed CORDIC architectures are suitable for pipelined implementation. The CORDIC architecture proposed in chapter 2 uses unique angle set at each pipelined stage which results in latency of only 7 clock cycles. Further, suitable approximation of sine and cosine function using the terms with only negative power of two 2−𝑖 makes the architecture completely scaling-free. On the other hand, the proposed CORDIC architecture in chapter 3 has the very low latency of only 5 clock cycles. This low latency can be achieved due to the use of efficient mixture of rotation angles at each pipelined stage. Additionally, the suitable use of Taylor series approximation of sine and cosine functions makes the architecture completely scaling-free. Performance of two proposed architectures is compared the other CORDIC architecture present in literature. These architectures are coded in VerilogHDL, synthesised in Xilinx ISE14.7 and mapped onto SPARTAN 3E XC3S500E-FG320-5 FPGA device. The comparison shows that proposed CORDIC architecture in chapter 2 has better accuracy, while the architecture proposed in chapter 3 has best performance in terms of slice-delay product. Finally, radix-2 four-point DIT-FFT is implemented in Virtex-4 XC4VLX25-FF668 FPGA device by exploiting two proposed CORDIC architectures. The comparison of these two implementations is performed by considering hardware utilization and error in computation of FFT. The outputs of FFT implementations are analysed and verified using Xilinx ChipScope Pro Analyse