Forums

Sine Lookup Table with Linear Interpolation

Started by rickman March 16, 2013
Robert Baer wrote:

> glen herrmannsfeldt wrote: > >> In comp.dsp Robert Baer<robertbaer@localnet.com> wrote: >> >> (snip, I wrote) >> >>>> See: >> >> >>>> http://ia601506.us.archive.org/8/items/bitsavers_nationaldaMOSIntegratedCircuits_20716690/1972_National_MOS_Integrated_Circuits.pdf >>>> >> >> >>>> The description starts on page 273. >> >> >> I just tried it, copy and paste from the above link, and it worked. >> >> You might be sure to use Adobe reader if that matters. >> >> Also, it is page 273 in the document, page 282 in the PDF. >> >> (snip) >> >>> Problem with that..could see only front and back cover. >>> Different source perhaps? >> >> > The basic approach given there is very good; use of puny 4 or 5 digit > tables is a major weakness: sqrt(2)/2 as 0.7071 is junk; CRC in the > squares, cubes and roots section gives sqrt(2) as 1.414214 (6 digits) > and sqrt(50) as 7.07168 (also 6 digits). > And if one needs more, use the Taylor series (for reasonably small > angles) as it converges fast (Nth odd power and Nth odd factorial). > --or, use the FPU in the computer to get SIN and COS at the same time! > > Reduction from 360 degrees helps: > "Split" 180 degrees: sin(-x)=-sin(x) > "Split" 90 degrees: sin(180-x)=sin(x) > "Split" 45 degrees: sin(90-x)=cos(x) > "Split" 22.5 degrees: (sqrt(0.5)*(cos(x)-sin(x)) > Small angles requires less iterations for a given accuracy.
But, but, but, but,.... we work in radians!!!!!!!!!!!!!!!!!!!!!!!!!!!! Except maybe a carpenter! Jamie
On Mon, 18 Mar 2013 18:57:13 -0400, rickman <gnuarm@gmail.com> wrote:

>On 3/18/2013 2:10 PM, Jerry Avins wrote: >> On 3/17/2013 6:35 PM, rickman wrote: >>> On 3/17/2013 6:23 PM, langwadt@fonz.dk wrote: >>>> On Mar 17, 10:56 pm, rickman<gnu...@gmail.com> wrote: >>>>> On 3/16/2013 8:02 PM, langw...@fonz.dk wrote: >>>>> >>>>>> why not skip the lut and just do a full sine approximation >>>>> >>>>>> something like this, page 53-54 >>>>> >>>>>> http://www.emt.uni-linz.ac.at/education/Inhalte/pr_mderf/downloads/AD... >>>>>> >>>>>> >>>>> >>>>> I'm not sure this would be easier. The LUT an interpolation require a >>>>> reasonable amount of logic. This requires raising X to the 5th power >>>>> and five constant multiplies. My FPGA doesn't have multipliers and this >>>>> may be too much for the poor little chip. I suppose I could do some of >>>>> this with a LUT and linear interpolation... lol >>>>> >>>> >>>> I see, I assumed you had an MCU (or fpga) with multipliers >>>> >>>> considered CORDIC? >>> >>> I should learn that. I know it has been used to good effect in FPGAs. >>> Right now I am happy with the LUT, but I would like to learn more about >>> CORDIC. Any useful referrences? >> >> http://www.andraka.com/files/crdcsrvy.pdf should be a good start. Do you >> remember Ray Andraka? > >Yes, of course. I should have thought of that. I don't go to his site >often, but his stuff is always excellent. I may have even downloaded >this paper before. I took a look at the CORDIC once a few years ago and >didn't get too far. I'm happy with my current approach for the moment, >but I will dig into this more another time. > >I appreciate the link. Thanks Jerry.
If you just type "CORDIC FPGA" in Google it's the third link that comes up. Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
In comp.dsp Robert Baer <robertbaer@localnet.com> wrote:

