 Open Access
 Total Downloads : 250
 Authors : M. S. Parvathy, Anas A. S
 Paper ID : IJERTV3IS20817
 Volume & Issue : Volume 03, Issue 02 (February 2014)
 Published (First Online): 27022014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Design of an Optimized CORDIC for Fixed Angle of Rotation
M. S. Parvathy
PG student, VLSI & Embedded Systems, ECE Department TKM Institute of Technology
Karuvelil P.O, Kollam, Kerala691505, India
Anas A. S
Assistant professor, ECE Department TKM Institute of Technology
Karuvelil P.O, Kollam, Kerala691505, India
Abstract The CORDIC algorithm is a technique for efficiently implementing the trigonometric functions and hyperbolic functions.Vector rotation through fixed and known angles has wide applications in various areas. But there is no optimized coordinate rotation digital computer (CORDIC) design for vectorrotation through specific angles. FPGA based CORDIC design for fixed angle of rotation provides optimization schemes and CORDIC circuits for fixed and known rotations with different levels of accuracy. For reducing the area and time complexities, a hardwired preshifting scheme in barrelshifters of the CORDIC circuits is used. Pipelined schemes are suggested further for cascading dedicated singlerotation units and bi rotation CORDIC units for highthroughput and reduced latency implementations. The fixedpoint meansquarederror of the CORDIC circuit is analyzed and reduced. This design offers higher throughput, less latency and less areadelay product. The fixedangle CORDIC rotation would have wide applications in signal processing, games, animation, graphics and robotics. The coding is done in Verilog language, synthesized using Xilinx ISE

and simulated using ISim.
Keywords Coordinate rotation digital computer (CORDIC), digital signal processing (DSP) chip, VLSI

INTRODUCTION
The Coordinate Rotation DIgital Computer (CORDIC) algorithm has been used for many years for efficient implementation of vector rotation operations in hardware. CORDIC or Coordinate Rotation Digital Computer is a simple and hardwareefficient algorithm for the implementation of various elementary, especially trigonometric functions. Instead of using Calculus based methods such as polynomial or rational functional approximation, it uses simple shift, add, subtract and table lookup operations to achieve this objective. By making slight adjustments to the initial conditions and the LUT values, it can be used to efficiently implement Trigonometric, Hyperbolic, Exponential functions, Coordinate Transformations etc. using the same hardware. Since it uses only shiftadd arithmetic, VLSI implementation of such an algorithm is easily achievable.
The CORDIC algorithm was first proposed by Jack E Volder in 1959 [10], [11]. It is an iterative technique and consists of two modes of operation called rotation mode and vectoring mode. In either mode, the algorithm is rotation of an angle vector by a definite angle but in variable directions. This fixed rotation in variable direction is implemented through an iterative sequence of addition/subtraction followed by bitshift operation. The final result is obtained by appropriately scaling the result obtained after successive iterations. CORDIC works
by rotating the coordinate system through constant angles until the angle is reduces to zero.
CORDIC algorithm is very attractive for hardware implementation because less power dissipation, compactable & simple in design. Less power dissipation and compact because it uses only elementary shiftandadd operations to perform the vector rotation so it only needs the use of 2 shifter and 3 adder modules. Simplicity is due to elimination of multiplication with only addition, subtraction and bitshifting operation. Either if there is an absence of a hardware multiplier (e.g. C, P) or there is a necessity to optimize the number of logic gates (e.g. FPGA) CORDIC is the preferred choice. However, the major disadvantage of the CORDIC algorithm are large number of iterations required for accurate results and thus the speed is low and time delay is high, power consumption is high in some architecture types ,whenever a hardware multiplier is available, e.g. in a DSP microprocessor
Rotation of vectors through a fixed and known angle has wide applications in robotics, graphics, games, and animation
[3] [5]. Locomotion of robots is very often performed by successive rotations through small fixed angles and translations of the links. The translation operations are realized by simple additions of coordinate values while the new coordinates of a rotational step could be accomplished by suitable successive rotations through a small fixed angle which could be performed by a CORDIC circuit for fixed rotation. Similarly, interpolation of orientations between key frames in computer graphics and animation could be performed by fixed CORDIC rotations. There are plenty of examples of uniform rotation starting from electrons inside an atom to the planets and satellites. A simple example of uniform rotations is the hands of an animated mechanical clock which perform one degree rotation each time. There are several cases where highspeed constant rotation is required in games, graphic, and animation. The objects with constant rotations are very often used in simulation, modelling, games, and animation. The contributions of this paper are as follows,
Algorithm for optimization schemes for reducing the number of microrotations and for reducing the complexity of barrelshifters for fixedangle vectorrotation.

