# An Introduction to the CORDIC Algorithm

CORDIC (coordinate rotation
digital computer) is a hardware-efficient iterative method which uses
rotations to calculate a wide range of elementary functions.

This
article reviews the basics of this algorithm and later demonstrates how
we can use CORDIC to calculate the sine and cosine of a given angle.### Rotate to Perform a Wide Range of Operations

For the time being, let's forget about electronics and go back to high-school mathematics to see which operations can be achieved by simply rotating a vector.Suppose that we have an efficient system that receives a vector and rotates it by an arbitrary angle

. Choosing the origin as the center of rotation, we will get to the point (

#####
*Equation 1.*

*Equation 1.*

Figure 1 illustrates this rotation below.

#####
**Figure 1.** Rotating the input vector by

**Figure 1.**Rotating the input vector by

#####
*. Image courtesy of UCLA (PDF).*

If we choose

and

#####
*Equation 2.*

*Equation 2.*

Therefore, we can simply calculate sine and cosine of an arbitrary angle through rotation.

For another example of the functions that can be calculated from rotation, consider the vector magnitude,

. To achieve this, we only need to rotate the input vector so that it is aligned with the x-axis. In this way,

Interestingly, the list of the functions that can be calculated from rotation is relatively long. Inverse trigonometric functions such as arctan, arcsin, arccos, hyperbolic and logarithmic functions, polar to rectangular transform, Cartesian to polar transform, multiplication, and division are some of the most important operations that can be obtained from variants of rotation.

The CORDIC algorithm attempts to provide a hardware-efficient method for calculating these functions. “Hardware-efficient” means that the algorithm avoids the use of multipliers and relies on only shifts and additions/subtractions. Note that other methods of implementing these functions, such as utilizing power series, usually need dedicated multipliers.

### The Basics of CORDIC

Equation 1 can be simplified to:#####
*Equation 3.*

*Equation 3.*

The above equation shows that for one rotation, we need to perform 4 multiplications (plus some additions/subtractions). The question that remains is, How can we avoid these multiplications?

The CORDIC algorithm resorts to two fundamental ideas to achieve rotation without multiplication. The first fundamental idea is that rotating the input vector by an arbitrary angle

is equal to rotating the vector by several smaller angles,

The second fundamental idea is that we can choose the small elementary angles in a way that

for

Note that, in practice, we face a limited accuracy and the convergence of these equations is important. Fortunately, the equations converge and by increasing

, we can increase the accuracy of calculations.

Choosing angles such that

is an inverse power of two will allow us to perform these multiplications using bit shifts, but we still need to perform two other multiplications by

#####
**Figure 2. **Multiplication by cos(Î¸) acts as a scaling factor.

**Figure 2.**Multiplication by cos(Î¸) acts as a scaling factor.

Now let's examine the effect of this scaling factor when applying the successive elementary rotations of the CORDIC algorithm. Suppose that we want to rotate the input vector by

which is

#####
*Equation 4.*

*Equation 4.*

For the second rotation, we obtain:

#####
*Equation 5.*

*Equation 5.*

Substituting Equation 4 into Equation 5 gives us:

#####
*Equation 6.*

*Equation 6.*

For the third rotation, we will have:

#####
*Equation 7.*

*Equation 7.*

Finally, we obtain:

#####
*Equation 8.*

*Equation 8.*

Equation 8 has two implications. First, each rotation mandates a scaling factor which appears in the final calculations. This means that it is possible to ignore the

term of equation (3) and take the scaling factor into account at the end of the algorithm. Second, as we proceed with the algorithm, the angle of rotation rapidly becomes smaller and smaller. Hence,

For example, with

,

In summary, we can ignore the

term of Equation 3 and apply a scaling factor of approximately

We can use a constant scaling factor because the algorithm uses some predefined angles in each elementary rotation. You may wonder if we still need a multiplier to take the scaling factor into account. As discussed later, we will see that we can sometimes apply the scaling factor somewhere else in the system without using a multiplier.

Therefore, omitting the scaling factor term from Equation 3, we obtain the following equations for the CORDIC algorithm:

#####
*Equation 9.*

*Equation 9.*

where

determines the sign of the elementary angle and will be discussed in the next section of the article. The above equation shows that the algorithm will always perform a certain number of rotations with the predefined angles (for example, 12 rotations), and the only thing that the algorithm determines is whether each rotation will go clockwise or counter-clockwise during each iteration (choose

### Negative Feedback Mechanism of CORDIC

Equation 9 allows us to rotate a vector by some predefined angles without multiplication but how can we rotate the vector by an arbitrary angle? In other words, how should we choose the value offor each iteration of the algorithm? This is accomplished by simply recording the angle of previous rotations and comparing the overall achieved rotation with the desired angle.

If the desired rotation is larger (smaller) than previously achieved rotation, then we need to rotate counter-clockwise (clockwise) in the next iteration. For example, assume we want a rotation of

. At the beginning of the algorithm, we have achieved zero rotation and

This will lead to a

rotation in this iteration. Since

The described procedure is actually a negative feedback mechanism which computes the overall rotation and compares that to a reference value and chooses the new rotations in a way that minimizes the error signal (

).

The above mechanism is taken into account by adding another equation to the set of expressions in Equation 9 as follows:

#####
*Equation 10.*

*Equation 10.*

This equation accumulates the angle of all the previous rotations and compares that with an initial value

. For example, in the rotation by

There are two points that need to be further clarified here: first, as you may have noticed, we have to know the angle of each iteration,

. For example, if we design a twelve-iteration algorithm, the value of the first twelve angles which satisfy

Second, the algorithm will perform the same number of iterations for any given

. For example, although

The following figure shows the implementation of a single iteration in the CORDIC algorithm:

#####
**Figure 3.** Implementation of Equation 9 for one iteration. Image courtesy of UCLA (PDF).

**Figure 3.**Implementation of Equation 9 for one iteration. Image courtesy of UCLA (PDF).

### A Numerical Example

As an example, we will apply the CORDIC algorithm to calculate the sine and cosine ofwith

Iteration ( |

) |

- | - |

Now we can take the scaling factor into account:

which is pretty close to the

As mentioned previously, we can sometimes avoid multiplication by the scaling factor. This is possible in the above example. To this end, we can apply the scaling factor to the initial values and start from

and