(snip)
> I had used my "standard" 4.0 Acrobat; fails in that manner very > reliably. ver 7.0 works 100 percent; thanks.
For a long time (years) I was using 5.0 because it had some features that later ones didn't. I had 8.0 for the cases where that failed, but you can't run both at once. If you run another one, it just passes the file to the first one. Some time ago, I wrote a program to generate LZW compressed PDF from scanned bitmaps as PDF 1.0 files. (Among other things, only the usual 7 bit ASCII is allowed.) Later, I wrote on for JBIG2 compression, which I believe is 1.2 (That is, Acrobat 3.0.) But yes, many files require newer versions. -- glen
In comp.dsp Robert Baer <robertbaer@localnet.com> wrote:
>> (snip)
>>> Problem with that..could see only front and back cover.
> The basic approach given there is very good; use of puny 4 or 5 digit > tables is a major weakness: sqrt(2)/2 as 0.7071 is junk; CRC in the > squares, cubes and roots section gives sqrt(2) as 1.414214 (6 digits) > and sqrt(50) as 7.07168 (also 6 digits). > And if one needs more, use the Taylor series (for reasonably small > angles) as it converges fast (Nth odd power and Nth odd factorial). > --or, use the FPU in the computer to get SIN and COS at the same time!
But not so bad for 43 years ago! That was close to the beginning of MOS mask ROMs. It requires a 12V power supply, though the outputs are still TTL compatible, using both -12V and +5V power supplies.
> Reduction from 360 degrees helps: > "Split" 180 degrees: sin(-x)=-sin(x) > "Split" 90 degrees: sin(180-x)=sin(x) > "Split" 45 degrees: sin(90-x)=cos(x) > "Split" 22.5 degrees: (sqrt(0.5)*(cos(x)-sin(x)) > Small angles requires less iterations for a given accuracy.
-- glen
On 3/19/13 12:05 AM, glen herrmannsfeldt wrote:
...
> It requires a 12V > power supply, though the outputs are still TTL compatible, using > both -12V and +5V power supplies. >
my goodness we're old, glen. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
On Tue, 19 Mar 2013 00:18:35 -0400, robert bristow-johnson
<rbj@audioimagination.com> wrote:

>On 3/19/13 12:05 AM, glen herrmannsfeldt wrote: >... >> It requires a 12V >> power supply, though the outputs are still TTL compatible, using >> both -12V and +5V power supplies. >> > >my goodness we're old, glen.
I'm glad it's just you guys. ;) Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
On 3/19/13 12:21 AM, Eric Jacobsen wrote:
> On Tue, 19 Mar 2013 00:18:35 -0400, robert bristow-johnson > <rbj@audioimagination.com> wrote: > >> On 3/19/13 12:05 AM, glen herrmannsfeldt wrote: >> ... >>> It requires a 12V >>> power supply, though the outputs are still TTL compatible, using >>> both -12V and +5V power supplies. >>> >> >> my goodness we're old, glen. > > I'm glad it's just you guys. ;)
what was that EPROM? a 2716 or 2708 or something like that? -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
On 3/18/13 1:40 PM, dbd wrote:
> On Monday, March 18, 2013 8:51:48 AM UTC-7, robert bristow-johnson wrote: >> On 3/18/13 12:56 AM, dbd wrote: >> ... >>> For an approach with easier error estimation you could use the three table sine/cosine generator that implements the trig identities: >>> Sum formulas for sine and cosine >>> sin(w + deltaw) = sin(w) * cos(deltaw) + cos(w) * sin(deltaw) >>> cos(w + deltaw) = cos(w) * cos(deltaw) &#2013266070; sin(w) * sin(deltaw) >>> >>> The tables required are: >>> #1 one quadrant sin(w)/cos(w) table of 2^M entries >> i don't understand what this table is for at all? tan(w)? what do you >> do with it? > > That's one quadrant used for sine or cosine generation, the usual single lookup table. > >>> #2 sin(deltaw) table of 2^N entries >>> #3 cos(deltaw) table of 2^N entries >>> (#3 only if cosine is generated as well as sine) >> >> you need both tables, even if you only want to generate the sine, using >> this method. > > Right you are. It is a three table method for either sine or cosine.
i still don't get it. you only need a table or tables for the delta's. #2 and #3. i don't get what table #1 is about. you start out with sin(w)=0 and cos(w)=1 and pick the sin(deltaw) and cos(deltaw) outa 2 tables (or, if you're a teeny bit clever, a single table), and then have at it with the recursion equations above. i don't see a 3 table method. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
On 2013-03-18, Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
> > He indicated that his target is an FPGA that has no multiplies. This > is the exact environment where the CORDIC excels. LUTs can be > expensive in FPGAs depending on the vendor and the device.
yeah, you're right, I looked at the code on the wikipedia page and it was full of multiplies, but looking closer reveals they are all shifts and sign changes. -- &#9858;&#9859; 100% natural --- news://freenews.netfront.net/ - complaints: news@netfront.net ---
On Monday, March 18, 2013 9:44:51 PM UTC-7, robert bristow-johnson wrote:

sin(w + deltaw) = sin(w) * cos(deltaw) + cos(w) * sin(deltaw)
cos(w + deltaw) = cos(w) * cos(deltaw) &#2013266070; sin(w) * sin(deltaw)
by tables where:
 #1 one quadrant sin(w) or cos(w) table of 2^M entries
 #2 sin(deltaw) table of 2^N entries
 #3 cos(deltaw) table of 2^N entries

> i still don't get it. you only need a table or tables for the delta's. > #2 and #3. i don't get what table #1 is about.
#1 is the simple sine or cosine lookup table used to generate sin(w) or cos(w) for 2^M values of w in pi/2 (and extended to 2*pi by symmetries)
> > you start out with sin(w)=0 and cos(w)=1 and pick the sin(deltaw) and > cos(deltaw) outa 2 tables (or, if you're a teeny bit clever, a single > table), and then have at it with the recursion equations above.
There is no recursion in the equations. Tables #2 and #3 represent values of sin(deltaw) and cos(deltaw) for 2^N values of deltaw in the interval between the first two values of w that address table #1, say the interval from 0.0 to 0.5*pi*((2^N)-1)/(2^(M+N)).
> r b-j
Dale B. Dalrymple