How CORDIC Uses Bit Shifts for Trigonometry

The CORDIC (Coordinate Rotation Digital Computer) algorithm is a hardware-efficient method for calculating trigonometric, hyperbolic, and other mathematical functions using only basic additions, subtractions, and binary bit shifts. Instead of relying on computationally expensive hardware multipliers or massive lookup tables, CORDIC breaks down arbitrary angle rotations into a sequence of smaller, predefined micro-rotations. This article explains the underlying mathematics of CORDIC, how it converts complex matrix multiplication into simple bit shifts, and how it accurately derives sine and cosine values in binary systems.

The Fundamental Rotation Problem

Calculating trigonometric functions like \(\sin(\theta)\) and \(\cos(\theta)\) can be modeled as rotating a two-dimensional unit vector \((1, 0)\) around the origin by an angle \(\theta\). The resulting coordinates \((x', y')\) represent:

\[x' = \cos(\theta)\] \[y' = \sin(\theta)\]

Standard 2D rotation of a vector \((x, y)\) by an angle \(\alpha\) is governed by the rotation matrix:

\[x' = x \cos(\alpha) - y \sin(\alpha)\] \[y' = y \cos(\alpha) + x \sin(\alpha)\]

Factoring out \(\cos(\alpha)\) transforms these equations into:

\[x' = \cos(\alpha) [x - y \tan(\alpha)]\] \[y' = \cos(\alpha) [y + x \tan(\alpha)]\]

This formulation requires multiplying by both \(\cos(\alpha)\) and \(\tan(\alpha)\), which is resource-intensive on simple microcontrollers, FPGAs, and ASICs lacking dedicated floating-point units.

The CORDIC Simplification: Using Powers of Two

CORDIC simplifies rotation arithmetic through two core design choices:

  1. Decomposing the Target Angle: Any arbitrary target angle \(\theta\) is reached by performing a series of successive rotations by decreasing, fixed angles \(\alpha_i\), such that: \[\theta \approx \sum_{i=0}^{N-1} d_i \alpha_i \quad \text{where } d_i \in \{-1, +1\}\] Here, \(d_i\) determines the direction of the rotation (clockwise or counterclockwise).

  2. Constraining Tangents to Powers of Two: The angle steps \(\alpha_i\) are deliberately chosen so that their tangents equal negative powers of two: \[\tan(\alpha_i) = 2^{-i}\] This yields predefined angles:

    • \(\alpha_0 = \arctan(2^0) = 45.0^\circ\)
    • \(\alpha_1 = \arctan(2^{-1}) \approx 26.565^\circ\)
    • \(\alpha_2 = \arctan(2^{-2}) \approx 14.036^\circ\)
    • \(\alpha_3 = \arctan(2^{-3}) \approx 7.125^\circ\)

Replacing Multiplication with Binary Bit Shifts

Because \(\tan(\alpha_i) = 2^{-i}\), multiplying a binary number by \(\tan(\alpha_i)\) is mathematically equivalent to performing an arithmetic right shift by \(i\) bit positions:

\[x \cdot \tan(\alpha_i) = x \cdot 2^{-i} = x \gg i\]

By temporarily ignoring the \(\cos(\alpha_i)\) factor (pseudo-rotation), the iteration equations simplify entirely to additions, subtractions, and bit shifts:

\[x_{i+1} = x_i - d_i (y_i \gg i)\] \[y_{i+1} = y_i + d_i (x_i \gg i)\] \[z_{i+1} = z_i - d_i \alpha_i\]

Where: * \(x_i, y_i\) are the coordinates of the current vector. * \(z_i\) is the residual angle accumulator tracking the remaining angle to rotate. * \(d_i = +1\) if \(z_i \ge 0\) (rotate counterclockwise), and \(d_i = -1\) if \(z_i < 0\) (rotate clockwise). * \(\alpha_i = \arctan(2^{-i})\) is a small precalculated constant retrieved from a minimal lookup table.

Correcting the Scale Factor (\(K\))

Each pseudo-rotation operation stretches the vector by a factor of \(\sqrt{1 + \tan^2(\alpha_i)} = \sqrt{1 + 2^{-2i}}\). Over \(N\) iterations, the cumulative gain \(K\) approaches a constant value:

\[K = \prod_{i=0}^{N-1} \sqrt{1 + 2^{-2i}} \approx 1.646760258\]

Because the sequence of rotation angles is fixed, the total gain \(K\) is known in advance and does not depend on the target angle \(\theta\). To obtain unscaled, accurate values of \(\cos(\theta)\) and \(\sin(\theta)\), the initial coordinate \(x_0\) is simply initialized to the reciprocal of \(K\):

\[x_0 = \frac{1}{K} \approx 0.607252935\] \[y_0 = 0\] \[z_0 = \theta\]

Execution Walkthrough

To compute \(\sin(\theta)\) and \(\cos(\theta)\):

  1. Initialization: Set \(x_0 \approx 0.60725\), \(y_0 = 0\), and the accumulator \(z_0 = \theta\).
  2. Iteration Loop: For \(i = 0\) to \(N-1\):
    • Evaluate the sign of \(z_i\) to establish \(d_i \in \{-1, +1\}\).
    • Compute \(x_{i+1} = x_i - d_i (y_i \gg i)\).
    • Compute \(y_{i+1} = y_i + d_i (x_i \gg i)\).
    • Update the remaining angle: \(z_{i+1} = z_i - d_i \alpha_i\).
  3. Output: After \(N\) iterations, \(z_N \approx 0\), \(x_N \approx \cos(\theta)\), and \(y_N \approx \sin(\theta)\).

Each iteration yields roughly one additional bit of precision, allowing digital circuits to execute exact trigonometric calculations at high speeds with minimal gate counts.