Redundant Number System Based Cordic For Fast Fourier Transform

Abstract

Digital Signal Processing (DSP) techniques find application from home appliances to Satellite applications. DSP involves complex mathematical computations and therefore, there is a need for high-speed mathematical processor. Trigonometric function calculation is one of the primary tasks performed in DSP applications. For long time microprocessor-based systems have been used to perform this task. Software algorithms used by the processor do not meet the highly demanding needs of all DSP tasks. Using hardware systems to perform these DSP task is a competent solution to this problem. Field Programmable Gate Arrays (FPGAs) are often used as co-processor to perform all the high speed tasks that can not be achieved by microprocessors. FPGAs are chosen because they are on-site programmable and are highly suitable for hardware implementations. The software solutions adopted by the microprocessor to implement trigonometric functions are computation intensive. They do not suit hardware platform because they need complex circuit to perform the mathematical operations. Among the existing hardware algorithm CO-ordinate Rotation DIgital Computer (CORDIC) is widely adopted because of its simplicity and speed efficiency. CORDIC is one such iterative hardware efficient algorithm that performs high seed mathematical operations in linear, circular and hyperbolic coordinate system and computes various trigonometric, logarithmic and transcendental functions fast with high degree of accuracy for DSP applications. The drawback of conventional CORDIC implementation, based on ripple carry adders or subtractions, is the internal carry propagation delay. To enhance the performance of CORDIC Redundant Arithmetic has been proposed. This arithmetic, due to its carry-free property, avoids the carry propagation from the LSB to MSB. Nevertheless, its use involves several difficulties. It is not possible to detect the sign of a redundant number without inspecting all the digits which requires a propagation from the MSB to the LSB. Hence, the decision criteria is chosen according to several most significant digits. Since, not all digits are examined there is the possibility that the sign is not determined. In such a case either the digit set {-1,0,1} can be chosen leading to a non-constant Scale factor or an arbitrary rotation has to be performed. In the first case, the scale factor has to be computed in parallel to the CORDIC iterations to ensure the convergence. In order to solve the problems of the redundant arithmetic based CORDIC several methods have been proposed. All of them maintain the scale factor constant. They have been classified in the three groups. Group I, which are based on an estimation of the sign like Double Rotation CORDIC, Correcting Rotation CORDIC, House holder CORDIC. Group II, Differential CORDIC algorithm. Group III, which are based on the pre-computation of the directions of the micro-rotation. The CORDIC algorithm is used for various applications like the Digital Chirp Generation, Fast Fourier Transform, Digital Filtering, etc. The main speed limiting operation in FFT is complex multiplication. Complex multiplication is one of the most time-critical and area-consuming operations in a FPGA implementation. The CORDIC in FFT architecture eliminates the need of complex multiplier and the need to store the Sine/Cosine factors in the twiddle factor ROM. The CORDIC based FFT architectures are well suited for the FPGAs where no memories are available to store the Sine/Cosine terms (like Actel family). To incorporate CORDIC a new butterfly is designed where required multiplication terms are given as input vector to the CORDIC block as discussed in the thesis. This project work involves design, VHDL implementation and FPGA prototyping of Redundant arithmetic blocks, CORDIC processor, Predicting CORDIC Processor and its applications to Digital Chirp Generator and FFT. The project work has been carried out in several stages. It started with the design of the architecture and its bit-accurate implementation on MATLAB. The RTL design was carried out in VHDL. The designs were simulated in the Modelsim, synthesized using the Xilinx synthesis Tool (XST), and finally implemented using placing and routing Tool. Implemented design was downloaded on the Xilinx Vertex board along with Chipscope. All the results from MATLAB simulation and logical synthesis have been discussed.