An Introduction to the CORDIC Algorithm - LEKULE

Breaking

3 Jun 2017

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 (
) by rotating the point (
) by




Equation 1.

Figure 1 illustrates this rotation below.


Figure 1. Rotating the input vector by
. Image courtesy of UCLA (PDF).

If we choose

 and
, after rotation we will have



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,
and the x component will give the vector magnitude.
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.

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,
,
, provided
. For example, a rotation of
is the same as three successive rotations by
,
, and
(note that we can use negative angles too).
The second fundamental idea is that we can choose the small elementary angles in a way that

for
. In this way, multiplication by
can be achieved by a bitwise shift which is a much faster operation compared to multiplication. You may wonder if, for a given
, we can satisfy the conditions of these two fundamental ideas simultaneously, i.e.
 while
.
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
. Note that the multiplications by
 act as a system gain (because both the x and y components need to be multiplied by the same scaling factor). If we ignore this scaling factor, the rotation angle will be correct but we still have to scale down both the x and y components to arrive at the final values of
and
. This is illustrated in Figure 2 where multiplications by
are not applied and, as a result,
and
 are achieved which are
times larger than
and
, respectively.


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
. The first rotation by
will give us:


Equation 4.

For the second rotation, we obtain:


Equation 5.

Substituting Equation 4 into Equation 5 gives us:


Equation 6.

For the third rotation, we will have:


Equation 7.

Finally, we obtain:


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,
tends toward unity.
For example, with

,
becomes
which leads to a scaling factor of
. As a result, if the algorithm is designed to have more than six iterations, looking at the four significant figures, we obtain the following scaling factor:



In summary, we can ignore the

term of Equation 3 and apply a scaling factor of approximately
at the end of the process regardless of the desired rotation angle. For a more demanding application where higher accuracy is required, you can consider more significant figures for the scaling factor. This generally comes at no cost because, as explained in the example at the end of the article, the scaling factor is usually stored as an initial value in the system.
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.

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
equal to +1 or -1).

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 of

for 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
, so
. This will bring about a rotation of
. In the second iteration, we see that the achieved rotation is still smaller than the target angle (
), so
.
This will lead to a

rotation in this iteration. Since
, the next iteration will choose
which means that a rotation of
will be applied clockwise and the overall rotation will be
. This process will go on until all the
iterations of the algorithm are performed.
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.

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

. For example, in the rotation by
, we must choose
 and consider the sign of
 to decide about the direction of the next rotation.
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
 should be stored in a lookup table (you can see this lookup table in Figure 3).
Second, the algorithm will perform the same number of iterations for any given

. For example, although
is exactly equal to
, the algorithm will not stop with three iterations because this will require a different scaling factor (with three iterations
will not be
!). In this case, three iterations will lead to
but the algorithm will continue until all the iterations are performed so that
is
and
is within the acceptable range.
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).

A Numerical Example

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

with
iterations. As previously mentioned, to calculate the sine and cosine with rotation, we have to choose
and
. The following table shows how the set of expressions in Equation 10 are evaluated for this example:

Iteration (
)
- -

Now we can take the scaling factor into account:

which is pretty close to the
. The y component gives the sine of
equal to
 which is a very good approximation of
.
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
so that the final multiplication is omitted. In other words, since the initial values are constants, the application of the scaling factor merely changes the constants that are used.

No comments: