CORDIC, short for coordinate rotation digital computer, is a simple and efficient algorithm to calculate trigonometric functions, hyperbolic functions, square roots, multiplications, divisions, exponentials, and logarithms with arbitrary base, typically converging with one digit (or bit) per iteration. CORDIC is therefore an example of a digit-by-digit algorithm. The original system is sometimes referred to as Volder's algorithm. 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 field-programmable gate arrays or FPGAs), as the only operations they require are addition, subtraction, bitshift and lookup tables. 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 when the target platform lacks the hardware to multiply for cost or space reasons. This was the case for most early microcomputers based on processors like the MOS 6502 and Zilog Z80. Over the years, a number of variations on the concept emerged, including circular CORDIC (Jack E. Volder), linear CORDIC, hyperbolic CORDIC (John Stephen Walther), and generalized hyperbolic CORDIC (GH CORDIC) (Yuanyong Luo et al.),
Concept At a high level, the basic CORDIC algorithm involves applying a sequence of scaled rotations to a vector. The scale factors and angles of rotation are known in advance; only the direction of each rotation is dependent on the input. In rotation mode, a target rotation angle is taken as input, and the rotation directions are chosen so that the accumulated rotation angle approaches the target. The output is the final vector. In vectoring mode, a vector is taken as input, and the rotation directions are chosen so that the y coordinate of the vector approaches 0. The output is the total rotation angle. See Modes of operation for the full details. The scale factors and angles of rotation are chosen so that the scaled rotations can be computed using only addition, subtraction, and bit shifting. The angles are looked up in a table that has been computed in advance.
History Similar mathematical techniques were published by Henry 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 out of necessity to replace the analog resolver 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. In his research, Volder was inspired by a formula in the 1946 edition of the CRC Handbook of Chemistry and Physics:
K n R sin ( θ ± φ ) = R sin ( θ ) ± 2 − n R cos ( θ ) , K n R cos ( θ ± φ ) = R cos ( θ ) ∓ 2 − n R sin ( θ ) , {\displaystyle {\begin{aligned}K_{n}R\sin(\theta \pm \varphi )&=R\sin(\theta )\pm 2^{-n}R\cos(\theta ),\\K_{n}R\cos(\theta \pm \varphi )&=R\cos(\theta )\mp 2^{-n}R\sin(\theta ),\\\end{aligned}}}
… excerpt ends here. Continue reading the full article.
