CORDIC

CORDIC
Name	CORDIC
Class	Iterative algorithm
Data structure	Lookup table
Time	O(n)
Space	O(1)
Author	Jack E. Volder
Year	1959

CORDIC (Coordinate Rotation Digital Computer) is a simple and efficient iterative algorithm used to calculate hyperbolic and trigonometric functions. It requires only basic operations—bit shifts, addition, subtraction, and a small lookup table—making it highly suitable for implementation in hardware such as FPGAs, microcontrollers, and early digital computer systems. The algorithm operates by performing a series of micro-rotations, progressively rotating a vector to compute angles, sines, cosines, and other related values. Its elegance lies in avoiding complex multiplications, which were computationally expensive in the era of its invention.

Overview

The fundamental principle involves rotating a vector in a two-dimensional plane through a series of progressively smaller, predetermined angles. These rotations are executed using simple addition and bit shift operations, which correspond to multiplications by powers of two. A critical feature is the use of a precomputed lookup table containing arctangent values for these diminishing angles. The algorithm can be configured to operate in different rotation modes, such as the *rotation mode* for computing sine and cosine from an angle, or the *vectoring mode* for determining the magnitude and phase of a vector. This versatility allows it to serve as the computational core for a wide array of digital signal processing tasks.

Mathematical foundation

The algorithm is derived from the general rotation of a vector (x, y) by an angle θ, which can be expressed using rotation matrix operations from linear algebra. The key insight is that a rotation can be decomposed into a sequence of smaller rotations, where each step i rotates by an angle δᵢ = arctan(2⁻ⁱ). This specific choice transforms the required cosine factor into a constant scale factor K, which converges to approximately 0.60725 after many iterations. The mathematical recurrence relations are: xᵢ₊₁ = xᵢ - σᵢ yᵢ 2⁻ⁱ and yᵢ₊₁ = yᵢ + σᵢ xᵢ 2⁻ⁱ, where σᵢ ∈ {-1, +1} directs the direction of each micro-rotation. The algorithm can also be extended to the hyperbolic coordinate system by using angles defined by arctanh(2⁻ⁱ), enabling the calculation of functions like the hyperbolic sine.

Algorithm

A typical implementation begins by initializing the vector coordinates and an angle accumulator. For each iteration i, the algorithm determines the direction σᵢ to rotate based on the sign of the remaining angle (in rotation mode) or the sign of the y-coordinate (in vectoring mode). It then performs the shift-and-add operations on the x and y registers, updates the angle accumulator by subtracting or adding the corresponding arctangent value from the lookup table, and proceeds to the next iteration. The process continues for a fixed number of steps, with the final result being scaled by the precomputed constant K. For hyperbolic calculations, certain iterations (i=4, 13, 40, ...) must be repeated to ensure convergence, a requirement stemming from the mathematics of the Taylor series for arctanh.

Applications

Its primary historical application was in the avionics systems of aircraft like the B-58 Hustler, where it computed navigation functions for the IBM-built Air Data Computer. In modern digital signal processing, it is extensively used in direct digital synthesis for generating waveforms, in software-defined radio for phase and frequency correction, and within Fast Fourier transform algorithms. The algorithm is also fundamental in computer graphics for coordinate transformations and in various embedded system components, including arithmetic logic unit designs and digital filter implementations. Its ability to compute inverse trigonometric functions makes it valuable in control theory for calculating phase-locked loop error signals.

Implementations and variations

Early hardware implementations were realized in the discrete transistor logic of the IBM 1620 and other minicomputers. Modern versions are commonly synthesized onto FPGAs and ASICs, often using pipelined architecture to achieve high throughput for real-time computing applications. Variations include the *pipelined CORDIC*, which unrolls the iterations for speed, and the *angle recoding* method, which reduces the number of required iterations. Techniques like the *Taylor series* expansion are sometimes combined with it to accelerate convergence. For high-precision requirements in systems like the Global Positioning System, extended versions with higher bit width and more iterations are employed.

Historical development

The algorithm was conceived in 1959 by Jack E. Volder while working for the Convair division of General Dynamics, driven by the need for real-time navigation computations for the B-58 Hustler bomber's inertial navigation system. Its development was contemporaneous with, but independent of, similar techniques described in the 1956-1957 reports by Henry Briggs and later generalized by John Stephen Walther at Hewlett-Packard in 1971. Walther's key contribution was unifying the circular, linear, and hyperbolic versions into a single, generalized framework, which was subsequently published in a seminal 1971 paper. The algorithm's efficiency ensured its adoption across the computer industry, influencing designs at companies like Hewlett-Packard for their early calculators and within the military-industrial complex for various avionics systems.

Category:Numerical analysis Category:Digital signal processing Category:Computer arithmetic