PDA

View Full Version : CORDIC for dummies



Bean
11-18-2010, 12:48 PM
Hey guys (and gals), way back in the SX days I got interested in CORDIC. And since Chip said the Propeller 2 would have a CORDIC engine, I thought I would create a tutorial explaining how CORDIC works.

When I started I had NO idea how the stuff worked, and it took quite a bit of experimenting until I was satisfied that I understood it. In the process I kept some notes. These notes have been expanded into this tutorial. It is still a work in progress, but I didn't want to get too far along if it doesn't make sense so far.

If you are interested in CORDIC and have a couple of minutes would you please read though this and give me your comments and suggestions.

Hopefully I'll have something worthwhile by the time the P2 comes out.

Thanks,

Bean

[Edit] I have fixed the math for the example at the end. It makes sense now.
I have updated the PDF.
I have updated the PDF again Nov 22, 2010
I have updated the PDF again Nov 23, 2010

Ale
11-18-2010, 01:01 PM
Bean that was some very nice explanation you wrote there, and the best of it was that it was machine/implementation agnostic. I'd complement it with some nice code, add the "bring to range" part and ship it.

Miss-spelling "Since we want to find degrees, instead of simply adding and subtraction a value"

Should be "Since we want to find degrees, instead of simply adding and subtracting a value"

great work !

Roy Eltham
11-18-2010, 01:49 PM
Bean,

First off, before reading this, I wasn't familiar with CORDIC at all. I think I understand it now after reading this doc, so thanks. Below are my thoughts while reading the document.

The first page is describing a binary search. In fact, the whole thing is just binary searching in different "spaces".

The last two pages use << (shift up), but shouldn't it be >> (shift down) instead? Since you are multiplying by 0.5, 0.25, 0.125, etc.. that is actually divide by 2, 4, 8, etc. Which means you want shift down, not shift up. Maybe I missed something?

Also, on the last page you say:
X = 262 (223.607 is the real radius, so we scale by 0.85346 for any points)
Is that scaling factor really valid for any input values of X,Y? Or is it just close enough to be "good enough"?

Bean
11-18-2010, 01:56 PM
@Roy, Yeah, you're right that should be >> instead of <<. And yes, that scale is for ANY point as long as you do the same number of loops.

One thing I thought when X=2*Y that was a 30 degree angle, but ATAN(0.5) gives 26.565 ???

Or is a 30 degree angle when the hyp is 2*X ???

Anyway I will go through all the math before I finalize it and make sure it is all correct.

I also want to make some graphs and maybe even a propeller TV demo showing the process.

Bean

kwinn
11-18-2010, 02:09 PM
Excellent explanation of Cordic. I was aware of the technique, but not the name. I thought of it as a form of binary search. It is applicable to solving a wide range of calculations/problems.

Bean
11-18-2010, 02:44 PM
I have found that I have a wrong sign in the math for the final forumla and example.
I will fix them and re-post.

Bean

Bean
11-18-2010, 03:03 PM
Okay, I fixed the math and reposted it.

Thanks for the comments so far.

Bean

Baggers
11-18-2010, 03:57 PM
Great post Bean :)

Ray0665
11-18-2010, 04:13 PM
I first encountered Cordic in Beau Schwabe's HM55B object and never did understand it even after reading several papers I found on the web. Mostly because my math education was 40 years ago. I was however able to lift it from that object and and use it in the navigation code of a robot I created even if I didn't understand it. After reading this - I get it!! -- Your paper here is clear consice and completely understandable well done!!

I humbly offer here my Trig object with thanks to both you and Beau

Heater.
11-18-2010, 04:26 PM
Bean,

That's great, thank you.

Do you think you could do a work like that on the Fast Fourier Transform? The workings of which have avoided lodging in my brain for decades now:)

dMajo
11-18-2010, 04:55 PM
Nice explanation. If also me, with my bad English, have get it that mean you have done an excellent job.

Duane Degn
11-18-2010, 05:09 PM
Bean,

That makes it just too easy!

All I knew about CORDIC was that it's a way of doing math with a microcontroller.

Is anyone out there writing a PASM book? If there isn't one in the works, you should take it up. Your CORDIC tutorial was very easy to understand. I feel like I'm starting to understand PASM myself but I sure wish I had a nice tutorial to follow.

