CORDIC (for "coordinate rotation digital computer"), also known as Volder's algorithm, or: Digit-by-digit method Circular CORDIC (Jack E. Volder),
Linear CORDIC, Hyperbolic CORDIC (John Stephen Walther),
and Generalized Hyperbolic CORDIC (GH CORDIC) (Yuanyong Luo et al.),
is a simple and efficient
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
to calculate
trigonometric function
In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in all ...
s,
hyperbolic function
In mathematics, hyperbolic functions are analogues of the ordinary trigonometric functions, but defined using the hyperbola rather than the circle. Just as the points form a circle with a unit radius, the points form the right half of the u ...
s,
square roots
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
E ...
,
multiplications,
divisions, and
exponentials
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
and
logarithms
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...
with arbitrary base, typically converging with one digit (or bit) per iteration. CORDIC is therefore also an example of digit-by-digit algorithms. CORDIC and closely related methods known as pseudo-multiplication and pseudo-division or factor combining are commonly used when no
hardware multiplier
A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers.
A variety of computer arithmetic techniques can be used to implement a digital multiplier. Most techniques involve co ...
is available (e.g. in simple
microcontroller
A microcontroller (MCU for ''microcontroller unit'', often also MC, UC, or μC) is a small computer on a single VLSI integrated circuit (IC) chip. A microcontroller contains one or more CPUs (processor cores) along with memory and programmable i ...
s and
FPGA
A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware de ...
s), as the only operations it requires are
addition
Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
s,
subtraction
Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
s,
bitshift
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...
and
lookup table
In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from hash tables in a way that, to retrieve a value v wi ...
s. As such, they all belong to the class of
shift-and-add algorithms. In computer science, CORDIC is often used to implement
floating-point arithmetic
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
when the target platform lacks hardware multiply for cost or space reasons.
History
Similar mathematical techniques were published by
Henry Briggs Henry Briggs may refer to:
*Henry Briggs (mathematician) (1561–1630), English mathematician
*Henry Perronet Briggs (1793–1844), English painter
*Henry George Briggs (1824–1872), English merchant, traveller, and orientalist
*Henry Shaw Briggs ...
as early as 1624
and Robert Flower in 1771,
but CORDIC is better optimized for low-complexity finite-state CPUs.
CORDIC was conceived in 1956
by
Jack E. Volder at the
aeroelectronics department of
Convair
Convair, previously Consolidated Vultee, was an American aircraft manufacturing company that later expanded into rockets and spacecraft. The company was formed in 1943 by the merger of Consolidated Aircraft and Vultee Aircraft. In 1953, it ...
out of necessity to replace the
analog resolver
A resolver is a type of rotary electrical transformer used for measuring degrees of rotation. It is considered an analog device, and has digital counterparts such as the digital resolver, rotary (or pulse) encoder.
Description
The most common ...
in the
B-58 bomber's navigation computer with a more accurate and faster real-time digital solution.
Therefore, CORDIC is sometimes referred to as a
digital resolver
Digital usually refers to something using discrete digits, often binary digits.
Technology and computing Hardware
*Digital electronics, electronic circuits which operate using digital signals
**Digital camera, which captures and stores digital i ...
.
In his research Volder was inspired by a formula in the 1946 edition of the ''
CRC Handbook of Chemistry and Physics
The ''CRC Handbook of Chemistry and Physics'' is a comprehensive one-volume reference resource for science research. First published in 1914, it is currently () in its 103rd edition, published in 2022. It is sometimes nicknamed the "Rubber Bible ...
'':
:
with
,
.
His research led to an internal technical report proposing the CORDIC algorithm to solve
sine
In mathematics, sine and cosine are trigonometric functions of an angle. The sine and cosine of an acute angle are defined in the context of a right triangle: for the specified angle, its sine is the ratio of the length of the side that is oppo ...
and
cosine functions and a prototypical computer implementing it.
The report also discussed the possibility to compute hyperbolic
coordinate rotation
Rotation in mathematics is a concept originating in geometry. Any rotation is a motion of a certain space that preserves at least one point. It can describe, for example, the motion of a rigid body around a fixed point. Rotation can have sign ...
,
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...
s and
exponential function
The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, a ...
s with modified CORDIC algorithms.
Utilizing CORDIC for
multiplication
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
and
division
Division or divider may refer to:
Mathematics
*Division (mathematics), the inverse of multiplication
*Division algorithm, a method for computing the result of mathematical division
Military
*Division (military), a formation typically consisting ...
was also conceived at this time.
Based on the CORDIC principle, Dan H. Daggett, a colleague of Volder at Convair, developed conversion algorithms between binary and
binary-coded decimal
In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for ...
(BCD).
In 1958, Convair finally started to build a demonstration system to solve
radar fix
Radar navigation is the utilization of marine and aviation radar systems for vessel and aircraft navigation. When a craft is within radar range of land or special radar aids to navigation, the navigator can take distances and angular bearing ...
-taking problems named ''CORDIC I'', completed in 1960 without Volder, who had left the company already.
More universal ''CORDIC II'' models ''A'' (stationary) and ''B'' (airborne) were built and tested by Daggett and Harry Schuss in 1962.
Volder's CORDIC algorithm was first described in public in 1959,
which caused it to be incorporated into navigation computers by companies including
Martin-Orlando
The Glenn L. Martin Company—also known as The Martin Company from 1957-1961—was an American aircraft and aerospace industry, aerospace manufacturing company founded by aviation pioneer Glenn L. Martin, and operated between 1917-1961. The Ma ...
,
Computer Control,
Litton,
Kearfott
Kearfott is a defense equipment manufacturer founded in 1918 in New Jersey, United States. It is based in Woodland Park. Today the electronics division is part of BAE Systems, while the remaining Kearfott Guidance & Navigation division is a subsid ...
,
Lear-Siegler
Lear Siegler Incorporated (LSI) is a diverse American corporation established in 1962. Its products range from car seats and brakes to weapons control systems for military fighter planes. The company's more than $2 billion-a-year annual sales come ...
,
Sperry Sperry may refer to:
Places
In the United States:
*Sperry, Iowa, community in Des Moines County
*Sperry, Missouri
*Sperry, Oklahoma, town in Tulsa County
*Sperry Chalet, historic backcountry chalet, Glacier National Park, Montana
*Sperry Glacier, ...
,
Raytheon
Raytheon Technologies Corporation is an American multinational aerospace and defense conglomerate headquartered in Arlington, Virginia. It is one of the largest aerospace and defense manufacturers in the world by revenue and market capitaliza ...
, and
Collins Radio
Rockwell Collins was a multinational corporation headquartered in Cedar Rapids, Iowa, providing avionics and information technology systems and services to government agencies and aircraft manufacturers. It was formed when the Collins Radio Compa ...
.
Volder teamed up with Malcolm McMillan to build ''Athena'', a
fixed-point desktop calculator
An electronic calculator is typically a portable electronic device used to perform calculations, ranging from basic arithmetic to complex mathematics.
The first solid-state electronic calculator was created in the early 1960s. Pocket-siz ...
utilizing his binary CORDIC algorithm.
The design was introduced to
Hewlett-Packard
The Hewlett-Packard Company, commonly shortened to Hewlett-Packard ( ) or HP, was an American multinational information technology company headquartered in Palo Alto, California. HP developed and provided a wide variety of hardware components ...
in June 1965, but not accepted.
Still, McMillan introduced
David S. Cochran (HP) to Volder's algorithm and when Cochran later met Volder he referred him to a similar approach
John E. Meggitt (IBM
) had proposed as ''pseudo-multiplication'' and ''pseudo-division'' in 1961.
Meggitt's method also suggested the use of base 10
rather than
base 2, as used by Volder's CORDIC so far. These efforts led to the
ROMable
A ROM image, or ROM file, is a computer file which contains a copy of the data from a read-only memory chip, often from a video game cartridge, or used to contain a computer's firmware, or from an arcade game's main board. The term is freque ...
logic implementation of a decimal CORDIC prototype machine inside of Hewlett-Packard in 1966,
built by and conceptually derived from
Thomas E. Osborne's prototypical ''Green Machine'', a four-function,
floating-point
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can b ...
desktop calculator he had completed in
DTL logic
in December 1964.
This project resulted in the public demonstration of Hewlett-Packard's first desktop calculator with scientific functions, the
hp 9100A in March 1968, with series production starting later that year.
When
Wang Laboratories
Wang Laboratories was a US computer company founded in 1951 by An Wang and G. Y. Chu. The company was successively headquartered in Cambridge, Massachusetts (1954–1963), Tewksbury, Massachusetts (1963–1976), and finally in Lowell, Massachusett ...
found that the hp 9100A used
an approach similar to the ''factor combining'' method in their earlier
LOCI-1 (September 1964) and
LOCI-2 (January 1965)
''Logarithmic Computing Instrument'' desktop calculators,
they unsuccessfully accused Hewlett-Packard of infringement of one of
An Wang
An Wang (; February 7, 1920 – March 24, 1990) was a Chinese–American computer engineer and inventor, and cofounder of computer company Wang Laboratories, which was known primarily for its dedicated word processing machines. Wang was an impo ...
's patents in 1968.
John Stephen Walther at Hewlett-Packard generalized the algorithm into the ''Unified CORDIC'' algorithm in 1971, allowing it to calculate
hyperbolic functions
In mathematics, hyperbolic functions are analogues of the ordinary trigonometric functions, but defined using the hyperbola rather than the circle. Just as the points form a circle with a unit radius, the points form the right half of the u ...
,
natural exponentials,
natural logarithm
The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
s,
multiplication
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
s,
division
Division or divider may refer to:
Mathematics
*Division (mathematics), the inverse of multiplication
*Division algorithm, a method for computing the result of mathematical division
Military
*Division (military), a formation typically consisting ...
s, and
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
E ...
s.
The CORDIC
subroutines
In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed.
Functions may ...
for trigonometric and hyperbolic functions could share most of their code.
This development resulted in the first
scientific
Science is a systematic endeavor that builds and organizes knowledge in the form of testable explanations and predictions about the universe.
Science may be as old as the human species, and some of the earliest archeological evidence for ...
handheld calculator, the
HP-35
The HP-35 was Hewlett-Packard's first pocket calculator and the world's first ''scientific'' pocket calculator: a calculator with trigonometric and exponential functions. It was introduced in 1972.
History
In about 1970 HP co-founder Bill Hewl ...
in 1972.
Based on hyperbolic CORDIC,
Yuanyong Luo et al. further proposed a Generalized Hyperbolic CORDIC (GH CORDIC) to directly compute logarithms and exponentials with an arbitrary fixed base in 2019.
Theoretically, Hyperbolic CORDIC is a special case of GH CORDIC.
Originally, CORDIC was implemented only using the
binary numeral system
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one).
The base-2 numeral system is a positional notatio ...
and despite Meggitt suggesting the use of the decimal system for his pseudo-multiplication approach, decimal CORDIC continued to remain mostly unheard of for several more years, so that
Hermann Schmid and Anthony Bogacki still suggested it as a novelty as late as 1973
and it was found only later that Hewlett-Packard had implemented it in 1966 already.
Decimal CORDIC became widely used in
pocket calculator
An electronic calculator is typically a portable electronic device used to perform calculations, ranging from basic arithmetic to complex mathematics.
The first solid-state electronic calculator was created in the early 1960s. Pocket-sized d ...
s,
most of which operate in binary-coded decimal (BCD) rather than binary. This change in the input and output format did not alter CORDIC's core calculation algorithms. CORDIC is particularly well-suited for handheld calculators, in which low cost – and thus low chip gate count – is much more important than speed.
CORDIC has been implemented in the
ARM-based STM32G4,
Intel 8087
The Intel 8087, announced in 1980, was the first x87 floating-point coprocessor for the 8086 line of microprocessors.
The purpose of the 8087 was to speed up computations for floating-point arithmetic, such as addition, subtraction, multiplicati ...
,
80287
x87 is a floating-point-related subset of the x86 architecture instruction set. It originated as an extension of the 8086 instruction set in the form of optional floating-point coprocessors that worked in tandem with corresponding x86 CPUs. Th ...
,
80387 up to the
80486
The Intel 486, officially named i486 and also known as 80486, is a microprocessor. It is a higher-performance follow-up to the Intel 386. The i486 was introduced in 1989. It represents the fourth generation of binary compatible CPUs following the ...
coprocessor series as well as in the
Motorola 68881
The Motorola 68881 and Motorola 68882 are floating-point units (FPUs) used in some computer systems in conjunction with Motorola's 32-bit 68020 or 68030 microprocessors. These coprocessors are external chips, designed before floating point math bec ...
and
68882
The Motorola 68881 and Motorola 68882 are floating-point units (FPUs) used in some computer systems in conjunction with Motorola's 32-bit 68020 or 68030 microprocessors. These coprocessors are external chips, designed before floating point math bec ...
for some kinds of floating-point instructions, mainly as a way to reduce the gate counts (and complexity) of the
FPU sub-system.
Applications
CORDIC uses simple shift-add operations for several computing tasks such as the calculation of trigonometric, hyperbolic and logarithmic functions, real and complex multiplications, division, square-root calculation, solution of linear systems,
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
estimation,
singular value decomposition
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is related ...
,
QR factorization
In linear algebra, a QR decomposition, also known as a QR factorization or QU factorization, is a decomposition of a matrix ''A'' into a product ''A'' = ''QR'' of an orthogonal matrix ''Q'' and an upper triangular matrix ''R''. QR decomp ...
and many others. As a consequence, CORDIC has been used for applications in diverse areas such as
signal
In signal processing, a signal is a function that conveys information about a phenomenon. Any quantity that can vary over space or time can be used as a signal to share messages between observers. The ''IEEE Transactions on Signal Processing'' ...
and
image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
,
communication systems
A communications system or communication system is a collection of individual telecommunications networks, transmission systems, relay stations, tributary stations, and terminal equipment usually capable of interconnection and interoperatio ...
,
robotics
Robotics is an interdisciplinary branch of computer science and engineering. Robotics involves design, construction, operation, and use of robots. The goal of robotics is to design machines that can help and assist humans. Robotics integrat ...
and
3D graphics
3D computer graphics, or “3D graphics,” sometimes called CGI, 3D-CGI or three-dimensional computer graphics are graphics that use a three-dimensional representation of geometric data (often Cartesian) that is stored in the computer for the ...
apart from general scientific and technical computation.
Hardware
The algorithm was used in the navigational system of the
Apollo program's
Lunar Roving Vehicle
The Lunar Roving Vehicle (LRV) is a battery-powered four-wheeled rover used on the Moon in the last three missions of the American Apollo program ( 15, 16, and 17) during 1971 and 1972. It is popularly called the Moon buggy, a play on the t ...
to compute
bearing and range, or distance from the
Lunar module
The Apollo Lunar Module (LM ), originally designated the Lunar Excursion Module (LEM), was the lunar lander spacecraft that was flown between lunar orbit and the Moon's surface during the United States' Apollo program. It was the first crewed ...
.
CORDIC was used to implement the
Intel 8087
The Intel 8087, announced in 1980, was the first x87 floating-point coprocessor for the 8086 line of microprocessors.
The purpose of the 8087 was to speed up computations for floating-point arithmetic, such as addition, subtraction, multiplicati ...
math coprocessor in 1980, avoiding the need to implement hardware multiplication.
CORDIC is generally faster than other approaches when a hardware multiplier is not available (e.g., a microcontroller), or when the number of gates required to implement the functions it supports should be minimized (e.g., in an FPGA or
ASIC
An application-specific integrated circuit (ASIC ) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use, such as a chip designed to run in a digital voice recorder or a high-efficien ...
).
In fact, CORDIC is a standard drop-in
IP in FPGA development applications such as Vivado for Xilinx, while a power series implementation is not due to the specificity of such an IP, i.e. CORDIC can compute many different functions (general purpose) while a hardware multiplier configured to execute power series implementations can only compute the function it was designed for.
On the other hand, when a hardware multiplier is available (''e.g.'', in a
DSP
DSP may refer to:
Computing
* Digital signal processing, the mathematical manipulation of an information signal
* Digital signal processor, a microprocessor designed for digital signal processing
* Yamaha DSP-1, a proprietary digital signal ...
microprocessor), table-lookup methods and
power series
In mathematics, a power series (in one variable) is an infinite series of the form
\sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots
where ''an'' represents the coefficient of the ''n''th term and ''c'' is a const ...
are generally faster than CORDIC. In recent years, the CORDIC algorithm has been used extensively for various biomedical applications, especially in FPGA implementations.
The
STM32G4 series and certain
STM32H7 series of MCUs implement a CORDIC module to accelerate computations in various mixed signal applications such as graphics for
human-machine interface
In the industrial design field of human–computer interaction, a user interface (UI) is the space where interactions between humans and machines occur. The goal of this interaction is to allow effective operation and control of the machine fr ...
and
field oriented control Vector control, also called field-oriented control (FOC), is a variable-frequency drive (VFD) control method in which the stator currents of a three-phase AC or brushless DC electric motor are identified as two orthogonal components that can be v ...
of motors. While not as fast as a power series approximation, CORDIC is indeed faster than interpolating table based implementations such as the ones provided by the ARM CMSIS and C standard libraries.
Though the results may be slightly less accurate as the CORDIC modules provided only achieve 20 bits of precision in the result. For example, most of the performance difference compared to the ARM implementation is due to the overhead of the interpolation algorithm, which achieves full floating point precision (24 bits) and can likely achieve relative error to that precision.
Another benefit is that the CORDIC module is a coprocessor and can be run in parallel with other CPU tasks.
The issue with using Taylor series is that while they do provide small absolute error, they do not exhibit well behaved relative error.
Other means of polynomial approximation, such as
minimax
Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...
optimization, may be used to control both kinds of error.
Software
Many older systems with integer-only CPUs have implemented CORDIC to varying extents as part of their
IEEE floating-point
The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in ...
libraries. As most modern general-purpose CPUs have floating-point registers with common operations such as add, subtract, multiply, divide, sine, cosine, square root, log
10, natural log, the need to implement CORDIC in them with software is nearly non-existent. Only microcontroller or special safety and time-constrained software applications would need to consider using CORDIC.
Modes 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 the sine and cosine of an angle, assuming that the desired angle is given in
radian
The radian, denoted by the symbol rad, is the unit of angle in the International System of Units (SI) and is the standard unit of angular measure used in many areas of mathematics. The unit was formerly an SI supplementary unit (before that c ...
s 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
In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucl ...
corresponding to the desired angle must be found. Using CORDIC, one would start with the vector
:
:
In the first iteration, this vector is rotated 45° counterclockwise to get the vector
. Successive iterations rotate the vector in one or the other direction by size-decreasing steps, until the desired angle has been achieved. Each step angle is
for
.
More formally, every iteration calculates a rotation, which is performed by multiplying the vector
with the
rotation matrix In linear algebra, a rotation matrix is a transformation matrix that is used to perform a rotation in Euclidean space. For example, using the convention below, the matrix
:R = \begin
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end ...
:
:
The rotation matrix is given by
:
Using the following two
trigonometric identities
In trigonometry, trigonometric identities are equalities that involve trigonometric functions and are true for every value of the occurring variables for which both sides of the equality are defined. Geometrically, these are identities involvin ...
:
:
the rotation matrix becomes
:
The expression for the rotated vector
then becomes
:
where
and
are the components of
. Restricting the angles
such that
, 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
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...
. The expression then becomes
:
where
:
and
is used to determine the direction of the rotation: if the angle
is positive, then
is +1, otherwise it is −1.
All
factors can be ignored in the iterative process and then applied all at once afterwards with 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
and hence saving a multiplication. Additionally, it can be noted that
:
to allow further reduction of the algorithm's complexity. Some applications may avoid correcting for
altogether, resulting in a processing gain
:
:
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 whether the rotation should be clockwise or counterclockwise at each iteration (choosing the value of
). This is done by keeping track of how much the angle was rotated at each iteration and subtracting that from the wanted angle; then in order to get closer to the wanted angle
, if
is positive, the rotation is clockwise, otherwise it is negative and the rotation is counterclockwise:
:
:
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.
Vectoring mode
The rotation-mode 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
being positive or negative.
The vectoring-mode 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
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.
Implementation
Software example
The following is a
MATLAB
MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementation ...
/
GNU Octave
GNU Octave is a high-level programming language primarily intended for scientific computing and numerical computation. Octave helps in solving linear and nonlinear problems numerically, and for performing other numerical experiments using a langu ...
implementation of CORDIC that does not rely on any
transcendental function
In mathematics, a transcendental function is an analytic function that does not satisfy a polynomial equation, in contrast to an algebraic function.
In other words, a transcendental function "transcends" algebra in that it cannot be expressed alge ...
s 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. With MATLAB's standard double-precision 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 = os(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^-2j]:
% Kvalues = cumprod(1./abs(1 + 1j*2.^(-(0:23))))
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 = ;0 % start with 2-vector cosine and sine of zero
poweroftwo = 1;
angle = angles(1);
% Iterations
for j = 0:n-1;
if beta < 0
sigma = -1;
else
sigma = 1;
end
factor = sigma * poweroftwo;
% Note the matrix multiplication can be done using scaling by powers of two and addition subtraction
R = , -factor; factor, 1
v = R * v; % 2-by-2 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 os(beta), sin(beta)
v = v * Kn;
return
endfunction
The two-by-two
matrix multiplication
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
can be carried out by a pair of simple shifts and adds.
x = v - sigma * (v * 2^(-j));
y = sigma * (v * 2^(-j)) + v
v = ; y
The semicolon or semi-colon is a symbol commonly used as orthography, orthographic punctuation. In the English language, a semicolon is most commonly used to link (in a single sentence) two independent clauses that are closely related in thou ...
In Java the Math class has a
scalb(double x,int scale)
method to perform such a shift,
C has the
ldexp
C mathematical operations are a group of functions in the standard library of the C programming language implementing basic mathematical functions. All functions use floating-point numbers in one manner or another. Different C standards provid ...
function,
and the x86 class of processors have the
fscale
floating point operation.
Hardware example
The number of
logic gate
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
s 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 multiplier-based or CORDIC-based implementation will depend on the context. The multiplication of two
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s 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 converter
In digital signal processing, a digital down-converter (DDC) converts a digitized, band-limited signal to a lower frequency signal at a lower sampling rate in order to simplify the subsequent radio stages. The process can preserve all the informat ...
s.
Double iterations CORDIC
In the publications: http://baykov.de/CORDIC1972.htm and http://baykov.de/CORDIC1975.htm it was proposed to use the double iterations method for the implementation of the functions: arcsinX, arccosX, lnX, expX, as well as for calculation of the hyperbolic functions. Double iterations method consists in the fact that unlike the classical CORDIC method, where the iteration step value changes EVERY time, i.e. on each iteration, in the double iteration method, the iteration step value is repeated twice and changes only through one iteration. Hence the designation for the degree indicator for double iterations appeared: ''i'' = 1,1,2,2,3,3... Whereas with ordinary iterations: ''i'' = 1,2,3... The double iteration method guarantees the convergence of the method throughout the valid range of argument changes.
The generalization of the CORDIC convergence problems for the arbitrary positional number system http://baykov.de/CORDIC1985.htm with Radix R showed that for the functions sin, cos, arctg, it is enough to perform (R-1) iterations for each value of i (i = 0 or 1 to n, where n is the number of digits), i.e. for each digit of the result. For the functions ln, exp, sh, ch, arth, R iterations should be performed for each value i. For the functions arcsin and arccos 2 (R-1) iterations should be performed for each number digit, i.e. for each value of i.
For arsh, arch functions, the number of iterations will be 2R for each i, that is, for each result digit.
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
The BKM algorithm is a shift-and-add algorithm for computing elementary functions, first published in 1994 by Jean-Claude Bajard, Sylvanus Kla, and Jean-Michel Muller. BKM is based on computing complex logarithms (''L-mode'') and exponentials ( ...
, 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
(in radians) by computing the exponential of
, which is
. The BKM algorithm is slightly more complex than CORDIC, but has the advantage that it does not need a scaling factor (''K'').
See also
*
Methods of computing square roots
Methods of computing square roots are numerical analysis algorithms for approximating the principal, or non-negative, square root (usually denoted \sqrt, \sqrt /math>, or S^) of a real number. Arithmetically, it means given S, a procedure for fi ...
*
IEEE 754
The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found i ...
*
Floating-point unit
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can b ...
s
*
Digital Circuits/CORDIC in Wikibooks
References
Further reading
* (NB. ''DIVIC'' stands for ''DIgital Variable Increments Computer''. Some sources erroneously refer to this as by ''J. M. Parini''.)
*
*
*
*
*
*
*
*
*
*
*
*
*
*
* (about CORDIC in
TI-58
The TI-59 is an early programmable calculator, that was manufactured by Texas Instruments from 1977. It is the successor to the TI SR-52, quadrupling the number of "program steps" of storage, and adding "ROM Program Modules" (an insertable ROM ...
/
TI-59
The TI-59 is an early programmable calculator, that was manufactured by Texas Instruments from 1977. It is the successor to the TI SR-52, quadrupling the number of "program steps" of storage, and adding "ROM Program Modules" (an insertable ROM ...
)
*
*
*
*
*
* (x+268 pages)
*
*
*
*
*
External links
*
Soft CORDIC IP (verilog HDL code)''CORDIC Bibliography Site''CORDIC implementation in verilogCORDIC Vectoring with Arbitrary Target ValuePicBasic Pro, Pic18 CORDIC math implementationPython CORDIC implementationSimple C code for fixed-point CORDIC*
ttp://bibix.nl/index.php?menu1=arx_ip Descriptions of hardware CORDICs in Arx with testbenches in C++ and VHDLAn Introduction to the CORDIC algorithmImplementation of the CORDIC Algorithm in a Digital Down-Converter50-th Anniversary of the CORDIC Algorithm*Implementation of the CORDIC Algorithm
fixed point C code for trigonometric and hyperbolic functionsC code for test and performance verification
{{DEFAULTSORT:Cordic
Digit-by-digit algorithms
Shift-and-add algorithms
Root-finding algorithms
Computer arithmetic
Numerical analysis
Trigonometry