Electronics Guide

Rotation Mode

In rotation mode, CORDIC rotates a vector through a specified angle by decomposing the rotation into a sequence of micro-rotations. Each micro-rotation uses a predetermined angle whose tangent is a power of two, allowing the rotation to be performed using only shifts and additions. The algorithm converges to the desired angle through a binary search process, adding or subtracting each micro-rotation angle based on the remaining angular distance.

The rotation mode directly computes sine and cosine functions when initialized with an angle and unit vector. Starting with coordinates (1, 0) and rotating through angle theta produces (cos(theta), sin(theta)) after the iteration sequence completes. This dual computation of both trigonometric functions simultaneously represents a significant efficiency advantage over other methods.

Vectoring Mode

Vectoring mode performs the inverse operation, rotating a vector to align with an axis and tracking the accumulated rotation angle. This mode computes arctangent, magnitude, and phase simultaneously. Given input coordinates (x, y), the algorithm rotates until y becomes zero, producing the magnitude sqrt(x^2 + y^2) and angle arctan(y/x).

The vectoring mode proves particularly valuable in signal processing applications where conversion between rectangular and polar coordinates is frequently required. Phase detection, frequency estimation, and vector normalization all benefit from CORDIC vectoring.

Hyperbolic CORDIC

A modified CORDIC formulation handles hyperbolic functions by changing the rotation direction and angle sequence. Hyperbolic CORDIC computes sinh, cosh, tanh, and their inverses, as well as exponentials and logarithms. The algorithm requires certain iterations to be repeated due to the convergence properties of hyperbolic rotations, but maintains the fundamental shift-add structure.

The natural logarithm and exponential function emerge from hyperbolic CORDIC through appropriate initialization and mode selection. These computations are essential for floating-point division, square root extraction via logarithms, and scientific computing applications.

Linear CORDIC

Linear CORDIC mode provides multiplication and division using only shifts and additions. While less commonly used given the availability of dedicated multipliers in modern systems, linear CORDIC remains relevant for resource-constrained implementations and educational understanding of the algorithm's generality.

CORDIC Scaling Factor

CORDIC iterations introduce a scaling factor K that accumulates with each rotation. This constant approximately equals 0.6073 for the circular functions and must be compensated either by pre-scaling the input, post-scaling the output, or absorbing the factor into subsequent operations. Various techniques exist to minimize the overhead of this scaling, including merged scaling iterations and table-based correction.

Unified CORDIC

Unified CORDIC architectures handle circular, hyperbolic, and linear modes within a single hardware structure by parameterizing the mode selection. This approach maximizes hardware reuse in systems requiring multiple function types, trading some performance for reduced silicon area.

Taylor Series

Taylor series expansions provide a natural starting point for polynomial approximation, expressing functions as infinite sums of terms involving successively higher derivatives evaluated at a single point. While theoretically exact as the number of terms approaches infinity, truncated Taylor series often provide poor approximations for practical use, particularly near the boundaries of the approximation interval.

For example, the Taylor series for sine around zero is x - x^3/3! + x^5/5! - x^7/7! + ..., which converges well for small arguments but requires many terms for larger values. The uneven error distribution across the interval makes Taylor series suboptimal for most hardware implementations.

Chebyshev Approximations

Chebyshev polynomial approximations distribute error more evenly across the approximation interval by minimizing the maximum absolute error (minimax approximation). The resulting polynomials achieve equivalent accuracy with fewer terms than Taylor series, reducing computational cost and latency.

Chebyshev polynomials of the first kind form an orthogonal basis on the interval [-1, 1] with respect to a specific weight function. Function approximation proceeds by computing Chebyshev coefficients through numerical integration or the discrete cosine transform, then converting to standard power-series form for evaluation.

Minimax Polynomials

The Remez algorithm computes true minimax polynomial approximations that minimize the maximum error over the approximation interval. These polynomials exhibit the equiripple property, where the error oscillates between equal positive and negative extremes at n+2 points for a degree-n polynomial.

Minimax approximations require iterative numerical computation during design but yield optimal polynomials for hardware implementation. The resulting coefficients are typically stored in ROM or computed offline, with only the polynomial evaluation performed at runtime.

Horner's Method

Horner's method evaluates polynomials efficiently by factoring the expression to minimize the number of multiplications. A polynomial a_n*x^n + a_{n-1}*x^{n-1} + ... + a_1*x + a_0 becomes (...((a_n*x + a_{n-1})*x + a_{n-2})*x + ...)*x + a_0, requiring only n multiplications and n additions for a degree-n polynomial.

Hardware implementations of Horner's method pipeline the multiply-add operations for high throughput, often using fused multiply-add units that compute a*b + c in a single operation with only one rounding error.

Rational Approximations

