Exploring CORDIC Algorithm: Digit-by-Digit Method & Volder's Algorithm

[Greg Bernhardt]

Definition/Summary

CORDIC (digit-by-digit method, Volder's algorithm) (stands for COordinate Rotation DIgital Computer) is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions. It is commonly used when no hardware multiplier is available as the only operations it requires are addition, subtraction, bitshift and table lookup.

Equations



Extended explanation

CORDIC revolves around the idea of "rotating" the phase of a complex number, by multiplying it by a succession of constant values. However, the multiplies can all be powers of 2, so in binary arithmetic they can be done using just shifts and adds; no actual multiplier is needed.

This explanation shows how to use CORDIC in rotation mode to calculate sine and cosine of an angle, and assumes the desired angle is given in radians and represented in a fixed point format. To determine the sine or cosine for an angle β, the y or x coordinate of a point on the unit circle corresponding to the desired angle must be found. Using CORDIC, we would start with the vector v0:

$$v_0 = \left(\begin{array}{c} 1 \\ 0 \end{array}\right)$$

In the first iteration, this vector would be rotated 45° counterclockwise to get the vector v1. Successive iterations will rotate the vector in one or the other direction by size decreasing steps, until the desired angle has been achieved. Step i size is Artg(1/(2(i-1))) where i 1,2,3,….
An illustration of the CORDIC algorithm in progress.

More formally, every iteration calculates a rotation, which is performed by multiplying the vector vi − 1 with the rotation matrix Ri:
$$v_{i} = R_{i}v_{i-1}\$$
The rotation matrix R is given by:
$$R_{i} = \left( \begin{array}{rr} \cos \gamma_{i} & -\sin \gamma_{i} \\ \sin \gamma_{i} & \cos \gamma _{i}\end{array} \right)$$
Using the following two trigonometric identities
$$\begin{align} \cos \alpha & = & {1 \over \sqrt{1 + \tan^2 \alpha}} \\ \sin \alpha & = & {{\tan \alpha} \over \sqrt{1 + \tan^2 \alpha}} \end{align}$$
the rotation matrix becomes:
$$R_{i} = {1 \over \sqrt{1 + \tan^2 \gamma_{i}}} \begin{pmatrix} 1 & -\tan \gamma_{i} \\ \tan \gamma_{i} & 1 \end{pmatrix}$$
The expression for the rotated vector vi = Rivi − 1 then becomes:
$$v_{i} = {1 \over \sqrt{1 + \tan^2 \gamma_{i}}} \begin{pmatrix} x_{i-1} &-& y_{i-1} \tan \gamma_{i} \\ x_{i-1} \tan \gamma_{i} &+& y_{i-1} \end{pmatrix}$$
where xi − 1 and yi − 1 are the components of vi − 1. Restricting the angles γi so that tanγi takes on the values \pm 2^{-i} the multiplication with the tangent can be replaced by a division by a power of two, which is efficiently done in digital computer hardware using a bit shift. The expression then becomes:

$$v_{i} = K_{i}\begin{pmatrix} x_{i-1} &-& \sigma_{i} 2^{-i} y_{i-1} \\ \sigma_{i} 2^{-i} x_{i-1} &+& y_{i-1} \end{pmatrix}$$
where
$$K_i = {1 \over \sqrt{1 + 2^{-2i}}}$$
and σi can have the values of −1 or 1 and is used to determine the direction of the rotation: if the angle βi is positive then σi is 1, otherwise it is −1.

We can ignore Ki in the iterative process and then apply it afterward by a scaling factor:
$$K(n) = \prod_{i=0}^{n-1} K_i = \prod_{i=0}^{n-1} 1/\sqrt{1 + 2^{-2i}}$$
which is calculated in advance and stored in a table, or as a single constant if the number of iterations is fixed. This correction could also be made in advance, by scaling v0 and hence saving a multiplication. Additionally it can be noted that

$$K = \lim_{n \to \infty}K(n) \approx 0.6072529350088812561694 [3]$$
to allow further reduction of the algorithm's complexity. After a sufficient number of iterations, the vector's angle will be close to the wanted angle β. For most ordinary purposes, 40 iterations (n = 40) is sufficient to obtain the correct result to the 10th decimal place.

The only task left is to determine if the rotation should be clockwise or counterclockwise at every iteration (choosing the value of σ). This is done by keeping track of how much we rotated at every iteration and subtracting that from the wanted angle, and then checking if βn + 1 is positive and we need to rotate clockwise or if it is negative we must rotate counterclockwise in order to get closer to the wanted angle β.

$$\beta_{i} = \beta_{i-1} - \sigma_i \gamma_i. \quad \gamma_i = \arctan 2^{-i},$$
The values of γn must also be precomputed and stored. But for small angles, arctan(γn) = γn in fixed point representation, reducing table size.

As can be seen in the illustration above, the sine of the angle β is the y coordinate of the final vector vn, while the x coordinate is the cosine value.

* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!

 

[fresh_42]

The CORDIC algorithm was presented in 1959 by Jack E. Volder. In the original version, it was thus possible to form trigonometric functions such as sine, cosine and tangent as well as the multiplication and division of numbers solely by the additions and shift operations (shift-and-add operations) which can be easily implemented in digital circuits. Shift operations to the numerical base 2 are very easy to implement in digital circuits by appropriate interconnection.