CORDIC (COordinate Rotation DIgital Computer) – Volder’s Algorithm

by admin in , , on June 13, 2019

CORDIC (for COordinate Rotation DIgital Computer), also known as Volder’s algorithm, is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions, 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 is available (e.g. in simple microcontrollers and FPGAs), as the only operations it requires are addition, subtraction, bitshift and table lookup. As such, they belong to the class of shift-and-add algorithms.

Example On Using The Code:

Input
Beta = 30;              % Angle in Degree
beta = Beta*pi/180;     % Angle in Radian
n = 99;                 % Max. Number of Iterations
V = cordic(beta,n);     % Calling the Function
Output

Contents

  • History
  • Applications
    • Hardware
    • Software
  • Modes of operation
    • Rotation mode
    • Vectoring mode
    • Implementation
  • Related algorithms
  • References

History

Similar mathematical techniques were published by Henry Briggs as early as 1624[4][5] and Robert Flower in 1771,[6] but CORDIC is optimized for low-complexity finite-state CPUs. CORDIC was conceived in 1956[7][8] by Jack E. Volder at the aeroelectronics department of Convair out of necessity to replace the analog resolver in the B-58 bomber’s navigation computer with a more accurate and performant real-time digital solution.[8] Therefore, CORDIC is sometimes referred to as digital resolver.[9][10]

In his research Volder was inspired by a formula in the 1946 edition of the CRC Handbook of Chemistry and Physics:

His research led to an internal technical report proposing the CORDIC algorithm to solve sine and cosine  functions and a prototypical computer implementing it.[7][8] The report also discussed the possibility to compute hyperbolic coordinate rotation, logarithms and exponential functions with modified CORDIC algorithms.[7][8] Utilizing CORDIC for multiplication and division was also conceived at this time.[8] Based on the CORDIC principle, Dan H. Daggett, a colleague of Volder at Convair, developed conversion algorithms between binary and binary-coded decimal (BCD).[8][11]

In 1958, Convair finally started to build a demonstration system to solve radar fix-taking problems named CORDIC I, completed in 1960 without Volder, who had left the company already.[1][8] More universal CORDIC II models A (stationary) and B (airborne) were built and tested by Daggett and Harry Schuss in 1962.[8][12]

Volder’s CORDIC algorithm was first described in public in 1959,[1][2] which caused it to be incorporated into navigation computers by companies including Martin-Orlando, Computer Control, Litton, Kearfott, Lear-Siegler, Sperry, Raytheon, and Collins Radio soon.[8]

Volder teamed up with Malcolm MacMillan to build Athena, a fixed-point desktop calculator utilizing his binary CORDIC algorithm. The design was introduced to Hewlett-Packard in June 1965, but not accepted.[14] Still, MacMillan 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.

Decimal CORDIC became widely used in pocket calculators,[10] 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.

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 estimation, singular value decomposition, QR factorization and many others. As a consequence, CORDIC has been used for applications in diverse areas such as signal and image processing, communication systems, robotics and 3D graphics apart from general scientific and technical computation.[44][45]

Hardware

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).

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. In recent years, the CORDIC algorithm has been used extensively for various biomedical applications, especially in FPGA implementations.

Software

Many older systems with integer-only CPUs have implemented CORDIC to varying extents as part of their IEEE floating-point libraries. As most modern general-purpose CPUs have floating-point registers with common operations such as add, subtract, multiply, divide, sine, cosine, square root, log10, 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, 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 beta, the y or x coordinate of a point on the unit circle corresponding to the desired angle must be found. Using CORDIC, one would start with the vector v0:

An illustration of the CORDIC algorithm in progress. In the first iteration, this vector is rotated 45° counterclockwise to get the vector v1. Successive iterations 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(2^-i) for  i=0,1,2,….

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 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 gamma _(i) so that gamma _(i)takes on the values +- 2^(-i), 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 sigma _(i) can have the values of −1 or 1, and is used to determine the direction of the rotation; if the angle gamma _(i) is positive then sigma _(i)is +1, otherwise it is −1. K_(i) can be ignored in the iterative process and then applied afterward 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 v0 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 K altogether, resulting in a processing gain A:

