Breaking News
Comments
Newest First | Oldest First | Threaded View
Kevin Neilson
User Rank
Manager
Re: Here's how it's done
Kevin Neilson   3/16/2014 1:18:50 AM
NO RATINGS
You can do arctan with a modified version of CORDIC.  You can also do something similar to the method I described below, but using the Farrow technique.  It's not easy to get the derivative of arctan as it is for sine, so you use a blockRAM LUT for arctan, another for the derivative of arctan, and possibly another for second derivative.  Then you can do a Taylor expanson to interpolate between the LUT values in the first LUT by using the derivatives in the other LUTs.  Use Horner's Method again to save multiplies.  The Farrow method works for arbitrary functions.

So if you want to know the arctan between LUT values N and N+1, you take the N value from the first LUT, add 1/2 * the Nth value in the second LUT, and (1/2)^2 / 2! * the Nth value in the 3rd LUT.  (Not taking into account Horner's Method.)  There are probably a lot of other techniques for arctan that smart people have come up with.

If you're doing arctan on a complex IQ value in order to find its phase, for demodulation purposes, you can take the absolute value to map it into the first quadrant, and then use one 2-dimensional lookup table to find phase angle and another for magnitude.  (There are also simple algebraic functions which approximate magnitude pretty well.  That might be another interesting topic for the next article in this series.)  By 2-dimensional, I mean that half of the address bits are used for I and half for Q and the output of the LUT gives you arctan(Q/I). 

-Kevin Neilson

betajet
User Rank
CEO
Re: Here's how it's done
betajet   3/15/2014 7:57:12 PM
NO RATINGS
anon: That's a very nice way to do sine.  Thank you for posting it.


Do you have a suggestion for arctan?

TanjB
User Rank
Rookie
Don't forget to test
TanjB   3/15/2014 7:38:22 PM
NO RATINGS
Beware of maintaining mathematical properties such as monotonicity.  A classic problem with rough estimates from tables is to have the interpolations at the joints between section be discontinous or even slightly backwards step.  Even when you think you have the right formula all you need is one of them to falsely round down and the other to falsely round up, which can happen with a fraction of lsb inaccuracy.  Since an implementation can end up being reused somewhere else you probably want to be sure it is suitable for unexpected uses.

Given the small word length of your inputs you can afford to run tests which exhaustively check every value for glitches like that.

Kevin Neilson
User Rank
Manager
Here's how it's done
Kevin Neilson   3/14/2014 12:02:59 AM
NO RATINGS
The pure Taylor works, but it just eats up too much logic.  Here's how it's normally done:  You start with a lookup table in blockRAM.  There is plenty in a Xilinx part.  You then do a Taylor to interpolate between the LUT values.  A first-order (linear interp) or second-order is usually good.  You need the derivative of sine at the LUT points.  The derivative is cosine, which you get from a different address in the same LUT.  Since the blockRAM is dual-port, you read it out on the second port on the same cycle.  Now you multiply this by the lower-order address bits (left over after using the upper bits for the LUT address) and bit-shift and add to the LUT value.  Booyah, 1st-order Taylor.  If you want to do higher orders the derivatives are easy (either sin or cos from the LUT or their opposites) and you use Horner's Method to reduce the number of multiplies necessary.  This method is also super-fast when you use blockRAMs and DSP48s.  This is usually what you'll get if you use a core.

CORDIC is OK if you want a lot of precision and you have a lot of time to blow.  It's not as valuable as it was in the pre-DSP48 days.

-Kevin Neilson

tom-ii
User Rank
Blogger
Re: I'd definitely stick to CORDIC
tom-ii   3/13/2014 6:10:43 PM
NO RATINGS
@MButts:

 

Thanks!

MButts
User Rank
Rookie
Re: I'd definitely stick to CORDIC
MButts   3/13/2014 6:09:09 PM
NO RATINGS
Check out Ray Andraka's paper about CORDIC on FPGAs at his site:

http://www.andraka.com/cordic.htm

Very clearly explained, you'll understand CORDIC after reading Ray.

tom-ii
User Rank
Blogger
Re: I'd definitely stick to CORDIC
tom-ii   3/13/2014 5:43:54 PM
NO RATINGS
@betajet:

That's the 1st I've heard of "BAM."  Thanks for the info!

As for CORDIC, I've still not quite wrapped my head all the way around it, yet, but I see it takes some pre-computed lookup tables for it to work.  Which is okay, I suppose, but the purpose of this set of exercises was to get some decent fixed-point libraries put together.

The other thing about this silly project was that it got the computation done in a single (albeit slow) clock tick. 

 

FWIW, and as you point out, YMMV  ;)

betajet
User Rank
CEO
I'd definitely stick to CORDIC
betajet   3/13/2014 5:19:28 PM
NO RATINGS
IMO, CORDIC is a great way to compute sine and cosine, and also arctan.  CORDIC only uses shifts and ADD/SUB.  I'd also stick to fixed-point arithmetic, since the values of sin and cos only go between -1 and +1.

As far as representing angles, I like Binary Angular Measurement (BAM).  You represent an angle as a fixed-point binary fraction of a circle.  You use every bit of your number representation, and BAM automatically calculates angles modulo 360 degrees due to the modulo 2^N nature of binary arithmetic.

BAM angles have the nifty property that unsigned and two's complement arithmetic are equivalent.  You can think of angles as being from 0 to just less than 360 degrees using unsigned arithmetic, or from -180 to just less than 180 degrees using 2's complement arithmetic.

JMO/YMMV



Most Recent Comments
Steve Manley
 
engineers
 
Weapon
 
rick merritt
 
rick merritt
 
Loser99
 
Aeroengineer
 
Aeroengineer
 
Aeroengineer
EE Life
Frankenstein's Fix, Teardowns, Sideshows, Design Contests, Reader Content & More
Glen Chenier

Engineers Solve Analog/Digital Problem, Invent Creative Expletives
Glen Chenier
Post a comment
An analog engineer and a digital engineer join forces, use their respective skills, and pull a few bunnies out of a hat to troubleshoot a system with which they are completely unfamiliar. ...

Max Maxfield

What's the Best Traveling Toolkit?
Max Maxfield
13 comments
A few years ago at a family Christmas party, I won a pocket knife as part of a "Dirty Santa" game. This little scamp was a Buck 730 X-Tract. In addition to an incredibly strong and sharp ...

Rishabh N. Mahajani, High School Senior and Future Engineer

Future Engineers: Don’t 'Trip Up' on Your College Road Trip
Rishabh N. Mahajani, High School Senior and Future Engineer
10 comments
A future engineer shares his impressions of a recent tour of top schools and offers advice on making the most of the time-honored tradition of the college road trip.

Larry Desjardin

Engineers Should Study Finance: 5 Reasons Why
Larry Desjardin
41 comments
I'm a big proponent of engineers learning financial basics. Why? Because engineers are making decisions all the time, in multiple ways. Having a good financial understanding guides these ...

Top Comments of the Week
Flash Poll
Like Us on Facebook
EE Times on Twitter
EE Times Twitter Feed

Datasheets.com Parts Search

185 million searchable parts
(please enter a part number or hit search to begin)