Rational function approximations express the target function as a ratio of polynomials, often achieving better accuracy than pure polynomials for the same total number of coefficients. The Pade approximation provides rational functions that match Taylor series coefficients, while minimax rational approximations minimize error over an interval.

The computational cost of rational approximations includes a division operation, which may be acceptable when division hardware is available or when the improved accuracy justifies the overhead. Functions with poles or asymptotic behavior often benefit significantly from rational approximation.

Direct Table Lookup

The simplest table-based approach stores function values at uniformly spaced arguments and retrieves the nearest stored value. While fast and simple, direct lookup without interpolation provides limited accuracy unless extremely large tables are used. This method suits applications where moderate accuracy suffices and low latency is paramount.

Linear Interpolation

Linear interpolation between adjacent table entries significantly improves accuracy without substantially increasing complexity. The computation requires reading two table entries, computing their difference, multiplying by the fractional position, and adding to the base value. Modern implementations often use dedicated interpolation hardware that performs these operations in parallel with the table lookup.

Bipartite Tables

Bipartite table methods split the input into two parts, using separate smaller tables that combine to produce the result. The initial value table provides a coarse approximation, while the offset table provides a correction. This decomposition dramatically reduces total table size while maintaining accuracy.

For reciprocal and square root functions, bipartite methods achieve single-precision accuracy with tables of only a few thousand entries, compared to millions of entries for direct lookup at equivalent precision.

Multipartite Tables

Extending the bipartite concept, multipartite methods use three or more tables with hierarchically refined corrections. Each additional table provides higher-order correction terms, enabling very high accuracy with modest total memory. The design involves careful optimization of table sizes and bit allocations to minimize total cost.

Symmetric Table Methods

Functions with symmetry properties allow table size reduction by exploiting those symmetries. Sine and cosine require only one quadrant of storage, with simple transformations covering the remaining quadrants. Exponential and logarithm can share tables through their inverse relationship.

Additive Range Reduction

Additive reduction subtracts multiples of a known constant to bring the argument within range. For trigonometric functions, multiples of pi/2 or pi are subtracted, with the quadrant tracked for result reconstruction. The challenge lies in performing this reduction accurately when the input is much larger than the reduction constant.

Cody-Waite reduction uses extended precision representation of the reduction constant to minimize error accumulation. The constant is split into high and low parts, with the high part chosen for exact subtraction. This technique handles moderately large arguments accurately.

Multiplicative Range Reduction

Multiplicative reduction scales the argument by a power of two or other convenient factor. Exponential functions use this approach, expressing exp(x) as exp(r) * 2^n where r is the reduced argument and n is an integer. The scaling by powers of two is exact in binary floating-point, avoiding error introduction.

Logarithm functions invert this process, separating the input into mantissa and exponent components that are processed independently and combined for the final result.

Payne-Hanek Reduction

For extremely large arguments, Payne-Hanek reduction computes the remainder modulo pi/2 using arbitrary-precision arithmetic focused on the relevant bits. Rather than computing the full quotient, the algorithm identifies and extracts only the fractional part needed for accurate reduction.

This method handles arguments up to the maximum floating-point value while maintaining full precision in the reduced result. The trade-off is increased complexity and latency compared to simpler reduction methods.

Trigonometric Identities

Trigonometric argument reduction uses identities such as sin(x + pi/2) = cos(x) and sin(-x) = -sin(x) to map all arguments to a primary interval, typically [0, pi/4]. Within this interval, both sine and cosine are well-behaved, monotonic, and efficiently approximated.

The octant of the original argument determines which identity applies for result reconstruction. Careful handling of boundary cases and sign changes ensures correct results across all inputs.

Exponential and Logarithmic Identities

Exponential argument reduction uses exp(a + b) = exp(a) * exp(b) to separate large and small components. The integer part of x/ln(2) determines the power-of-two scaling, while the fractional part is evaluated using polynomial approximation.

Logarithm reduction uses log(a * b) = log(a) + log(b), separating the mantissa and exponent of floating-point inputs. The mantissa logarithm is computed over [1, 2), then combined with the exponent contribution.

Hyperbolic Identities

Hyperbolic functions relate to exponentials through sinh(x) = (exp(x) - exp(-x))/2 and cosh(x) = (exp(x) + exp(-x))/2. For small arguments, direct polynomial approximation avoids the cancellation errors inherent in the exponential formulation. For large arguments, the exponential relationship becomes advantageous.

Newton-Raphson Iteration

Newton-Raphson iteration for reciprocal computation uses the recurrence x_{n+1} = x_n * (2 - d * x_n), where d is the divisor and x_n approximates 1/d. Each iteration approximately doubles the number of correct bits, achieving quadratic convergence. Three iterations typically suffice for double precision starting from an 8-bit initial approximation.

The iteration requires two multiplications and one subtraction per step, well-suited to fused multiply-add hardware. Division completes by multiplying the dividend by the computed reciprocal.

