 CORDIC

Trigonometry History
Usage
Functions
Generalized
Inverse functions
Further readingReference Identities
Exact constants
Trigonometric tablesLaws and theorems Law of sines
Law of cosines
Law of tangents
Law of cotangents
Pythagorean theoremCalculus Trigonometric substitution
Integrals of functions
Derivatives of functions
Integrals of inverse functionsCORDIC (digitbydigit 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 when no hardware multiplier is available (e.g., simple microcontrollers and FPGAs) as the only operations it requires are addition, subtraction, bitshift and table lookup.
Contents
Origins
The modern CORDIC algorithm was first described in 1959 by Jack E. Volder. It was developed at the aeroelectronics department of Convair to replace the analog resolver in the B58 bomber's navigation computer.^{[1]}
Although CORDIC is similar to mathematical techniques published by Henry Briggs as early as 1624, it is optimized for low complexity finite state CPUs.
John Stephen Walther at HewlettPackard further generalized the algorithm, allowing it to calculate hyperbolic and exponential functions, logarithms, multiplications, divisions, and square roots.^{[2]}
Originally, CORDIC was implemented using the binary numeral system. In the 1970s, decimal CORDIC became widely used in pocket calculators, most of which operate in binarycodeddecimal (BCD) rather than binary.
CORDIC is particularly wellsuited for handheld calculators, an application for which cost (e.g., chip gate count has to be minimized) is much more important than is speed. Also the CORDIC subroutines for trigonometric and hyperbolic functions can share most of their code.
Applications
Hardware
CORDIC is generally faster than other approaches when a hardware multiplier is unavailable (e.g., in a microcontroller based system), or when the number of gates required to implement the functions it supports should be minimized (e.g., in an FPGA).
On the other hand, when a hardware multiplier is available (e.g., in a DSP microprocessor), tablelookup methods and power series are generally faster than CORDIC. In recent years, the CORDIC algorithm is used extensively for various biomedical applications, especially in FPGA implementations.
Software
Many older systems with integeronly CPUs have implemented CORDIC to varying extents as part of their IEEE Floating Point libraries. As most modern generalpurpose CPUs have floating point registers with common operations such as add, subtract, multiply, divide, sin, cos, square root, log10, natural log, the need to implement CORDIC in them with software is nearly nonexistent. Only microcontroller or special safety and timeconstrained software applications would need to consider using CORDIC.
Mode of operation: rotation mode
CORDIC can be used to calculate a number of different functions. This explanation shows how to use CORDIC in rotation mode to calculate sine and cosine of an angle, and assumes the desired 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 desired angle must be found. Using CORDIC, we would start with the vector v_{0}:
In the first iteration, this vector would be rotated 45° counterclockwise to get the vector v_{1}. Successive iterations will rotate the vector in one or the other direction by size decreasing steps, until the desired angle has been achieved. Step i size is arctan(1/(2^{i−1})) for i = 1, 2, 3, ….
More formally, every iteration calculates a rotation, which is performed by multiplying the vector v_{i − 1} with the rotation matrix R_{i}:
The rotation matrix R is given by:
Using the following two trigonometric identities
the rotation matrix becomes:
The expression for the rotated vector v_{i} = R_{i}v_{i − 1} then becomes:
where x_{i − 1} and y_{i − 1} are the components of v_{i − 1}. Restricting the angles γ_{i} so that tan γ_{i} takes on the values the multiplication with the tangent can be replaced by a division by a power of two, which is efficiently done in digital computer hardware using a bit shift. The expression then becomes:
where
and σ_{i} can have the values of −1 or 1 and is used to determine the direction of the rotation: if the angle β_{i} is positive then σ_{i} is 1, otherwise it is −1.
We can ignore K_{i} in the iterative process and then apply it afterward by a scaling factor:
which is calculated in advance and stored in a table, or as a single constant if the number of iterations is fixed. This correction could also be made in advance, by scaling v_{0} and hence saving a multiplication. Additionally it can be noted that
 ^{[3]}
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 β.
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 v_{n}, while the x coordinate is the cosine value.
Mode of operation: vectoring mode
The rotationmode algorithm described above can rotate any vector (not only a unit vector aligned along the x axis) by an angle between 90° and +90°. Decisions on the direction of the rotation depend on β_{i} being positive or negative.
The vectoringmode of operation requires a slight modification of the algorithm. It starts with a vector the x coordinate of which is positive and the y coordinate is arbitrary. Successive rotations have the goal of rotating the vector to the x axis (and therefore reducing the y coordinate to zero). At each step, the value of y determines the direction of the rotation. The final value of β_{i} contains the total angle of rotation. The final value of x will be the magnitude of the original vector scaled by K. So, an obvious use of the vectoring mode is the transformation from rectangular to polar coordinates.
Software implementation
The following is a MATLAB/GNU Octave implementation of CORDIC that does not rely on any transcendental functions except in the precomputation of tables. If the number of iterations n is predetermined, then the second table can be replaced by a single constant. The twobytwo matrix multiplication represents a pair of simple shifts and adds. With MATLAB's standard doubleprecision arithmetic and "format long" printout, the results increase in accuracy for n up to about 48.
function v = cordic(beta,n) % This function computes v = [cos(beta), sin(beta)] (beta in radians) % using n iterations. Increasing n will increase the precision. if beta < pi/2  beta > pi/2 if beta < 0 v = cordic(beta + pi, n); else v = cordic(beta  pi, n); end v = v; % flip the sign for second or third quadrant return end % Initialization of tables of constants used by CORDIC % need a table of arctangents of negative powers of two, in radians: % angles = atan(2.^(0:27)); angles = [ ... 0.78539816339745 0.46364760900081 0.24497866312686 0.12435499454676 ... 0.06241880999596 0.03123983343027 0.01562372862048 0.00781234106010 ... 0.00390623013197 0.00195312251648 0.00097656218956 0.00048828121119 ... 0.00024414062015 0.00012207031189 0.00006103515617 0.00003051757812 ... 0.00001525878906 0.00000762939453 0.00000381469727 0.00000190734863 ... 0.00000095367432 0.00000047683716 0.00000023841858 0.00000011920929 ... 0.00000005960464 0.00000002980232 0.00000001490116 0.00000000745058 ]; % and a table of products of reciprocal lengths of vectors [1, 2^j]: Kvalues = [ ... 0.70710678118655 0.63245553203368 0.61357199107790 0.60883391251775 ... 0.60764825625617 0.60735177014130 0.60727764409353 0.60725911229889 ... 0.60725447933256 0.60725332108988 0.60725303152913 0.60725295913894 ... 0.60725294104140 0.60725293651701 0.60725293538591 0.60725293510314 ... 0.60725293503245 0.60725293501477 0.60725293501035 0.60725293500925 ... 0.60725293500897 0.60725293500890 0.60725293500889 0.60725293500888 ]; Kn = Kvalues(min(n, length(Kvalues))); % Initialize loop variables: v = [1;0]; % start with 2vector cosine and sine of zero poweroftwo = 1; angle = angles(1); % Iterations for j = 0:n1; if beta < 0 sigma = 1; else sigma = 1; end factor = sigma * poweroftwo; R = [1, factor; factor, 1]; v = R * v; % 2by2 matrix multiply beta = beta  sigma * angle; % update the remaining angle poweroftwo = poweroftwo / 2; % update the angle from table, or eventually by just dividing by two if j+2 > length(angles) angle = angle / 2; else angle = angles(j+2); end end % Adjust length of output vector to be [cos(beta), sin(beta)]: v = v * Kn; return
Hardware implementation
The number of logic gates for the implementation of a CORDIC is roughly comparable to the number required for a multiplier as both require combinations of shifts and additions. The choice for a multiplierbased or CORDICbased implementation will depend on the context. The multiplication of two complex numbers represented by their real and imaginary components (rectangular coordinates), for example, requires 4 multiplications, but could be realized by a single CORDIC operating on complex numbers represented by their polar coordinates, especially if the magnitude of the numbers is not relevant (multiplying a complex vector with a vector on the unit circle actually amounts to a rotation). CORDICs are often used in circuits for telecommunications such as digital down converters.
Related algorithms
CORDIC is part of the class of "shiftandadd" algorithms, as are the logarithm and exponential algorithms derived from Henry Briggs' work. Another shiftandadd 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 cos x + isin x. The BKM algorithm is slightly more complex than CORDIC, but has the advantage that it does not need a scaling factor (K).
History
Volder was inspired by the following formula in the 1946 edition of the CRC Handbook of Chemistry and Physics:
with ^{[1]}
Some of the prominent early applications of CORDIC were in the Convair navigation computers CORDIC I to CORDIC III,^{[1]} the HewlettPackard HP9100 and HP35 calculators,^{[4]} the Intel 80x87 coprocessor series until Intel 80486, and Motorola 68881.^{[5]}
Decimal CORDIC was first suggested by Hermann Schmid and Anthony Bogacki.^{[6]}
Notes
 ^ ^{a} ^{b} ^{c} J. E. Volder, "The Birth of CORDIC", J. VLSI Signal Processing 25, 101 (2000).
 ^ J. S. Walther, "The Story of Unified CORDIC", J. VLSI Signal Processing 25, 107 (2000).
 ^ J.M. Muller, Elementary Functions: Algorithms and Implementation, 2nd Edition (Birkhäuser, Boston, 2006), p. 134.
 ^ D. Cochran, "Algorithms and Accuracy in the HP 35", Hewlett Packard J. 23, 10 (1972).
 ^ R. Nave, "Implementation of Transcendental Functions on a Numerics Processor", Microprocessing and Microprogramming 11, 221 (1983).
 ^ H. Schmid and A. Bogacki, "Use Decimal CORDIC for Generation of Many Transcendental Functions", EDN Magazine, February 20, 1973, p. 64.
References
 Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, pp330334, September 1959
 Daggett, D. H., DecimalBinary conversions in CORDIC, IRE Transactions on Electronic Computers, Vol. EC8 #5, pp335–339, IRE, September 1959
 John S. Walther, A Unified Algorithm for Elementary Functions, Proc. of Spring Joint Computer Conference, pp379–385, May 1971
 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.*Full Text
 Senzig, Don, Calculator Algorithms, IEEE Compcon Reader Digest, IEEE Catalog No. 75 CH 09209C, 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, Specialpurpose 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), 328339 (1996)
 Andraka, Ray, A survey of CORDIC algorithms for FPGA based computers
 Henry Briggs, Arithmetica Logarithmica. London, 1624, folio
 CORDIC Bibliography Site, Shaoyun Wang, July 2011
 The secret of the algorithms, Jacques Laporte, Paris 1981
 Digit by digit methods, Jacques Laporte, Paris 2006
 Ayan Banerjee, FPGA realization of a CORDIC based FFT processor for biomedical signal processing, Kharagpur, 2001
 CORDIC Architectures: A Survey, B. Lakshmi and A. S. Dhar, Journal: VLSI Design, January 2010
 Implementation of a CORDIC Algorithm in a Digital DownConverter, C. Cockrum, Fall 2008
