International Journal of Scientific and Engineering Research (IJSER)
Research Articles => Engineering, IT, Algorithms => Topic started by: IJSER Content Writer on February 18, 2012, 02:05:34 am

Author : Er. Manoj Arora, Er. R S Chauhan, Er.Lalit Bagga
International Journal of Scientific & Engineering Research Volume 3, Issue 1, January2012
ISSN 22295518
Download Full Paper : PDF (http://www.ijser.org/onlineResearchPaperViewer.aspx?FPGAPrototypingofHardwareImplementationofCORDICAlgorithm.pdf)
Abstract In 1959 J. E. Volder presents a new algorithm for the real time solution of the equations raised in navigation system. This algorithm was the best replacement of analog navigation system by the digital. CORDIC algorithm used for the fast calculation of elementary functions like multiplication, division, trigonometric functions, logarithmic function, and various conversions like conversion of rectangular to polar coordinate, conversion between BCD and binary coded information. In the present time CORDIC algorithm have a number of applications in the field of communication, 3D graphics, signal processing and a lot more. This review paper presents the prototype of hardware implementation of CORDIC algorithm using Spartan –II series FPGA, with constraint to area efficiency and throughput architecture.
Index Terms : CORDIC; FPGA; Discrete Fourier Transform (DFT); Discrete Cosine transform (DCT); Iterative CORDIC; Pipelined CORDIC,SVD.
1 INTRODUCTION
Coordinate Rotation Digital Computer is abbreviated as ORDIC. The main concept of this algorithm is based on the very simple and long lasting fundamentals of twodimensional geometry. The first description for iterative approach of this algorithm is firstly provided by Jack E. Volder in 1959”[1]”. CORDIC algorithm provides an efficient way of rotating the vectors in a plane by simple shift add operation to estimate the basic elementary functions like trigonometric operations, multiplication, division and some other operations like logarithmic functions, square roots and exponential functions. Most of the applications either in wireless communication or in digital signal processing are based on microprocessors which make use of a single instruction and a bunch of addressing modes for their working. As these processors are costs efficient and offer extreme flexibility but yet are not suited for some of these applications. For most of these applications the CORDIC algorithm is a best suited alternative to that architecture which rely on simple multiply and add hardware. The pocket calculators and some of DSP objects like FFT, DCT, and demodulators are some common fields where CORDIC algorithm is found.
In 1971 CORDIC based computing received attention, when John Walther showed that, by varying a few simple parameters, it could be used as a single algorithm for implementation of most of the mathematical functions. During this period Mr Cochran invent various algorithms and
showed that CORDIC is much better approach for scientific calculator applications. The popularity of CORDIC is enhanced there after mainly due to its potential for efficient and lowcost implementation of a large class of applications which include the generation of trigonometric, logarithmic and transcendental elementary functions; complex number multiplication, eigenvalue computation, matrix inversion, solution of linear systems and singular value decomposition (SVD) for signal processing, image processing, and general scientific computation. Some other popular and upcoming applications are:
1) Direct frequency synthesis, digital modulation and coding for speech/music synthesis and communication;
2) Direct and inverse kinematics computation for robot manipulation;
3) Planar and threedimensional vector rotation for graphics and animation.
Although CORDIC algorithm is not a very fast algorithm for use but this algorithm is followed due to its very simple implementation and also the same architecture can be used for all the applications which is based on simple shift add operation.
2 CORDIC ALGORTHM
CORDIC is acronym for COordinate Rotation DIgital Computer. The CORDIC algorithm is used to evaluate real time calculation of the exponential and logarithmic functions using the iterative rotation of the input vector. This rotation of a given vector (xi, yi) is realized by means of a sequence of rotations with fixed angles which results in overall rotation through a given angle or result in a final angular argument of zero. Fig1.shows all the computing steps involved in CORDIC algorithm.
In the fig.1 “[1]” the angle αi is the amount of rotation angle for each iteration and this rotational angle is defined by the following equation:
α I = tan121 (1)
Fig.1 CORDIC computing step
So this angular moment of vector can easily be achieved by the simple process of shifting and adding. Now if we consider the iterative equation as shown on the next page
xi+1 = xi cos αi – yi sin αi
yi+1 = xi sin αi + yi cosαi (2)
from equation (1), we can write as
xi+1 = cos αi (xi– yi tan αi)
yi+1 = cos αi (xi tan αi + yi )
Now here we define scale factor kn which is same as shown below:
Ki = cos αi or 1/√(1+22i)
So for the above written two equation we can rewrite them as
xi+1 = (1/√(1+22i) ) Ri cos( αi + θ )
yi+1 = (1/√(1+22i) ) Ri cos( αi  θ ) (3)
OR xi+1 = ki (xi  2i yi)
yi+1 = ki (yi + 2i xi )
Now as shown in above equation the direction of rotation may be clock wise or anticlockwise means unpredictable for different iterations so for that ease we define a binary notation di to identify the direction. It can equal either +1 or 1. So putting di in above equation we get:
xi+1 = ki (xi  di 2i yi)
yi+1 = ki (yi + di 2i xi) (4)
As the value of di depends on the direction of rotation. If we move clockwise then the value of di is +1 otherwise 1.Now these iterations are basically combination of elementary functions like addition , subtraction , shifting and table look up operations and no multiplication and division functions are required in the CORDIC operation.
In CORDIC algorithm, a number of microrotations are combined in different ways to realize some different functions. This is achieved by properly controlling the direction of the successive microrotations. So on the basis of controlling these microrotations we can divide CORDIC in two parts and this control on successive microrotations can be achieved in the following two ways:
Vectoring mode:  In this type of mode the ycomponent of the input vector is forced to zero. So this type of consideration yields computation of magnitude and phase of the input vector.
Rotation mode:  In the rotation mode θcomponent is forced to zero. and this mode yields computation of a plane rotation of the input vector by a given input phase θ0 .
2.1 Vectoring mode
As earlier written the in vectoring mode of CORDIC algorithm the magnitude and the phase of the input vector are calculated. The ycomponent is forced to zero that means the input vector(x0, y0) is rotated towards the xaxis. So the CORDIC iteration in vectoring mode is controlled by the sign of ycomponent as well as xcomponent. Means in the vectoring mode the rotator rotates the input vector through any angle to align the result in the xaxis direction.
So in the vectoring mode the CORDIC equations are:
Read More: Click here... (http://www.ijser.org/onlineResearchPaperViewer.aspx?FPGAPrototypingofHardwareImplementationofCORDICAlgorithm.pdf)