Which are the best books about CORDIC algorithms and applications

For CORDIC algorithms check out Ray's website at

- Subroto Datta

at

Hi Subroto, Thank you for your pointing to Ray Andraka website.

I have read his paper, a very nice paper. I will print all references in his paper too. But I am afraid that the paper was published in

1998, almost 9 years ago and there must have been new progresses on this topics.

By searching Google using keyword: CORDIC, I found more than 300 books on the topics so that I need experts on this regard to point to the best books on the field.

Weng

at

Hi Subroto, Thank you for your pointing to Ray Andraka website.

I have read his paper, a very nice paper. I will print all references in his paper too. But I am afraid that the paper was published 1998, almost 9 years ago and there must have been new progresses on this topics.

By searching Google using keyword: CORDIC, I found more than 300 books on the topics so that I need experts on this regard to point to the best books on the field.

Weng

Not necessarily. All the books on my reference shelf I refer to most often are >10 years old. :-)

CORDIC was a great way to do many DSP functions before FPGAs with dedicated fast low-power multipliers came along. Nowadays, a lot of its advantages are waning. However, it's still a fascinating and elegant idea and worthy of study (certainly I keep meaning to learn more about it!).

I'd definitely start by absorbing all that Ray has to say on the subject, then go from there.

-Ben-

Hi Ben, I have read Ray paper and went to his website and read "How to calculate sine()". After reading I still have difficulties understanding its process.

Can you give an example on how to calculate sine(x), where x = 35 degrees?

I don't understand why he could calculate the factor K before starting calculation. Because during calculating, one doesn't know how many iterations should be taken to reach required accuracy.

Thank you.

Weng

You seen this, right?

HTH, Syms.

Ah, but that's not so. The whole point about CORDIC is that you *do* know in advance how many iterations it takes. You *never* stop the iterations early.

Having said that... the fudge-factor K reaches an asymptote so quickly that the error (for any number of iterations greater than about 10) is negligibly small.

I'll try an explanation... be sure to read it in a monospaced (Courier etc) font.

I can rotate a vector (x,y) through any angle A, giving a rotated vector (x', y'), by using the matrix multiplication

/ x' \ / cos(A) -sin(A) \ / x \ | | = | | * | | \ y' / \ sin(A) cos(A) / \ y /

We can divide both sides of the equation by cos(A)...

/ x'/cos(A) \ / 1 -tan(A) \ / x \ | | = | | * | | \ y'/cos(A) / \ tan(A) 1 / \ y /

since tan(A) = sin(A)/cos(A). That works out fairly easily as

x'/cos(A) = x - y.tan(A) or x' = cos(A) * (x - y.tan(A)) y'/cos(A) = x.tan(A) + y or y' = cos(A) * (x.tan(A) + y)

Now here comes the cunning part: Suppose we choose A so that tan(A) is exactly 2^(-N) for some integer N. The calculation of x.tan(A) and y.tan(A) is now a simple right shift (division by an exact power of 2). Note, too, that you can make the rotation negative simply by swapping the + and - operations.

Of course, to get this we require A = arctan(2^(-N)) for some integer N. For example:

N=0: A = arctan(1) = 45 degrees N=1: A = arctan(0.5) = 26.565... degrees N=2: A = arctan(0.25) = 14.036... degrees

All this would be harmless fun, until Volder (in his 1959 paper) was able to prove that ANY angle within a certain range (roughly +/- 100 degrees) can be expressed as the sum of all these different A, for N=0,1,2....infinity, if each of those terms is either added or subtracted (i.e. multiplied by +1 or -1). Of course we don't need to go to infinity, but only "far enough" for any given accuracy. To take your 35-degree example:

start 0 ... too small add arctan(1) 0 + 45 = 45 ... too big subtract arctan(1/2) 45 - 26.565 = 18.435 ... too small add arctan(1/4) 18.435 + 14.036 = 32.471 ... too small add arctan(1/8) 32.471 + 7.125 = 39.696 ... too big subtract arctan(1/16) 39.696 - 3.576 = 36.120 ... too big ...

