Quantcast

Documentation Center

  • Trial Software
  • Product Updates

CORDIC Algorithm Using Simulink® Blocks

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:

Equation 1

$$ x' = cos(\theta) [ x - y tan(\theta)]  $$

$$ y' = cos(\theta) [ y + x tan(\theta)]  $$

$$ \theta = \mbox {Rotation Angle} $$

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.

Equation 2

$$ tan(\theta) = \pm 2^{-n} $$

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.

Equation 3

$$ x_{n+1} = K_{n} [ x_{n} - y_{n} d_{n} 2^{-n}] $$

$$ y_{n+1} = K_{n} [ y_{n} + x_{n} d_{n} 2^{-n}] $$

$$ z_{n+1} = z_{n} - d_{n} atan(2^{-n}) $$

$$ K_{n} = cos(atan(2^{-n})) = 1 / \sqrt{1+2^{-2n}} $$

$$ d_{n} = \pm 1 $$

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:

Equation 4

$$ x_{n+1} = K_{n} [ x_{n} - y_{n} d_{n} 2^{-n}] $$

$$ y_{n+1} = K_{n} [ y_{n} + x_{n} d_{n} 2^{-n}] $$

$$ z_{n+1} = z_{n} - d_{n} atan(2^{-n}) $$

$$ d_{n} = \mbox {-1 if } z_{n} < 0 \mbox{, +1 otherwise} $$

The result after n rotations can be represented as:

Equation 5

$$ x_{n} = G_{n} [ x_{0} cos(\theta_{0}) - y_{0} sin(\theta_{0})] $$

$$ y_{n} = G_{n} [ y_{0} cos(\theta_{0}) + x_{0} sin(\theta_{0})] $$

$$ \theta_{n} = 0 $$

$$ G_{n} = \Pi_{n} \sqrt{1+2^{-2n}} $$

where G is a constant and approaches to 1.647 when n approaches infinity.

In vector mode the following equations are used:

Equation 6

$$ x_{n+1} = K_{n}.[ x_{n} - y_{n} . d_{n} . 2^{-n}] $$

$$ y_{n+1} = K_{n}.[ y_{n} + x_{n} . d_{n} . 2^{-n}] $$

$$ z_{n+1} = z_{n} - d_{n} . atan(2^{-n}) $$

$$ d_{n} = \mbox {+1 if } y_{n} < 0 \mbox{, -1 otherwise} $$

The result after n rotation can be represented as:

Equation 7

$$ x_{n} = G_{n} \sqrt {x_{0}^2 +  y_{0}^2 } $$

$$ y_{n} = 0 $$

$$ \theta_{n} = \theta_{0} + atan(y_{0}/x_{0}) $$

$$ G_{n} = \Pi_{n} \sqrt{1+2^{-2n}} $$

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:

$$ x_{0} = 1/G_{n} $$

$$ y_{0} = 0 $$

Using these initial conditions, equation 5 reduces to:

$$ x_{n} = cos(\theta_{0}) $$

$$ y_{n} = sin(\theta_{0}) $$

open sine-cosine modelopen sine-cosine model

Arcsine

To calculate the arcsine function, the CORDIC algorithm is used in vector mode. The condition for d is:

$$ d_{n} = \mbox {+1 if } y_{n} < c \mbox{, -1 otherwise} $$

$$ c = \mbox{input argument} $$

Rotation produces the following equations:

$$ x_{n} = \sqrt{(G_{n} x_{0})^2 - c^2} $$

$$ y_{n} = c $$

$$ z_{n} = z_{0} + asin(c/G_{n} x_{0}) $$

Start with a vector on the x axis and rotate it so that its y component is c. The algorithm has good precision when

$$ -1 < c/G_{} . x_{0} < 1 $$

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.

open arcsine modelopen arcsine model

Arccosine

For the arccosine, we can use the same equation as we used for arcsine and replace the condition for d:

$$ d_{n} = \mbox {+1 if } x_{n} < c \mbox{, -1 otherwise} $$

or simply calculate arcsine and use the following equality

$$ acos(\theta) = \pi/2 - asin(\theta)  $$

open arccosine modelopen arccosine model

Polar to Cartesian

Polar to Cartesian conversion is an extension to the sine and cosine calculation. In equation 5 let:

$$ x_{0} = \mbox {r polar magnitude} $$

$$ z_{0} = \theta \mbox { polar phase} $$

$$ y_{0} = 0 $$

After n iterations the resultant x and y represents the Cartesian coordinate.

$$ x_{n} = r cos(\theta) $$

$$ y_{n} = r sin(\theta) $$

open polar to Cartesian modelopen polar to Cartesian model

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:

$$ z_{n} = atan(y_{0}/x_{0}) $$

$$ x_{n} = G_{n} \sqrt{x_{0}^2 + y_{0}^2} $$

open Cartesian to polar modelopen Cartesian to polar model

References

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"
Was this topic helpful?