I'd be very interested in any other tutorials you create.

Thank you,

Duane Degn

Roy Eltham
11-18-2010, 05:36 PM
Bean,

Read the new version, and I noticed that you fixed the <<'s to be >>'s on page 6, but on page 5 it's still got them ad <<'s. Other then that, it looks great.

Phil Pilgrim (PhiPi)
11-18-2010, 05:38 PM
Wow, Bean, very cool! Once the laity sees this, the high priests will be out of a job! :)

-Phil

Bean
11-18-2010, 05:40 PM
Roy, Thanks for catching that.

I just fixed it and added a bit of a explaination and graph on the first page. Reposted just now.

Bean

ErNa
11-18-2010, 09:05 PM
Hi, great. Maybe you could add in the first "guessing", that this is called successive approximation and just the way a SAR-ADC is working. That would give another link. The method is also known from math to determine the zero crossing of a functions graph.

prof_braino
11-19-2010, 01:15 PM
This is excellent work. Even I could understand it.

My only comment will be to re-consider the unfortunate title.

"CORDIC for Beginners" or similar would have much less negative connotation than "dummies".

The "for dummies" series has a negative connotation from, of course, the words dummies, and from its use in media by character that demonstrate stupidity after glancing at one on the books. In real life, the "Brain Surgery for Dummies" book proved to be a total rip-off, the subject did not show any measurable improvement before expiring.

Otherwise it great.

Do you do educational stuff professionally?

Heater.
11-19-2010, 01:31 PM
prof_braino,

Some years ago I may have had the same objection to the use of "dummies" in the title. But the "bla bla for Dummies" thing is part of the culture now and one knows what to expect when one sees it. In most part due to the series of books I guess.

Also in this case I think it fits better than other alternatives. such as "Introduction to...." or "...for beginners."

Why is that?

Well if you are a beginner there are already pages for you on wikipedia and other places.

They for beginners and are quite fine but boom, you are immediately hit in the face with matrix notation and other such things that get in the way for dummies, err I mean, the mathematically uninitiated.

This document demonstrates my long held belief that there are many brilliant but ultimately simple concepts in mathematics that almost anyone could understand if they could be presented in such a way as to avoid the blindness and confusion brought on by the symbols of mathematics itself.

For example, the way it is possible in calculus to divide zero by zero and get a meaningful result, the slope of a line.

Dunnsept
11-19-2010, 01:46 PM
Bean:

awesome stuff! and I hate math ;-)

on page 6:
Continuing on, the angle would be for 0.25, turns out to be 14.03624347

I assume something like:
Continuing on, we calculate what the angle would be for 0.25, which turns out to be 14.blahblah

Jay Kickliter
11-19-2010, 05:22 PM
I second that. I'm taking communications theory course that should be renamed 'Fourier, Fourier, and more Fourier', yet even the the textbook doesn't try to explain FFT. No matter how many times I read up on it, I just don't get it.


Bean,
Do you think you could do a work like that on the Fast Fourier Transform? The workings of which have avoided lodging in my brain for decades now:)

Heater.
11-19-2010, 05:33 PM
Well, the Fourier part I can just about get my head around.

But the trick(s) that go on to make a fast discrete fourier transform just haven't registered yet.

prof_braino
11-20-2010, 12:38 AM
I second that. I'm taking communications theory course that should be renamed 'Fourier, Fourier, and more Fourier', yet even the the textbook doesn't try to explain FFT. No matter how many times I read up on it, I just don't get it.

I third that!

But wait, Bean did this great work, now we are demanding more...

This here is saying something to me, I should try to listen....

We don't to punish his good work with a burden of more work...

Why don't the rest of follow Beans example, a start another thread called
Fourier for Dummies, and see if we come up with something as effective.

We could decide if Beam just "has the magic" or if he's given us a format for presenting a concept.

Any takers? I nominate Heater, he says he knows the Fourier part.

Heater.
11-20-2010, 02:17 AM
prof_braino,

You are right, we are greedy. We should be grateful for what we get.

Interesting idea about the "Fourier for Dummies" thread. Although I can't see it working. Something about "the blind leading the blind":)


We could decide if Beam just "has the magic" or if he's given us a format for presenting a concept.