Shiftadd operations for corresponding scaling circuits.

A hardware preshifting scheme is suggested for reduction of barrelshifter complexity.

A cascaded pipelined circuit in which more than one CORDIC module in separate stages in a cascade. The cascade
of CORDIC modules is faster and involves less areadelay complexity.

An efficient CORDIC circuit using a pair of micro rotations, and named as Bi rotation CORDIC.


SYSTEM ARCHITECTURE
This section presents reference CORDIC circuit, optimization of Cordic circuit, hardwired preshifting scheme to reduce the complexity of barrel shifter in reference Cordic circuit and multiStage SingleRotation Cascaded Cordic Circuit.
.

Reference Cordic Circuit
Reference CORDIC circuit for vector rotation with initial vector (X, Y) rotate through an angle to obtain final vector (X, Y) through successive iterations is shown below. The rotationmode CORDIC algorithm to rotate a vector U= [Ux Uy] through an angle to obtain a rotated vector V= [Vx Vy] is given by
(Ux)i+1= (Ux) i (Uy )i 2i (1)
(Uy)i+1= (Uy) i + (Ux )i 2i (2)
i+1 = i – tan1(2i) (3)
such that when n is sufficiently large
T (4)
where = 1 if i <0 and = 1 otherwise, and K is the scalefactor of the CORDIC algorithm, given by,
K= (5)
Fig. 1. Reference CORDIC circuit for fixed Rotations
A reference CORDIC circuit for fixed rotations according to (1) and (2) is shown in Fig. 1. X0 and Y0 are fed as set/reset input to the pair of input registers and the successive feedback values Xi and Yi at the iteration are fed in parallel to the input registers. Note that conventionally we feed the pair of input registers with the initial values X0 and Y0 as well as the feedback values Xi and Yi through a pair of multiplexers.

Optimization of Cordic Circuit
Optimization schemes are for reducing the number of microrotations and for reducing the complexity of barrel shifters for fixedangle vectorrotation. Optimization is done for both micro rotations and scaling with the help of algorithm.
The steps involved in optimizng the Elementary angle set of Microrotations are as follows:

, maximum tolerable error between desired angle and approximated angle is given as an input.

Optimization algorithm searches starts with single micro rotation

If the microrotation that has smaller angle of deviation than cannot be found, the number of microrotations is increased by one.

Optimization algorithm is run again.

Based on the obtained microrotations, the parameters for scaling operation can be searched with the different objective function.
The steps involved in optimizing the scaling process are as follows:

k, maximum tolerable error between desired angle and approximated angle is given as an input.

Optimization algorithm searches starts with single term of scaling.

The number of scaling terms is increased by one until k is smaller than the given maximum deviation k, where k is deviation of ratio of approximated scale factor to actual scale factor from 1.

Optimization algorithm is run again.
For rotation of a vector through a known and fixed angle of rotation using a rotationmode CORDIC circuit, a set of a small number of predetermined elementary angles , for
0 im1}, where = arctan (2k(i)) is the elementary angle to be used for the ith microrotation in the CORDIC algorithm and m is the minimum necessary number of micro
rotations. Meanwhile, it is well known that the rotation through any angle, 0 < 2 can be mapped into a positive
rotation through 0 < /4 without any extra arithmetic
operations. Hence, as a first step of optimization, we perform the rotation mapping so that the rotation angle lies in the range of 0 < /4. In the next step, we minimize the number of elementary angles in the set } according to the accuracy requirements. The rotation mode CORDIC algorithm of (1),
(2) and (3) therefore, can be modified accordingly to have
= (6)
The set of micro rotations is optimized according to the algorithm which is described in section B. Since the elementary angles and direction of microrotations are
predetermined for the given angle of rotation, the angle estimation datapath is not required in the CORDIC circuit for fixed and known rotations. Moreover, because only a few elementary angles are involved in this case, the corresponding controlbits could be stored in a ROM of few words.
Fig. 2. Optimization of CORDIC circuit
The major contributors to the hardwarecomplexity in the implementation of a CORDIC circuit are the barrelshifters and the adders.
The optimization of CORDIC circuit is shown in Fig. 2.


