CORDIC for dummies
Bean
Posts: 8,129
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
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
Comments
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 !
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"?
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
I will fix them and re-post.
Bean
Thanks for the comments so far.
Bean
I humbly offer here my Trig object with thanks to both you and Beau
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:)
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
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
I just fixed it and added a bit of a explaination and graph on the first page. Reposted just now.
Bean
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?
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.
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
But the trick(s) that go on to make a fast discrete fourier transform just haven't registered yet.
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.
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":)
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.
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.
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.
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.
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
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:)
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.44761You 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.
For the record, here is a link to an early discussion of CORDIC on the Prop.
Those interested should check out Chip's chapter 12 on speech synthesis in Programming and customizing the multicore propeller microcontroller. 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!)
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