Goldschmidt Division

Goldschmidt division simultaneously converges both dividend and divisor, maintaining their ratio while driving the divisor toward unity. The iteration multiplies both values by a factor that moves the divisor closer to one, yielding the quotient directly when convergence completes.

This method offers advantages for pipelined implementation because successive iterations are independent, allowing multiple divisions to overlap in the pipeline. The multiplication operations can also be performed in parallel within each iteration.

Series Expansion Methods

Taylor series expansion around unity provides division through 1/d = 1/(1-(1-d)) = 1 + (1-d) + (1-d)^2 + ... when |1-d| < 1. After range reduction to bring the divisor near one, partial sums of this series converge to the reciprocal. The series terms involve only powers of (1-d), computed by successive squaring.

Table-Based Initial Approximation

Lookup tables indexed by the most significant bits of the divisor provide fast initial approximations. A table with 256 entries (8 address bits) yields approximately 8 bits of accuracy, sufficient for three Newton-Raphson iterations to reach double precision. The table size trades against iteration count in the overall design optimization.

Linear Approximation

Piecewise linear approximation uses table entries plus linear interpolation for improved accuracy without dramatically increased table size. This approach achieves 12-14 bits of accuracy from modest tables, reducing the required iteration count.

Quadratic Approximation

Higher-order interpolation provides still better initial approximations at the cost of additional arithmetic. Quadratic approximation stores three coefficients per segment, computing ax^2 + bx + c using two multiply-adds. The resulting 20+ bits of accuracy may eliminate one iteration from the refinement sequence.

Hardware Reciprocal Instructions

Many processors provide fast approximate reciprocal instructions that return reduced-precision results in a single cycle. These instructions combine optimized table lookup with hardware interpolation, offering a balance between full-precision division and raw table lookup. Software refinement iterations extend the precision as needed.

Graphics Processing Units

GPUs include special function units (SFUs) that compute reciprocal, reciprocal square root, sine, cosine, exponential, and logarithm operations. These units serve the intense transcendental function demands of 3D graphics, where coordinate transformations, lighting calculations, and texture mapping require billions of such operations per second.

GPU special function units typically provide reduced precision (often 22-24 bits of mantissa rather than the full 24 bits of single precision) in exchange for increased throughput. For graphics applications, this precision trade-off is invisible in the rendered output while significantly improving performance.

Digital Signal Processors

DSP architectures often include specialized support for trigonometric functions used in communication signal processing. Phase rotators, coordinate converters, and NCO (numerically controlled oscillator) units implement optimized algorithms for their specific functions. Fixed-point arithmetic predominates in these implementations, with word widths matched to application requirements.

Scientific Computing Accelerators

High-performance computing systems may include dedicated elementary function accelerators that maintain full double-precision accuracy while achieving high throughput. These units implement sophisticated algorithms including table-based polynomial approximation with extensive range reduction, meeting the stringent accuracy requirements of scientific applications.

Neural Network Accelerators

Machine learning workloads frequently require activation functions including sigmoid, tanh, and softmax, all involving elementary function computation. Neural network accelerators implement these functions using reduced-precision approximations appropriate to the inherent noise tolerance of machine learning algorithms. Lookup tables and piecewise linear approximations provide sufficient accuracy at minimal cost.

FPGA Implementations

Field-programmable gate arrays enable custom elementary function implementations tailored to specific applications. CORDIC algorithms map efficiently to FPGA resources, using the abundant shift-add capability without requiring dedicated multipliers. Alternatively, FPGA implementations can exploit embedded multiplier blocks for polynomial evaluation methods.

The flexibility of FPGA implementation allows optimization across multiple dimensions: precision, throughput, latency, and resource utilization. Application-specific trade-offs can be evaluated through synthesis and simulation, enabling optimal designs for each use case.

Accuracy Requirements

The required precision of elementary function results varies widely across applications. Graphics rendering may tolerate errors of several units in the last place (ulp), while scientific computing demands correctly rounded results. Error analysis must account for range reduction, approximation, and rounding errors, ensuring the total error budget meets requirements.

Performance Requirements

Latency-critical applications favor parallel table-based methods and low-iteration convergence algorithms. Throughput-critical applications benefit from pipelined implementations that overlap multiple function evaluations. Energy-constrained applications seek minimum total operation counts, potentially accepting higher latency.

Resource Constraints

Available hardware resources strongly influence algorithm selection. Systems with limited memory favor CORDIC and polynomial methods. Systems with fast multipliers favor convergence and polynomial methods. Systems with large memory and bandwidth favor table-based methods.

Special Cases

Elementary functions require careful handling of special inputs including zero, infinity, NaN, and denormalized numbers. The IEEE 754 standard specifies behavior for many special cases, and conforming implementations must produce the required results. Boundary conditions at range reduction transitions also require attention to avoid discontinuities or accuracy loss.