I believe that, in this case at least, Bean does indeed have "the magic".

I think that to pull this off requires a something special.

Firstly that is someone who has a deep understanding of the topic at hand. That is to say, someone who understands the essence of the problem stripped free of all the mathematical notation and baggage that normally accompanies such things. The notion is built into their being.

Secondly they need to be aware of the level at which their intended audience is working. They have to be able to comprehend what it is like to have a "dummies" brain, devoid of most of that previously mentioned mathematical baggage.

With those things in place it becomes possible to make the explanation of the idea in a language clear enough for the audience.

As for "format for presenting a concept", That's nice but having a template for such a format is not anywhere near sufficient as you might see from my statements above.


...I nominate Heater, he says he knows the Fourier part.

That's nice but did you miss the "just about" part of my statement. I for sure don't meet the first criteria for the "magic" I outlined above.

prof_braino
11-20-2010, 05:00 PM
Heater is right, this probably won't work. So lets do it anyway!

I started a new thread to make "Fourier for dummies"

We can analyze Bean's work and see what we can do for Fourier.

Somebody smart like Leon or Sapieha can straighten us out where we go wrong.

Test will be whether heater or I can understand Fourier when we stop working on it.

As a note: I find the best way to understand something is to explain it to somebody else.

I helped put myself through college by tutoring in my worst subjects.
There were always lots of folks in need of tutoring,
and I was committed to spending the time anyway.

I would try to explain the notes and text by paraphrasing and examples.
Usually the light would go on just after the other person got it.

The only time this technique did not work was with eigen-vectors,
which I apparently passed on the final without actually understanding.

Heater.
11-20-2010, 05:22 PM
prof_braino


Test will be whether heater or I can understand Fourier when we stop working on it.

That's going to be a looooong thread:)

As I said the idea of Fourier analysis/transform is not the issue (well, it was understood well enough during my college times at least) but the trick to speed up the calculation in the DFT. I mean all that "bit reversal" stuff.

Campeck
11-20-2010, 06:38 PM
This document demonstrates my long held belief that there are many brilliant but ultimately simple concepts in mathematics that almost anyone could understand if they could be presented in such a way as to avoid the blindness and confusion brought on by the symbols of mathematics itself.

This is what keeps me from pursuing things I would otherwise pursue. Except in this case I read it and I still don't get it...I'll read it again but...I might just be below "dummy" lol

Heater.
11-20-2010, 07:29 PM
Campeck,

So you are stuck. Good:)

That means you can discuss with Bean about exactly at which point you lose the thread. Hopefully Bean will help you get unstuck. And perhaps then he will have a little improvement or clarification for the document as a result. We all win:)

Roy Eltham
11-21-2010, 06:37 AM
Bean,
I found another error in the doc. On the last page, where you are doing the step that does >> 3. -37 / 8 = -4, so 362 - (-4) = 366, you have it as 362 -2 = 360. Also, all the 360s after that should be 366s. Including the final step, so your scaling factor needs adjusting to 0.610948.

I found it while I was doing a Spin implementation of your example which I have included below. I put a big comment block in there explaining the funky stuff I had to do with the shifts to make it work right with negative numbers. Also, I inserted comments around the actual algorithm bits with your pseudo code from the doc.



'************************************************* *************
'* CordicExample *
'************************************************* *************
CON
_clkmode = xtal1 + pll16x
_clkfreq = 80_000_000

OBJ
math : "Float32"
VAR
long input_x, input_y

PUB main | LoopNum, SumAngle, sign_x, new_x, new_y

math.Start

' setup are starting state
input_x := 200
input_y := 100
SumAngle := 0

' Since the shift operator (>>) doesn't deal with negative numbers like we want, and the arithmetic shift (~>)
' on negative numbers always results in at least -1 (instead of 0) (e.g. -1 ~> 1 == -1), we have to do some
' extra stuff to manage it.

' For the y case it is simpler because we are using it to decide whether to add or subtract. So we can just do a
' normal shift when y is positive, and when y is negative we absolute value (||) y and change the subtract to an add.

