Fpga implementation of high-radix and mixed-radix, scaling-free cordic algorithms for fft implementation

Abstract

All the signals in the real world are analog. A few decades back, researchers developed systems that directly process analog signals. These analog signal processing systems have very less immunity to noise. However, soon after the introduction of high-speed analog-to-digital and digital-to-analog data converters, the way the analog signal is processed has entirely changed. Nowadays the traditional way to process analog signals is to convert them into digital signals, and use digital signal processing. Digital signals can be processed more efficiently, due to the tremendous advancement in digital circuits. The discrete Fourier transform (DFT) is a key signal processing algorithm (used for signal transformation and analyses), and it is used for many real-time applications. However, most of these applications demand high-performance. Since DFT has very high computation complexity (O(N2)), its VLSI implementation is not practical. Fast Fourier transform (FFT) algorithm given by Cooly-Tukey is mostly used to compute the N-point DFT when N is the integer power of two. The FFT algorithm decreases the computational complexity of DFT to O(Nlog(N)) by decomposing the computations of DFT (of a sequence of length N), into successively smaller DFT, and taking advantage of the periodicity and symmetry properties of the complex twiddle factor. Hence, FFT is mostly used in the VLSI implementations, for real-time DSP applications. The crucial component in the FFT implementation, is the butterfly engine which uses complex adder, subtractor, and multiplier. In this thesis, we propose a high-performance CORDIC algorithm for rotation mode to carry out the complex multiplication. The purpose of using the CORDIC algorithm is to reduce the hardware complexity of the butterfly engine by replacing complex multiplier with our proposed CORDIC algorithm based rotator. We propose a high-radix CORDIC algorithm to perform the two-dimensional vector rotation as radix-2b CORDIC algorithm takes n b iterations to compute the total rotation for n bit precision. Further, CORDIC algorithm needs only rotational angles to carry out complex multiplication, which reduces the need for large memory to store the twiddle factors. The main concern for the high-radix CORDIC algorithm is the compensation of the scale factor. To solve this problem, we also propose a mixed-radix, scaling-free CORDIC algorithm. In our proposed scaling-free CORDIC algorithm, the Taylor series approximation of sine and cosine is used for a high-radix CORDIC algorithm to achieve the scaling-free rotation of the two-dimensional vector. Further, our proposed CORDIC algorithm is designed in rotation mode and optimized by removing the Z datapath for the DSP applications for which the angle of rotation is known in advance. Finally, the multi-path delay commutator (MDC) FFT algorithm is implemented with our proposed CORDIC algorithm based rotator on FPGA. The our proposed design is compared with existing designs considering the critical parameters of the hardware implementation (latency, resource-utilization, and accuracy in terms of SNR and PSNR).