Speeding up the CORDIC algorithm with a DSP
Digital signal processors (DSPs) crunch the numbers for applications that require fast analog-to-digital-to-analog conversion, such as software-defined radio and radar. If you weren't using a DSP, you might use the CORDIC algorithm to perform similar calculations on your IC. The strength of the CORDIC algorithm is its ability to solve vector rotation without using a multiplier.
Despite the CORDIC's well-documented properties, you won't often find it implemented on a DSP because the CORDIC was conceived 49 years ago when the cost of multiplier hardware was prohibitive. (DSPs are typically equipped with multipliers.) But what happens when you mix the two? When a CORDIC algorithm is implemented on a DSP processor, can the multipliers improve CORDIC's performance, or can they be left idle?
We're going to answer this question positively by proposing a novel way to map the CORDIC algorithm onto DSP hardware. This new method uses the DSP's MAC (multiply/accumulate) units and eliminates the conditionals, thus preserving the machine pipelining.
CORDIC, an acronym for COordinate Rotation DIgital Computer, is a class of shift-add algorithms that rotate a vector in a plane. CORDIC has become a commonly used method in memory- and CPU-constrained embedded systems because it's a simple and efficient way to calculate the hyperbolic and trigonometric functions found in every scientific calculator.
Most often the algorithm is used when no hardware multiplier is available, such as in microcontrollers and FPGAs, because the only operations it requires are addition, subtraction, bitshift, and table lookup.
CORDIC is widely used due to its simplicity and its property of relatively fast convergence. It has many applications, including computing trigonometric functions and converting Cartesian coordinates to polar coordinates (and vice versa).
Basically the CORDIC algorithm chooses special angles of rotation such that it can perform the rotation operations by simple shifts and additions, rather than the multiply functions that are required in the general case. Thus, design teams can use the CORDIC algorithm instead of hardware multipliers, which require a higher gate count and cost more to build.
Before we get into the details of how to map the CORDIC algorithm onto a DSP engine, we'll briefly review the CORDIC algorithm that calculates the magnitude and angle of a vector from its Cartesian coordinates. We'll then describe the implementation of the algorithm on a DSP processor, which uses addition and shift operations only.
First, however, let's review the traditional approach to implementing CORDIC.
Let v be a vector with Cartesian coordinates (x, y). To simplify the description, we consider the right half plane of a unit circle only, in other words, we assume 1>x>0, 1>y.
The objective is to find the magnitude
If we can somehow rotate vector v = (x, y) to ve = (xe, ye) such that ye=0, the magnitude r will be the x-coordinate xe and the angle φ will be the rotated angle. This rotation is actually achieved by a number of successive rotations (called subrotations). For each subrotation, the angle of rotation is properly chosen such that:
• The computation can be accomplished by addition and shift operations only (avoiding the use of multiplication).
• The set of subrotations will drive vector v to the x-axis, in other words, making coordinate y equal to 0; this can be guaranteed if the current rotation is half of the previous one.