' For x we get the sign and then use it to do this (^ is XOR): ((||x >> LoopNum) ^ -sign_x) + sign_x
' which is equivolent to (x >> LoopNum) for positive values, since sign_x is 0 in that case.
' For negative values sign_x equals 1, so the operation looks like this: (||x >> LoopNum) ^ -1) + 1
' Since -1 is $FFFF_FFFF, the XOR operation is doing a 2s compliment of our number. This flips all the bits in the
' number. Making it negative, but when we do that we end up with a negative number that is 1 more negative than the
' positive number was (i.e. the 2s complement of 1 (0000_0001) is -2 (1111_1110)), so we need to add 1 to make it right.
' Basically, doing (n ^ -1) + 1 is doing an un-absolute value of n (as long as n is positive).
' Doing this avoids adding more if checks.
'

repeat LoopNum from 0 to 7
' we need the sign of x as a 0 or 1
sign_x := input_x >> 31
' If Y is positive
if input_y > 0
' Xnew = X + (Y >> LoopNum)
new_x := input_x + (input_y >> LoopNum)
' Ynew = Y - (X >> LoopNum)
new_y := input_y - (((||input_x >> LoopNum) ^ -sign_x) + sign_x)
' SumAngle = SumAngle + AngTable[LoopNum]
SumAngle := math.FAdd(SumAngle, AngTable[LoopNum])

' If Y is negative
elseif input_y < 0
' Xnew = X - (Y >> LoopNum)
new_x := input_x + (||input_y >> LoopNum) ' since we absolute valued y, we change the subtract to an add
' Ynew = Y + (X >> LoopNum)
new_y := input_y + (((||input_x >> LoopNum) ^ -sign_x) + sign_x)
' SumAngle = SumAngle - AngTable[LoopNum]
SumAngle := math.FSub(SumAngle, AngTable[LoopNum])

else
' Y = 0, so we are done
quit

' assign the new values back in for the next loop around
input_x := new_x
input_y := new_y

return SumAngle

DAT
AngTable long 45.0, 26.56505, 14.03624, 7.12501, 3.57633, 1.78991, 0.89517, 0.44761

fixmax
11-21-2010, 06:24 PM
prof_braino,

Some years ago I may have had the same objection to the use of "dummies" in the title. But the "bla bla for Dummies" thing is part of the culture now and one knows what to expect when one sees it. In most part due to the series of books I guess.

Also in this case I think it fits better than other alternatives. such as "Introduction to...." or "...for beginners."

Why is that?

Well if you are a beginner there are already pages for you on wikipedia and other places.

They for beginners and are quite fine but boom, you are immediately hit in the face with matrix notation and other such things that get in the way for dummies, err I mean, the mathematically uninitiated.

This document demonstrates my long held belief that there are many brilliant but ultimately simple concepts in mathematics that almost anyone could understand if they could be presented in such a way as to avoid the blindness and confusion brought on by the symbols of mathematics itself.

For example, the way it is possible in calculus to divide zero by zero and get a meaningful result, the slope of a line.

You are exactly correct in my opinion. I think another great example of that is PID loops and closed loop control. Most web searches go through a long dissertation on the math, but its really very simple. I think the biggest problem that I see with math whizzes is that they get so caught up in the beauty of math, that they forget who they are explaining to. People that can understand math at that level likely already know how to do it themselves!

Great CORDIC explanation by the way! I'd love to see more stuff like this on the forum. There are some truly brilliant people who are active here and could contribute much.

Tracy Allen
11-22-2010, 05:53 AM
That's a nice writeup Bean, a good perspective!

