This example shows how to use the Coordinate Rotation Digital Computer (CORDIC) algorithm to generate HDL code. The CORDIC algorithm can be used to compute trigonometric functions. The algorithm uses vector rotation to compute the sine, cosine, tangent, arcsine, arccosine, and arctangent functions. Vector rotation can also be used for polar to Cartesian, Cartesian to polar, vector magnitude, or (as a building block) DFT and DCT computations. The CORDIC algorithm is an iterative method for performing vector rotation by an arbitrary angle using shift and add techniques. Therefore it is suitable for hardware implementation. The implementation in this example is used for HDL code generation and test bench generation.
The algorithm used in this example is presented in a number of published papers. See References below.
Introduction to the CORDIC Algorithm
The basic equations for vector rotation are:
where x and y are the original coordinates before rotation, and x' and y' are the coordinates after rotation. This equation can be simplified by assuming that the tangent is a power of 2.
Then any angle of rotation can be obtained by performing successive smaller rotations. This assumption helps us to write equation 1 in the form of an iterative operation.
where the third equation is the angle accumulator.
These equations can be used in two different modes: rotation mode and vector mode. In rotation mode, the input vector rotates by a specific angle. In vector mode, the input vector rotates to the x axis.
In rotation mode the following equations are used:
The result after n rotations can be represented as:
where G is a constant and approaches to 1.647 when n approaches infinity.
In vector mode the following equations are used:
The result after n rotation can be represented as:
In the following five examples, equation 4 is implemented. To switch to vector mode, we just switch the condition (value of d) for clockwise or counterclockwise rotation.
Sine and Cosine
To calculate the sine and cosine functions, the CORDIC algorithm in rotational mode is used. The initial conditions are:
Using these initial conditions, equation 5 reduces to:
To calculate the arcsine function, the CORDIC algorithm is used in vector mode. The condition for d is:
Rotation produces the following equations:
Start with a vector on the x axis and rotate it so that its y component is c. The algorithm has good precision when
As the input approaches +/- 1, the error increases rapidly. The loss of accuracy is due to the gain of the rotation. When the vector is close to the y axis, the vector is shorter than the reference.
For the arccosine, we can use the same equation as we used for arcsine and replace the condition for d:
or simply calculate arcsine and use the following equality
Polar to Cartesian
Polar to Cartesian conversion is an extension to the sine and cosine calculation. In equation 5 let:
After n iterations the resultant x and y represents the Cartesian coordinate.
Cartesian to Polar/ Arctangant and Vector Magnitude
If we start with vector mode and let the initial angle be zero, then the angle accumulator and the x component of the result is:
Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, September, 1959, pp. 330-334
Ray Andraka, A Survey of CORDIC Algorithms for FPGA Based Computers, 1998, ACM 0-89791-978-5/98/01
Gene H. Golub and Charles F. Van Loan, MATRIX Computations, 3rd edition, Johns Hopkins University Press, 1996, section 5.2.3, "Givens QR Methods"