Hardwired PreShifting Scheme
The barrelshifter used in the optimization CORDIC circuit increases the complexity of the circuit. In order to avoid the complexity of barrelshifter, a hardwired preshifting scheme is used. A barrelshifter for maximum of S shifts for word length L is implemented by [log2(S+1)] stages of demultiplexors, where each stage requires L number of 1:2 line MUXes. The hardwarecomplexity of barrelshifter, therefore, increases linearly with the wordlength and logarithmically with the maximum number of shifts. We can reduce the effective wordlength in the MUXes of the barrel shifters, and so also the number of stages of MUXes by simple hardwired preshifting.
The time involved in a barrelshifter could also be reduced by hardwired preshifting, since the delay of the barrelshifter is proportional to the number of stages of MUXes, and it also possible to reduce the number of stages by hardwired pre shifting scheme. The hardwired preshifting scheme is shown in Fig. 3.
If l is the minimum number of shifts in the set of selected microrotations, we can load only the (Ll) moresignificant bits (MSBs) of an input word from the registers to the barrel shifters, since the l less significant bits (LSBs) would get truncated during shifting. The barrelshifter, therefore, needs to implement a maximum of(s l) shifts only, where s is the maximum number of shifts in the set of selected micro rotations. The output of the barrelshifters are loaded as the (Ll) LSBs to the add/subtract units, and the l MSBs of the corresponding operand of add/subtract unit are hardwired to 0. Therefore, the hardwarecomplexity of a barrelshifter could be reduced by the hardwired preshifting approach.
Fig. 3. Hardwired preshifting circuit

MultiStage SingleRotation Cascaded Cordic Circuit
Multistage cascaded CORDIC circuit connects n number of single rotations in cascaded form. Here the initial vector values are provided to the first rotation module, whose output is provided as the input to the second rotation module and this goes on till the nth rotation module finally to obtain the final vector Xn and Yn. The multistage singlerotation cascaded CORDIC circuit is shown in Fig. 4.
Fig. 4. Multistage singlerotation cascaded CORDIC circuit
Each stage of the cascaded design consists of a dedicated rotationmodule that performs a specific microrotation. Each rotationmodule consists of a pair of adders or subtractors (depending on the direction of microrotation which it is required to implement). Each of the adders/subtractors loads one of the pair of inputs directly and loads the other input in a preshifted form at (Ls(i)) LSB locations, where s(i) is the number of rightshifts required to be performed to implement the microrotation. The s(i) MSB locations are hardwired to be zero. The rotationmodule in this case does not require input
from SBR since each adder module always performs either addition or subtraction.

Scaling Optimization
The generalized expression for the scalefactor given by
(5) can be expressed explicitly for the selected set of m1 micro rotations as
K= (7)
where k(i) for m1 is the number of shifts in the ith microrotation
An approximate scalefactor is the product of shiftadd terms of form
KA= (8)
where s(i) is the number of shifts performed for the ith iteration of = 1, and m2 is maximum number of scaling iterations required for the approximation. The scaling circuit using hardwired preshifting scheme is shown in Fig. 5. The scaling circuit based on approximated scaling factor, Ka shown in Fig. 5. can use hardwired preshifting for minimizing barrelshifter complexity.
Fig. 5. Scaling circuit using hardwired pre shifting scheme


SIMULATION RESULTS
The design entry is modelled using Verilog in Xilinx ISE Design Suite 14.1 and the simulation of the design is performed using ISim from Xilinx ISE to validate the functionality of the design. Here CORDIC design for vector rotation through fixed and known angle is simulated.

Reference CORDIC circuit for single iteration
Here the initial vector (X0, Y0) which is rotated through a series of microrotations or iteration say, 1st iteration, 2nd iteration etc to obtain the final vector (Xn, Yn).
Inputs – X = 0001 and Y = 0000
Shifted values q11 = 0001 and q21 = 0001 Outputs S1 = 0001 and S2 = 0001
Fig. 6. Reference CORDIC circuit for 1st iteration
In Fig. 6. input X and Y is shifted for the iteration value corresponding to (zero shift). The shifted value is then add/subtract to the input values according to sign bit values stored in SBR.
Fig. 7. Reference CORDIC circuit for 2nd iteration
In Fig. 7. the input X and Y is shifted for the iteration value corresponding to (one shift). The shifted value is then add/subtract to the input values according to sign bit values stored in SBR.
Inputs – X = 1000 and Y = 0010
Shifted values q11 = 0100 and q21 = 0001 Outputs S1 = 1001 and S2 = 0110