and after, let's say, 16 such steps you will have converged on your desired 35 degree angle to within about 0.002%. Of course, you pre-calculate all these arctan angles and store them in a little lookup table.

Meanwhile, as you have been adding and subtracting these angles you have also been doing the matrix multiplication (in the right direction at each step, of course). If you started with x = 1.00000 and y = 0, then by the time you have finished, the final x and y values will be the cosine and sine of your desired angle BUT they will also have been multiplied by all the

1/cos(A) factors at each step. So you get a scaling (the CORDIC gain) of 1/cos(arctan(1)) * 1/cos(arctan(0.5)) * ...

Try it on a spreadsheet; you'll find this value very quickly converging on the limit value 1.646760258. To fix this problem, all you need to do is start with x=0.607252935... instead of 1.00000.

SUCH a pretty algorithm... but, as others have said, in these days of fast, cheap multipliers it's not so useful as it once was.

--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which 
are not the views of Doulos Ltd., unless specifically stated.

my recommondation:

Jean-Michel Muller: "Elementary Functions" - Algorithms and Implementation. Birkäuser 2006, ISBN 0-8176-4372-9

Covers different shift-and-add algos like cordic or BKM in detail...

WD

Weng,

First, thanks for looking at my paper. I'm not aware of much research on the CORDIC algorithm itself. There are a fair amount of applications papers that are using CORDIC in order to help solve problems, but nothing as far as I know regarding the algorithm itself.

There also are not a lot of books that devote much attention to CORDIC, although I suppose there are more now than there were when I wrote that paper. THere are a few books where I've seen a section on CORDIC. I think Frerking's Digital Communications (also ~10 years old now) has a section, as does Meyer-Baese's DSP with FPGAs. I don't think either has much more information than I have in my paper though.

Regarding the algorithm, the accuracy of the result is a function of the number of iterations you perform. Generally speaking, you compute the number of iterations required to meet the accuracy specification for your application and that becomes a system constant. From there, you compute K to determine the exact gain of your design in that application. In short, you do know how many iterations you are going to go before doing the calculation. Roughly speaking, the magnitude output for a vectoring CORDIC improves by two bits for each iteration. Phase output improves by one bit per iteration, and for rotation mode, the I and Q output accuracy improves by 1 bit per iteration.

I think the treatment in Frerking as well as that in Meyer-Baese is mor readable. Muller has a more complete treatise, but it is a difficult read comparatively speaking.

CORDIC still is hard to beat for extracting magnitude and phase. It's advantage is much less clear for phase rotators,e.g. mixers where there are plentiful fast multipliers on the FPGA. It is also still useful when you need a phase resolution on a rotator of more than about 2^12 revolutions, as the Sin/Cos lut starts getting unwieldy or needing more complicated interpolation to get the resolution.

Walter Dvorak wrote:

I second that. It's an excellent book. Although there are other good sources of information on CORDIC, this book had the best explanations I've seen for CORDIC algorithms (including many variations) and other shift-and-add algorithms (e.g., e^x, ln).

There was an earlier edition, so if you buy it used, you may want to make sure you get the 2006 edition.

Hi Jonathan, Thank you very much for you explanation. Very excellent explanation !!!

This is second time for me to get your help. The first time was when I was programming a random generation circuit copying your post in this group.

Weng

mentation.

.=2E.

Hi WD, Thank you for your recommendation. I will review the book and determine if I buy it.

Weng

I'm not entirely sure I understand this, since you can rather easily extract any derivative of sin/cos from a sin/cos lookup table with the help of a multiplier. For example, if I have a sin/cos LUT with 2^10/rev precision, can't I get sin/cos to nearly 2^20 precision with only one first-order interpolation? I agree that it's not so hardware-friendly a calculation as a CORDIC step, but it seems to offer much more bang per buck if you have hardware multipliers to hand.

Having said that, I probably should have done the sums before writing this post :-)

--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which 
are not the views of Doulos Ltd., unless specifically stated.