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

• Greg Bernhardt
In summary, CORDIC (COordinate Rotation DIgital Computer) is an efficient algorithm used to calculate hyperbolic and trigonometric functions when hardware multipliers are not available. It involves rotating a complex number by multiplying it by a succession of constant values, which can be done using only shifts and additions. The algorithm also uses rotation matrices and trigonometric identities to achieve accurate results. Developed by Jack E. Volder in 1959, CORDIC is a simple and effective method for performing various mathematical operations in digital circuits.
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!

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.

## 1. What is the CORDIC algorithm and what is it used for?

The CORDIC (Coordinate Rotation Digital Computer) algorithm is a method for calculating various mathematical functions, such as trigonometric and hyperbolic functions, using only basic arithmetic operations. It is commonly used in digital signal processing and numerical analysis applications.

## 2. How does the digit-by-digit method of the CORDIC algorithm work?

The digit-by-digit method of the CORDIC algorithm involves breaking down a complex calculation into smaller, simpler steps. Each digit of the input is processed one at a time, using a series of rotation and scaling operations, until the desired precision is reached.

## 3. What is Volder's algorithm and how does it differ from the digit-by-digit method?

Volder's algorithm is a variation of the CORDIC algorithm that uses a different approach to calculate the desired function. It involves pre-calculating a set of angles and storing them in a lookup table, which allows for faster computation compared to the digit-by-digit method.

## 4. What are the advantages of using the CORDIC algorithm?

The CORDIC algorithm has several advantages, including its simplicity, efficiency, and versatility. It only requires basic arithmetic operations and is suitable for hardware implementation, making it a popular choice in digital signal processing applications.

## 5. Are there any limitations to the CORDIC algorithm?

While the CORDIC algorithm is useful for a wide range of applications, it does have some limitations. It may not be as accurate as other numerical methods and may require a larger number of iterations to achieve the desired precision. It is also limited to certain functions and may not be suitable for all types of calculations.

• General Math
Replies
2
Views
1K
• General Math
Replies
4
Views
928
• General Math
Replies
4
Views
789
• General Math
Replies
7
Views
1K
• Introductory Physics Homework Help
Replies
6
Views
700
• Programming and Computer Science
Replies
1
Views
1K
• Math Proof Training and Practice
Replies
8
Views
1K
• General Math
Replies
2
Views
3K
• Introductory Physics Homework Help
Replies
3
Views
1K
• Advanced Physics Homework Help
Replies
9
Views
1K