CORDIC
CORDIC is a simple and efficient
algorithm to calculate
hyperbolic and
trigonometric functions. It is the algorithm of choice if no hardware multiplier is available, e.g. simple
microcontrollers and
FPGAs 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.
Encyclopedia
CORDIC is a simple and efficient
algorithm to calculate
hyperbolic and
trigonometric functions. It is the algorithm of choice if no hardware multiplier is available, e.g. simple
microcontrollers and
FPGAs 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 . CORDIC is particularly well-suited for handheld calculators, an application for which cost 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.
Application
Compared to other approaches, CORDIC is a clear winner when a hardware multiplier is unavailable or when you want to save the gates required to implement one . On the other hand, when a hardware multiplier is available , table-lookup methods and good old-fashioned power series are generally faster than CORDIC.
Mode of operation
CORDIC is a flexible algorithm that 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. If we wish to determine the sine or cosine for an angle we need to find the y or x coordinate of a point on the
unit circle corresponding to the wanted angle. Using CORDIC, we would start with the vector :
-
In the first iteration, this vector would be rotated 45° counterclockwise to get the vector . 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.
More formally, every iteration calculates a rotation, which is performed by multiplying the vector with the rotation matrix :
-
The rotation matrix R is given by:
-
If we extract from the rotation matrix, the calculation becomes:
-
The purpose of is to determine the direction of the rotation, and can have the values of -1 or 1. If we restrict the angle so that is 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:
-
where
-
We can ignore in the iterative process and then apply it afterward by a scaling factor:
-
which is calculated in advance and stored in a table. Additionally it can be noted that
-
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 .
The only task left is to determine if the rotation should be clockwise or counterclockwise at every iteration . 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 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 .
-
The values of must also be precomputed and stored. But for small angles, 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 , while the x coordinate is the cosine value.
Implementation in MATLAB
The following is a MATLAB implementation of CORDIC.
function v=cordic
% This function computes 'cos' and 'sin' of 'beta' 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;
%%Iterations
for j=0:n-1;
sigma=sign;
R=[1 -sigma*2^-j;sigma*2^-j 1];
v=R*v;
beta=beta-sigma*atan;
end
%% Computing output
v=v*Kn;
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 = .
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
float vnew_x; // To store the new value of x;
for
v_x *= K;
v_y *= K;
References
- Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, September 1959
- Daggett, D. H., Decimal-Binary conversions in CORDIC, IRE Transactions on Electronic Computers, Vol. EC-8 #5, pp335-339, IRE, September 1959.
- J. E. Meggitt, Pseudo Division and Pseudo Multiplication Processes, IBM Journal, April 1962.
- Schmid, Hermann, Decimal computation. New York, Wiley, 1974
- Senzig, Don, Calculator Algorithms, IEEE Compcon Reader Digest, IEEE Catalog No. 75 CH 0920-9C, pp139-141, IEEE, 1975.
- V.D.Baykov,S.A.Seljutin, Elementary functions evaluation in microcalculators, Moscow, Radio & svjaz,1982,64p.
- M. E. Frerking, Digital Signal Processing in Communication Systems, 1994
- Vitit Kantabutra, On hardware for computing exponential and trigonometric functions, IEEE Trans. Computers 45 , 328-339
- Henry Briggs, Arithmetica Logarithmica. London, 1624, folio
External links