After a sufficient number of iterations, the vector’s angle will be close to the wanted angle beta. 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 each iteration (choosing the value of sigma). 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 beta, if beta _(n+1) is positive, the rotation is clockwise, otherwise it is negative and the rotation is counterclockwise.

The values of gamma _(n) must also be precomputed and stored. But for small angles, arctan (gamma _(n)) = gamma _(n) in fixed-point representation, reducing table size.

As can be seen in the illustration above, the sine of the angle betais the y coordinate of the final vector v_(n), 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 beta_(i)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 beta _(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.

References

  1. Volder, Jack E. (1959-03-03). “The CORDIC Computing Technique”(PDF)Proceedings of the Western Joint Computer Conference (WJCC) (presentation). San Francisco, California, USA: National Joint Computer Committee (NJCC): 257–261. Retrieved 2016-01-02.
  2. Volder, Jack E. (1959-05-25). “The CORDIC Trigonometric Computing Technique”(PDF)IRE Transactions on Electronic Computers. The Institute of Radio Engineers, Inc. (IRE) (published September 1959). 8 (3): 330–334 (reprint: 226–230). EC-8(3):330–334. Retrieved 2016-01-01.
  3. Swartzlander, Jr., Earl E. (1990). Computer Arithmetic1 (2 ed.). Los Alamitos: IEEE Computer Society Press. ISBN 9780818689314. 0818689315. Retrieved 2016-01-02.
  4. Briggs, Henry (1624). Arithmetica Logarithmica. London. (Translation: [1])
  5. Laporte, Jacques (2014) [2005]. “Henry Briggs and the HP 35”. Paris, France. Archived from the original on 2015-03-09. Retrieved 2016-01-02.
  6. Flower, Robert (1771). The Radix. A new way of making logarithms. London: J. Beecroft. Retrieved 2016-01-02.
  7. Volder, Jack E. (1956-06-15), Binary Computation Algorithms for Coordinate Rotation and Function Generation (internal report), Convair, Aeroelectronics group, IAR-1.148
  8. Volder, Jack E. (June 2000). “The Birth of CORDIC”(PDF)Journal of VLSI Signal Processing. Hingham, MA, USA: Kluwer Academic Publishers. 25(2): 101–105. doi:10.1023/A:1008110704586. ISSN0922-5773. Archived from the original(PDF) on 2016-03-04. Retrieved 2016-01-02.
  9. Perle, Michael D. (June 1971), “CORDIC Technique Reduces Trigonometric Function Look-Up”, Computer Design, Boston, MA, USA: Computer Design Publishing Corp.: 72–78 (NB. Some sources erroneously refer to this as by P. Z. Perle or in Component Design.)
  10. Schmid, Hermann (1983) [1974]. Decimal Computation (1 (reprint) ed.). Malabar, Florida, USA: Robert E. Krieger Publishing Company. pp. 162, 165–176, 181–193. ISBN0-89874-318-4. Retrieved 2016-01-03. (NB. At least some batches of this reprint edition were misprints with defective pages 115–146.)
  11. Daggett, Dan H. (September 1959). “Decimal-Binary Conversions in CORDIC”IRE Transactions on Electronic Computers. The Institute of Radio Engineers, Inc. (IRE). 8 (3): 335–339. doi:10.1109/TEC.1959.5222694. ISSN0367-9950. EC-8(3):335-339. Retrieved 2016-01-02.
  12. Advanced Systems Group (1962-08-06), Technical Description of Fix-taking Tie-in Equipment (report), Fort Worth, Texas, USA: General Dynamics, FZE-052
  13. Schmid, Hermann (1974). Decimal Computation (1 ed.). Binghamton, New York, USA: John Wiley & Sons, Inc. pp. 162, 165–176, 181–193. ISBN0-471-76180-X. Retrieved 2016-01-03So far CORDIC has been known to be implemented only in binary form. But, as will be demonstrated here, the algorithm can be easily modified for a decimal system.* […] *In the meantime it has been learned that Hewlett Packard and other calculator manufacturers employ the decimal CORDIC techniques in their scientific calculators.

0 Sale

Share Now!

Release Information

  • Price
    :

    $2.39

  • Released
    :

    June 13, 2019

  • Last Updated
    :

    June 13, 2019

Share Your Valuable Opinions