External links
 CORDIC Bibliography Site
 Another USENET discussion
 BASIC Stamp, CORDIC math implementation
 CORDIC as implemented in the ROM of the HP35  Jacques Laporte (step by step analysis, simulator running the real ROM with breakpoints and trace facility.
 CORDIC implementation in verilog.
 CORDIC information
 CORDIC Vectoring with Arbitrary Target Value
 PicBasic Pro, Pic18 CORDIC math implementation
 Python CORDIC implementation
 Simple C code for fixedpoint CORDIC
 The CORDIC Algorithm
 Tutorial and MATLAB Implementation  Using CORDIC to Estimate Phase of a Complex Number
 USENET discussion
 Descriptions of hardware CORDICs in Arx with testbenches in C++ and VHDL
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
CORDIC — (sigle de COordinate Rotation DIgital Computer : « calcul numérique par rotation de coordonnées ») est un algorithme de calcul des fonctions trigonométriques et hyperboliques, notamment utilisé dans les calculatrices. Il a été… … Wikipédia en Français
CORDIC — (COordinate Rotation DIgital Computer), o el método de dígito por dígito, o el algoritmo de Volder, es un simple y eficiente algoritmo para calcular funciones hiperbólicas y trigonométricas. Típicamente es usado cuando no hay disponible un… … Wikipedia Español
CORDIC — (Метод CORDIC от англ. COordinate Rotation DIgital Computer цифровой вычислитель поворота системы координат; метод «цифра за цифрой», алгоритм Волдера) итерационный метод сведения прямых вычислений сложных функций к выполнению… … Википедия
CORDIC — Der CORDIC Algorithmus (COordinate Rotation DIgital Computer) ist ein effizienter iterativer Algorithmus, mit dessen Hilfe sich viele Funktionen implementieren lassen, wie z. B. trigonometrische, exponential und logarithmische sowie auch die … Deutsch Wikipedia
Cordic — Der CORDIC Algorithmus (COordinate Rotation DIgital Computer) ist ein effizienter iterativer Algorithmus, mit dessen Hilfe sich viele Funktionen implementieren lassen, wie z. B. trigonometrische, exponential und logarithmische sowie auch die… … Deutsch Wikipedia
CORDIC — Cordinate Rotation Digital Computer ( > IEEE Standard Dictionary ) … Acronyms
CORDIC — Cordinate Rotation Digital Computer ( > IEEE Standard Dictionary ) … Acronyms von A bis Z
Regis Cordic — Regis John Rege Cordic (May 15, 1926 April 16, 1999) was an American radio personality and actor. His career in entertainment divides roughly in half: from 1948 to 1965, he was the dominant morning drive time radio host in Pittsburgh,… … Wikipedia
KDKA (AM) — KDKA City of license Pittsburgh, Pennsylvania Broadcast area Western Pennsylvania Branding Newsradio 1020 KDKA Slogan The Vo … Wikipedia
Bob Trow — Robert Trow (February 6, 1926 mdash;November 2, 1998) was an American radio celebrity, actor, and craftsman.Raised in the Beltzhoover neighborhood of Pittsburgh, Pennsylvania, USA, Trow began his career in radio. He later became well known for… … Wikipedia