Multistage singlerotation cascaded CORDIC circuit
Multistage cascaded CORDIC circuit connects n number of single rotations in cascaded form Hre the initial vector values are provided to the first rotation module, whose output is provided as the input to the second rotation module and this goes on till the nth rotation module finally to obtain the final vector Xn and Yn. (Xn, Yn) is the final vector obtained
after vector rotation through n iterations from the initial vector (X0, Y0).
Fig. 8. Multistage singlerotation cascaded CORDIC circuit
In Fig. 8. the input initial values (X, Y) = (1, 0) is rotated by a fixed angle taken as . For , there are 7 numbers of iterations. The initial vector is rotated by the given angle to obtain the final vector (Xn, Yn).
Outputs Xn = 000000000000000011111000 and Yn = 000000000000000000111110 Angle Z0 = 0000000000000110110100010

Hardwired preshifting scheme
The barrelshifter used in the optimization CORDIC circuit increases the complexity of the circuit. In order to avoid the complexity of barrelshifter, a hardwired preshifting scheme is used. The barrelshifter needs to implement a maximum of(s l) shifts only, where s is the maximum number of shifts in the set of selected microrotations..
Fig. 9. Hardwired preshifting scheme
In this (Ll) MSBs are load to barrel shifters from the registers and load (ll) LSBs locations by keeping l MSBs as 0 to adder/subtractor module. In Fig. 9. the input initial values (X, Y) = (1, 0) is rotated by a fixed angle taken as . For 30 , there are 9 numbers of iterations. The initial vector is rotated by the given angle to obtain the final vector (Xn, Yn).


CONCLUSIONS

The Coordinate Rotation DIgital Computer (CORDIC) algorithm has been used for many years for efficient implementation of vector rotation operations in hardware. It is executed merely by table lookup, shift, and addition operations. In the rotation mode of CORDIC algorithm, given a vector with initial coordinate and a target rotation angle , the algorithm compute the final coordinate through a series of backward and forward rotation of the vector in an iterative manner. The project is intended to design an optimized circuit for vector rotation using CORDIC Algorithm. Optimization is performed for both Micro rotation and Scaling operation. The number of microrotations for rotation of vectors through fixed and known angles are optimized and several possible dedicated circuits are explored for rotationmode CORDIC processing with different levels of accuracy
REFERENCES

G.Sandhya, Syed Inthiyaz, Dr. Fazal Noor Basha, Power and Area Optimization for Pipelined CORDIC Processor Architecture in VLSI, International Journal of Engineering Research and Applications (IJERA), Vol. 2, Issue 3, pp.15881595, MayJun 2012.

L. Vachhani, K. Sridharan, and P. K. Meher, Efficient CORDIC algorithms and architectures for low area and high throughput implementation, IEEE Trans. Circuits Syst. II, vol. 56, no. 1, pp. 6165, Jan. 2009.

P.K.Meher, J.Valls, T.B. Juang, K. Sridharan, and K. Maharatna,
50 years of CORDIC: Algorithms, architectures and applications, IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 56, no. 9, pp.1893 1907, Sep.2009.

S. Y. Park and N. I. Cho, Fixedpoint error analysis of CORDIC processor based on the variance propagation formula, IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 51, no. 3, pp. 573584, Mar. 2005.

T. Lang and E. Antelo, Highthroughput CORDICbased geometry operations for 3D computer graphics, IEEE Trans. Comput., vol. 54, no. 3, pp. 347361, Mar. 2005.

K.Maharatna, S.Banerjee, E.Grass, M.Krstic, and A.Troya,
Modified virtually scaling free adaptive CORDIC rotator algorithm and architecture, IEEE Trans. Circuits Syst. for Video Technol., vol.15, no.11, pp.14631474, Nov. 2004.

S. Y. Park and N. I. Cho, Fixedpoint error analysis of CORDIC processor based on the variance propagation formula, IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 51, no. 3, pp. 573584, Mar. 2004.

Y. H. Hu and S. Naganathan, An angle recoding method for CORDIC algorithm implementation, IEEE Trans. Comput., vol. 42, no. 1, pp.99102, Jan. 1993.

K. J. Jones, 2D systolic solution to discrete Fourier transform, IEE Proc. Comput. Digit. Techn. vol. 136, no. 3, pp. 211216, May 1989.

J.S. Walther, A unified algorithm for elementary functions, in Proc. 38th Spring Joint Comput. Conf., pp. 379385, 1971.

J. E. Volder, The CORDIC trigonometric computing technique,
IRE Trans. Electron. Comput, vol. EC8, pp. 330334, Sep. 1959.