For the record, here is a link to an early discussion of CORDIC on the Prop (http://forums.parallaxinc.com/forums/default.aspx?f=25&p=1&m=148362).
Those interested should check out Chip's chapter 12 on speech synthesis in Programming and customizing the multicore propeller microcontroller (http://www.parallax.com/StoreSearchResults/tabid/768/List/0/SortField/4/ProductID/637/Default.aspx?txtSearch=programming+and+customizing ). Once one gets the concept (or the math!), then there remains appreciation of what the machinery can do--Chip certainly gets it! States, "Now, I'll introduce the VocalTract object. This is the neatest piece of software I've ever written, and it's the kind of program that the Propeller chip was designed for." Indeed, there are instructions in pasm that are tailored for CORDIC, and as Bean pointed out, we can look for more of that integrated into the hardware in Prop II. VocalTract requires the signal to pass through 4 resonant cavities, the "formants", the vocal resonances characteristic of the individual. You might think that this would take a pretty advanced analysis, a Fourier spectrum convoluted with the cavity resonance, perhaps. No. Chip says, "In each of the vocal tracts resonators, the incoming signal is summed into Y of an (X,Y) point, which defines the state of the resonator. Then, that point is CORDIC-rotated by an angle directly proportional to the formant's center frequency. The resulting Y of the (X,Y) point is passed on to the next resonator. When in-bank excitation is received, the (X,Y) point grows further from (0,0) as it rotates around. Out-of-band excitation causes the amplitude to decay to the point where the resonator pretty much just passes its input through to the output. If this wasn't simple enough, since the step-angle fed to each formant's CORDIC rotator is directly proportional to the formant's center frequency, simple linear interpolation is used to slide each formant from one frame's setting to the next. Goodbye, math headaches!"

(Indeed!)

MGreim
11-22-2010, 01:48 PM
Hi,

last year i have written / translated / adapted a cordic atan2 algorithm for the pasm.

My knowledge base had been:
http://www.worldserver.com/turk/computergraphics/FixedPointTrigonometry.pdf
as good theoretical introduction and C-code
and
http://www.gamedev.net/reference/articles/article406.asp
as C-source
i hope i didn't violate any (c) restrictions, but at least in the EU you can't patent an algorithm.

Algorithm and implementation its quite fast i think. Enclosed also a picture comparing the results from the Propeller for several sin/cos values to the atan2 values calculated with perl on a Linux machine.
Maybe its helpful for someone...



Regards

Markus

Graham Stabler
11-22-2010, 03:46 PM
Very nice.

BTW, here are some other CORDIC threads:

http://forums.parallax.com/showthread.php?t=88799

and

http://forums.parallax.com/showthread.php?p=642142

The former has my attempts at understanding with some code the second is about my cordic engine which was some code designed to do pretty much all the mathematic operations using cordic. There is some code posted but I am not sure I posted or even finished the object.

Graham

Ray0665
11-22-2010, 05:07 PM
Yikes!!AfterreadingtheabovetwolinksIappreciateeven moretheworkthatBeandidtalkaboutgobbledeegookandobs fucationdomainthisandmatrixthateeegads.
Thank you once again Bean, You go dude!

Batang
11-22-2010, 05:49 PM
For a good reference on the subject:

http://www.amazon.com/Embedded-Systems-Building-Blocks-Second/dp/0879306041/sr=1-1/qid=1172159470/ref=sr_1_1/103-6846089-8685436?ie=UTF8&s=books

Bean
11-22-2010, 06:48 PM
For those interested, I have expanded and updated the tutorial.
Please download it again from the first post to see the new version.

I still need to do a spin program to compute Sin/Cos but that shouldn't be too hard.

Bean

Roy Eltham
11-22-2010, 08:32 PM
Bean,
The improved document is great, thanks! Glad you added the SIN/COS stuff.

However, I noticed in your code example, you use the arithmetic shift right operator (~>) this doesn't work fully correctly for negative numbers. It won't shift a negative number down to 0. In cases where you want it to shift all the way down to 0, it'll end up with a -1.

In my example code posted above I showed a way to get around that. It also has my attempt at explaining the issue and the work around in the comments.

Roy

Bean
11-24-2010, 11:29 AM
I have updated the tutorial to the final version.
You can get it from the first post in this thread.

Enjoy,

Bean

evanh
11-24-2010, 01:05 PM
Ha, never knew that had a name. I've always just said "like a binary search" when referring to the general idea.

Roy Eltham
11-24-2010, 03:12 PM
Bean,

Any response to the issue I brought up above about the ~> operator?

Roy

lonesock
11-24-2010, 06:14 PM
Roy, that's a nice way to handle the ~> issue. In my experience, however, the issue doesn't bite me, as I never go for a full 32-bits' worth of accuracy. In F32 I prescale my vector, do 25 iterations (as float 32 uses 24 bits of mantissa), then use the result. So, I start with a 30-bit number, get about 25 significant bits, leaving about 5 insignificant bits down at the bottom. In that scenario, a 0 masquerading as a -1 doesn't affect my results any, so I just don't spend the cycles or code space handling that case.

Jonathan

SSteve
11-25-2010, 01:13 AM
Great tutorial. The few times I tried to understand CORDIC I got lost pretty quickly. But I followed this all the way through. It makes complete sense.

A few typos:


then it must have been 0 and 45. If it remains positive then it must have been 45 and 90.

s/been/been between/g


The only side effect is that the hypotenuse does not keep itís scale

s/it's/its/


Xnew=250+12=362

s/250/350/


On the following pages are two program that show how to use the CORDIC method.

s/program/programs/


Wait two seconds for user to start PST

s/two/four/

Bean
11-25-2010, 01:45 AM
SSteve, Thanks for catching those mistakes.

Bean

ErNa
11-25-2010, 08:30 AM
Bean,

Any response to the issue I brought up above about the ~> operator?

Roy

YES, I didn't see the "above", but one should ALWAY use ~> if the numbers are not explicitely positive, what again should never be the case ,-)

I replaced all my >> by ~> if I not intend to clear the MSB.
A good idea to point to ~>, it just creates a savety margin

davidsaunders
03-16-2011, 07:21 PM
Thank you. I have been told many times to use CORDIC, though did not understand CORDIC, (I had always used succive approximation in a way that turns out to be CORDIC). Thank you this helps my understanding so much.

M. K. Borri
03-16-2011, 08:35 PM
If it helps any, I wrote myself a fast atan2 approximation here http://robots-everywhere.com/portfolio/math/fastatan2.htm and a math library that uses it and also does fast geodesy http://obex.parallax.com/objects/194/

John A. Zoidberg
05-17-2011, 03:28 PM
Hello there,

Sorry for bumping up the post, but I'm a bit confused about the algorithm.

I tested the algorithm with the x = 3 and y = 4, and it should give 53.13 degrees.

However, it's 43.695. Eventually I have to multiply it by 0.607 (cordic gain) and then multiply it by two again to get back the approximation.

What could I have been missing? :)

