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 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 (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.
ApplicationCompared to other approaches, CORDIC is a clear winner when a hardware multiplier is unavailable (e.g. in a microcontroller) or when you want to save the gates required to implement one (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 good old-fashioned power series are generally faster than CORDIC.
Mode of operationCORDIC 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
v0:
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.
More formally, every iteration calculates a rotation, which is performed by multiplying the vector
vi with the
rotation matrix Ri:
The rotation matrix R is given by:
If we extract
cos(γ) from the rotation matrix, the calculation becomes:
The purpose of σ
i is to determine the direction of the rotation, and can have the values of -1 or 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:
where
We can ignore
Ki 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 (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 β.
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.
Implementation in MATLABThe 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. %%Initializationv=[1;0];sigma=1; Kn=prod(1./sqrt(1+2.^(-2*(0
n-1)))));%%Iterationsfor 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;
Implementation in CThe 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 algorithmfloat arctanTable[iterations]; // in Radiansfloat K = 0.6073; // Kfloat v_x,v_y; // Vector v; x and y componentsfor(int i=0; i < iterations; i++) { arctanTable
= atan(pow(2,-i));}float vnew_x; // To store the new value of x;for(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; } // 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; } v_x = vnew_x;}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.
- Vladimir Baykov, Problems of Elementary Functions Evaluation Based on Digit by Digit (CORDIC) Technique, PhD thesis, Leningrad State Univ. of Electrical Eng., 1972
- Schmid, Hermann, Decimal computation. New York, Wiley, 1974
- V.D.Baykov,V.B.Smolov, Hardware implementation of elementary functions in computers, Leningrad State University, 1975, 96p.
- 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.
- Vladimir D.Baykov, Vladimir B.Smolov, Special-purpose processors: iterative algorithms and structures, Moscow, Radio & svjaz, 1985, 288 pages
- M. E. Frerking, Digital Signal Processing in Communication Systems, 1994
- Vitit Kantabutra, On hardware for computing exponential and trigonometric functions, IEEE Trans. Computers 45 (3), 328-339 (1996)
- Andraka, Ray, A survey of CORDIC algorithms for FPGA based computers
- Henry Briggs, Arithmetica Logarithmica. London, 1624, folio
- CORDIC Bibliography Site
External links
