CORDIC

From Wikipedia, the free encyclopedia

CORDIC (digit-by-digit method, Volder`s algorithm) (for COordinate Rotation DIgital Computer) is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions. It is commonly used if no hardware multiplier (for example, simple microcontrollers and FPGAs) is available as it only requires small lookup tables, bitshifts and additions. Additionally, when implemented in soft or dedicated hardware the algorithm is suitable for pipelining. The modern CORDIC algorithm was first described in 1959 by Jack E. Volder, although it is similar to techniques published by Henry Briggs as early as 1624.

Originally, CORDIC was implemented in binary. In the 1970s, decimal CORDIC became widely used in pocket calculators, most of which operate not in binary but in binary-coded-decimal (BCD). CORDIC is particularly well-suited for handheld calculators, an application for which cost (and therefore gate count on the chip) is much more important than is speed. Also, for scientific calculators, CORDIC routines for trigonometric functions and hyperbolic functions can share most of their code.

Contents

[edit] Application

CORDIC is generally faster than other approaches when a hardware multiplier is unavailable (e.g. in a microcontroller), or when the number of gates required to implement one needs to be minimized (e.g. in an FPGA). On the other hand, when a hardware multiplier is available (e.g. in a DSP microprocessor), table-lookup methods and power series are generally faster than CORDIC.

[edit] Mode of operation

CORDIC can be used to calculate a number of different functions. This explanation shows how to use CORDIC in rotation mode to calculate sin and cos of an angle, and assumes the wanted 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 wanted angle needs to be found. Using CORDIC, we would start with the vector v0:

v_o = \begin{pmatrix} 1 \\ 0 \end{pmatrix}

In the first iteration, this vector would be rotated 45° counterclockwise to get the vector v1. Successive iterations will rotate the vector in the right direction by half the amount of the previous iteration until the wanted value has been achieved.

An illustration of the CORDIC algorithm in progress.
Enlarge
An illustration of the CORDIC algorithm in progress.

More formally, every iteration calculates a rotation, which is performed by multiplying the vector vi with the rotation matrix Ri:

v_{i+1} = R_{i}v_{i}\

The rotation matrix R is given by:

R_{i} = \begin{pmatrix} \cos \gamma_{i} & -\sin \gamma_{i} \\ \sin \gamma_{i} & \cos \gamma _{i}\end{pmatrix}

If we extract cos(γ) from the rotation matrix, the calculation becomes:

v_{i+1} = R_{i}v_{i} = \cos \gamma_{i} \begin{pmatrix} 1 & -\sigma_{i} \tan \gamma_{i} \\ \sigma_{i} \tan \gamma_{i} & 1 \end{pmatrix}\begin{pmatrix} x_{i} \\ y_{i} \end{pmatrix}

The purpose of σi is to determine the direction of the rotation, and can have the values of -1 or 1. If the angle βi is positive then σi is 1 otherwise it is -1. If we restrict the angle γ so that tan(γ) is 2 − i the tangent can be replaced by a multiplication by a power of two, which is easily done in digital computer hardware using a bit shift.

The calculation then becomes:

v_{i+1} = R_{i}v_{i} = \cos(\arctan(2^{-i}))\begin{pmatrix} 1 & -\sigma_{i} 2^{-i} \\ \sigma_{i} 2^{-i} & 1 \end{pmatrix}\begin{pmatrix} x_{i} \\ y_{i} \end{pmatrix} = K_{i}\begin{pmatrix} x_{i} -\sigma_{i} 2^{-i}y_{i} \\ x_{i}\sigma_{i} 2^{-i}+y_{i} \end{pmatrix}

where

K_i = \cos(\arctan(2^{-i}))\

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} \cos(\arctan(2^{-i})) = \prod_{i=0}^{n-1} 1/\sqrt{1 + 2^{-2i}}

which is calculated in advance and stored in a table. Additionally it can be noted that

K = \lim_{n \to \infty}K(n) \approx 0.607252935

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+1} = \beta_i - \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.

[edit] Implementation in MATLAB

The following is a MATLAB implementation of CORDIC.

function v=cordic(beta,n)
% This function computes 'cos' and 'sin' of 'beta' (in radians) using the
% cordic algorithm and returns the result in vector 'v'. 'n' is the number of
% iterations. Increasing 'n' will increase the precision. 

%%Initialization
v=[1;0];
sigma=1; 
Kn=prod(1./sqrt(1+2.^(-2*(0:(n-1)))));

%%Iterations
for j=0:n-1;
   sigma=sign(beta);
   R=[1 -sigma*2^-j;sigma*2^-j 1];
   v=R*v;
   beta=beta-sigma*atan(2^-j);
end

%% Computing output 
v=v*Kn;

[edit] Implementation in C

The following is a C implementation of CORDIC using floats. Beta is the input angle in radians. We start with vector v = (1,0).

int iterations; // Number of times to run the algorithm
float arctanTable[iterations]; // in Radians
float K = 0.6073; // K
float v_x,v_y; // Vector v; x and y components

for(int i=0; i < iterations; i++) {
   arctanTable[i] = atan(pow(2,-i));
}

float vnew_x;   // To store the new value of x;
for(int i=0; i < iterations; i++) {
    // If beta is negative, we need to do a counter-clockwise rotation:
    if( beta < 0) {
       vnew_x = v_x + (v_y*pow(2,-i)); 
       v_y -= (v_x*pow(2,-i));  
       beta += arctanTable[i]; 
    }
    // If beta is positive, we need to do a clockwise rotation:
    else {
       vnew_x = v_x - (v_y*pow(2,-i));
       v_y += (v_x*pow(2,-i));
       beta -= arctanTable[i];
    }
    v_x = vnew_x;
}
v_x *= K;
v_y *= K;

[edit] Related algorithms

CORDIC is part of the class of "shift-and-add" algorithms, as are the logarithm and exponential algorithms derived from Henry Briggs' work. Another shift-and-add algorithm which can be used for computing many elementary functions is the BKM algorithm, which is a generalization of the logarithm and exponential algorithms to the complex plane. For instance, BKM can be used to compute the sine and cosine of a real angle x (in radians) by computing the exponential of 0 + ix, which is cosx + isinx. The BKM algorithm is slightly more complex than CORDIC, but has the advantage that it does not need a scaling factor (K).

[edit] References

[edit] External links

Retrieved from "http://en.wikipedia.org../../../c/o/r/CORDIC_b9d4.html"
In other languages