COordinate Rotation DIgital Computer. (Doesn't help much, does it?!)
It calculates the trigonometric functions of sine, cosine, magnitude and phase (arctangent) to any desired precision. It can also calculate hyperbolic functions, but we don't cover that here.
CORDIC revolves around the idea of "rotating" the phase of a complex number, by multiplying it by a succession of constant values. However, the multiplies can all be powers of 2, so in binary arithmetic they can be done using just shifts and adds; no actual multiplier is needed.
Compared to other approaches, CORDIC is a clear winner when a hardware multiplier is unavailable, e.g. in a microcontroller, or when you want to save the gates required to implement one, e.g. in an FPGA. On the other hand, when a hardware multiplier is available, e.g. in a DSP microprocessor, table-lookup methods and good old-fashioned power series are generally faster than CORDIC.
Funny you should ask: I just happen to: cordic-xls.zip. I highly recommend you open this up and look it over a little before you ask any more questions.
Yup, it's your lucky day: cordic.zip.
|Given a complex value:||C = Ic + jQc|
|we will create a rotated value:||C' = Ic' + jQc'|
|by multiplying by a rotation value:||R = Ir + jQr|
|To add R's
phase to C:
|To subtract R's
phase from C:
|To add 90 degrees,
multiply by R = 0 + j1:
|To subtract 90 degrees,
multiply by R = 0 - j1:
|To add a phase,
multiply by R = 1 + jK:
|To subtract a phase,
multiply by R = 1 - jK:
|L||K = 2^-L||R = 1 + jK||Phase of R
|Magnitude of R||CORDIC Gain|
|0||1.0||1 + j1.0||45.00000||1.41421356||1.414213562|
|1||0.5||1 + j0.5||26.56505||1.11803399||1.581138830|
|2||0.25||1 + j0.25||14.03624||1.03077641||1.629800601|
|3||0.125||1 + j0.125||7.12502||1.00778222||1.642484066|
|4||0.0625||1 + j0.0625||3.57633||1.00195122||1.645688916|
|5||0.03125||1 + j0.031250||1.78991||1.00048816||1.646492279|
|6||0.015625||1 + j0.015625||0.89517||1.00012206||1.646693254|
|7||0.007813||1 + j0.007813||0.44761||1.00003052||1.646743507|
You can calculate the magnitude of a complex number C = Ic + jQc if you can rotate it to have a phase of zero; then its new Qc value would be zero, so the magnitude would be given entirely by the new Ic value.
"So how do I rotate it to zero," you ask? Well, I thought you might ask:
- You can determine whether or not the complex number "C" has a positive phase just by looking at the sign of the Qc value: positive Qc means positive phase. As the very first step, if the phase is positive, rotate it by -90 degrees; if it's negative, rotate it by +90 degrees. To rotate by +90 degrees, just negate Qc, then swap Ic and Qc; to rotate by -90 degrees, just negate Ic, then swap. The phase of C is now less than +/- 90 degrees, so the "1 +/- jK" rotations to follow can rotate it to zero.
- Next, do a series of iterations with successively smaller values of K, starting with K=1 (45 degrees). For each iteration, simply look at the sign of Qc to decide whether to add or subtract phase; if Qc is negative, add a phase (by multiplying by "1 + jK"); if Qc is positive, subtract a phase (by multiplying by "1 - jK"). The accuracy of the result converges with each iteration: the more iterations you do, the more accurate it becomes.
[Editorial Aside: Since each phase is a little more than half the previous phase, this algorithm is slightly underdamped. It could be made slightly more accurate, on average, for a given number of iterations, by using "ideal" K values which would add/subtract phases of 45.0, 22.5, 11.25 degrees, etc. However, then the K values wouldn't be of the form 2^-L, they'd be 1.0, 0.414, 0.199, etc., and you couldn't multiply using just shift/add's (which would eliminate the major benefit of the algorithm). In practice, the difference in accuracy between the ideal K's and these binary K's is generally negligible; therefore, for a multiplier-less CORDIC, go ahead and use the binary Ks, and if you need more accuracy, just do more iterations.]
Now, having rotated our complex number to have a phase of zero, we end up with "C = Ic + j0". The magnitude of this complex value is just Ic, since Qc is zero. However, in the rotation process, C has been multiplied by a CORDIC Gain (cumulative magnitude) of about 1.647. Therefore, to get the true value of magnitude we must multiply by the reciprocal of 1.647, which is 0.607. (Remember, the exact CORDIC Gain is a function of the how many iterations you do.) Unfortunately, we can't do this gain-adjustment multiply using a simple shift/add; however, in many applications this factor can be compensated for in some other part of the system. Or, when relative magnitude is all that counts (e.g. AM demodulation), it can simply be neglected.
To calculate phase, just rotate the complex number to have zero phase, as you did to calculate magnitude. Just a couple of details are different.
- For each phase-addition/subtraction step, accumulate the actual number of degrees (or radians) you have rotated. The actuals will come from a table of "atan(K)" values like the "Phase of R" column in the table above. The phase of the complex input value is the negative of the accumulated rotation required to bring it to a phase of zero.
- Of course, you can skip compensating for the CORDIC Gain if you are interested only in phase.
Yes--you're very astute.
You basically do the inverse of calculating magnitude/phase by adding/subtracting phases so as to "accumulate" a rotation equal to the given phase. Specifically:
- Start with a unity-magnitude value of C = Ic + jQc. The exact value depends on the given phase. For angles greater than +90, start with C = 0 + j1 (that is, +90 degrees); for angles less than -90, start with C = 0 - j1 (that is, -90 degrees); for other angles, start with C = 1 + j0 (that is, zero degrees). Initialize an "accumulated rotation" variable to +90, -90, or 0 accordingly. (Of course, you also could do all this in terms of radians.)
- Do a series of iterations. If the desired phase minus the accumulated rotation is less than zero, add the next angle in the table; otherwise, subtract the next angle. Do this using each value in the table.
- The "cosine" output is in "Ic"; the "sine" output is in "Qc".
A couple of notes:
- Again, the accuracy improves by about a factor of two with each iteration; use as many iterations as your application's accuracy requires.
- This algorithm gives you both cosine (Ic) and sine (Qc). Since CORDIC uses complex values to do its magic, it's not possible to calculate sine and cosine separately.
- A survey of CORDIC algorithms for FPGAs by Ray Andraka of Andraka Consulting Group. This very readable paper's review of CORDIC's principles is more comprehensive and rigorous than this FAQ, so it's a good place to go from here.
- Wikipedia's CORDIC Page
- Fixed-Point Trigonometry With CORDIC Iterations by Ken Turkowski
- New Virtually Scaling-Free Adaptive CORDIC Rotator
- Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, September 1959.
- J. E. Meggitt, Pseudo Division and Pseudo Multiplication Processes, IBM Journal, April 1962.
- M. E. Frerking , Digital Signal Processing in Communication Systems [Fre94].
- Henry Briggs, Arithmetica Logarithmica, 1624.
Thanks to Ray Andraka for helping me understand. Thanks to Rick Lyons for review. Thanks to Mark Brown and Bill Wiese for providing links.