Bean
05-17-2011, 08:51 PM
John,
The 0.607 cordic gain is only for the HYP value. The angle should be the correct value.

When I get a chance I'll run the numbers and see what I get.

P.S. I just realized that the diagram on the first page is showing the angle measured from the right side. Normally it is measured from the left side, so you would get (90 - 53) = 37 degrees.

Bean

Tracy Allen
05-18-2011, 01:57 AM
John,

Did you try literally x := 3 and y := 4 in Bean's program from the pdf? If so that won't work well, because the program calls for units of 1/256, so the whole numbers 3 and 4 should be scaled up to x := 3*256 and y := 4*256.

I tried 3 and 4 without the *256, and it came out at 57.558 degrees, which is different from the value you reported and also different from the nearly correct value of 53.152 degrees that I come up with when x := 3*256 and y := 4*256.

It is true that the small values 3 and 4 by themselves should also come up with the same angle, however, it is necessary to modify the CORDIC program, an adaptive wrapper to scale small values up for computation and then back down, to avoid numerical errors.

John A. Zoidberg
05-18-2011, 02:53 AM
Tracy,

Thanks for the prompt reply. I didn't scale down anything, and I had just now checked the older post about the Cordic (dated 2006), and it seems that you mentioned something about "method not usable in small numbers".

I'll scale the numbers as you said and try it on Matlab. Right now all I did on the Cordic is pencil-and-paper so it'll be a bit slow.

On top of that, I'll be writing the routines in small Atmega and PIC microcontrollers if it's successful.

User Name
03-10-2012, 12:30 AM
This document demonstrates my long held belief that there are many brilliant but ultimately simple concepts in mathematics that almost anyone could understand if they could be presented in such a way as to avoid the blindness and confusion brought on by the symbols of mathematics itself.

Heater's comments lodged in my brain, back-in-the-day. So, today, when I eventually figured out what cyclic prefixing means in the context of OFDM design, Heater's remarks were the first thing that popped into my head. It amazes me how simple and straightforward concepts can be couched in such marvelously obfuscatory language...under the guise of explaining them!

BTW, it seems to me that Bean's CORDIC for Dummies thread has brought quite a few individuals to the Parallax forum for the first time, helping both Parallax and CORDIC enquirers. Can't beat that!