Using correctly the quarter sine-wave symmetry in a basic DDS

Hi,
In a very basic DDS, the first method used to reduce the ROM size is to
only store one quarter of the sine-wave. Although this sounds very obvious,
I cannot figure out how to do it without storing 1/4th + 1 location in the
ROM.

For example, say we start with a 10-bit address for the full table (1024
locations). Ideally, we want to use the top two bits to determine which
quadrant we are into, and the bottom 8 bits as the address in a
256-location ROM (not a 257 location ROM!!).

However, when implementing this, it really seems like I need to store the
value at pi/4 (256 in the example above), which makes the ROM 257 location!


Any idea?

Thanks!

Dave

gretzteam <gretzteam@yahoo.com> wrote:

> In a very basic DDS, the first method used to reduce the ROM size is to
> only store one quarter of the sine-wave. Although this sounds very obvious,
> I cannot figure out how to do it without storing 1/4th + 1 location in the
> ROM.
 
> For example, say we start with a 10-bit address for the full table (1024
> locations). Ideally, we want to use the top two bits to determine which
> quadrant we are into, and the bottom 8 bits as the address in a
> 256-location ROM (not a 257 location ROM!!).

Well, it is 1.0 which probably doesn't fit anyway.  You know
it is 1.0 (or 0.99999) so just put that in.
 
> However, when implementing this, it really seems like I need to store the
> value at pi/4 (256 in the example above), which makes the ROM 257 location!

-- glen

On Tue, 17 Nov 2009 18:12:34 -0600, gretzteam wrote:

> Hi,
> In a very basic DDS, the first method used to reduce the ROM size is to
> only store one quarter of the sine-wave. Although this sounds very
> obvious, I cannot figure out how to do it without storing 1/4th + 1
> location in the ROM.
> 
> For example, say we start with a 10-bit address for the full table (1024
> locations). Ideally, we want to use the top two bits to determine which
> quadrant we are into, and the bottom 8 bits as the address in a
> 256-location ROM (not a 257 location ROM!!).
> 
> However, when implementing this, it really seems like I need to store
> the value at pi/4 (256 in the example above), which makes the ROM 257
> location!
> 
> 
> Any idea?
> 
> Thanks!
> 
> Dave

Do like Glen said, and hard-code one location.

Or store values at half-locations, i.e. pi * (1/2048, 3/2048 ... 
2047/2048).  Not only does this now wrap nicer, but you never have to 
deal with 1 -- just 0.9999997.

-- 
www.wescottdesign.com

>Do like Glen said, and hard-code one location.
>
>Or store values at half-locations, i.e. pi * (1/2048, 3/2048 ... 
>2047/2048).  Not only does this now wrap nicer, but you never have to 
>deal with 1 -- just 0.9999997.

Got it! 
I guess this has a bunch of advantages! 
1) Not storing 1.0 is a good one from the ROM width perspective.
2) The ROM address can be generated with a simple one-complement (inverse
all bits) when we detect the 2nd and 4th quadrant! Which also save the
extra address bit I needed!

Now it all sounds obvious, but I litterally spent the whole day on
this...should have posted earlier!

Thanks a lot! 

Dave 

On 11/17/2009 6:41 PM, gretzteam wrote:
>> Do like Glen said, and hard-code one location.
>>
>> Or store values at half-locations, i.e. pi * (1/2048, 3/2048 ...
>> 2047/2048).  Not only does this now wrap nicer, but you never have to
>> deal with 1 -- just 0.9999997.
>
> Got it!
> I guess this has a bunch of advantages!
> 1) Not storing 1.0 is a good one from the ROM width perspective.
> 2) The ROM address can be generated with a simple one-complement (inverse
> all bits) when we detect the 2nd and 4th quadrant! Which also save the
> extra address bit I needed!
>
> Now it all sounds obvious, but I litterally spent the whole day on
> this...should have posted earlier!
>
> Thanks a lot!
>
> Dave

Sounds like a day well spent to me.   Getting those insights into 
implementation issues can help a lot in building efficient systems.

-- 
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

>On 11/17/2009 6:41 PM, gretzteam wrote:
>>> Do like Glen said, and hard-code one location.
>>>
>>> Or store values at half-locations, i.e. pi * (1/2048, 3/2048 ...
>>> 2047/2048).  Not only does this now wrap nicer, but you never have to
>>> deal with 1 -- just 0.9999997.
>>
>> Got it!
>> I guess this has a bunch of advantages!
>> 1) Not storing 1.0 is a good one from the ROM width perspective.
>> 2) The ROM address can be generated with a simple one-complement
(inverse
>> all bits) when we detect the 2nd and 4th quadrant! Which also save the
>> extra address bit I needed!
>>
>> Now it all sounds obvious, but I litterally spent the whole day on
>> this...should have posted earlier!
>>
>> Thanks a lot!
>>
>> Dave
>
>Sounds like a day well spent to me.   Getting those insights into 
>implementation issues can help a lot in building efficient systems.

If you show any inside about efficiency these days, people think you are
old. :-)

Steve

Tim Wescott <tim@seemywebsite.com> wrote:
(snip)
 
> Do like Glen said, and hard-code one location.
 
> Or store values at half-locations, i.e. pi * (1/2048, 3/2048 ... 
> 2047/2048).  Not only does this now wrap nicer, but you never have to 
> deal with 1 -- just 0.9999997.

That sounds like the best way for use with phase accumulators.

Somewhere I still have the National Semiconductor data book
with a ROM sine lookup table.   That was in the NMOS days, so
it was pretty small, but I am pretty sure it didn't use the
half location method.  There were additional ROMS to do linear
interpolation to get more bits.

-- glen

>Tim Wescott <tim@seemywebsite.com> wrote:
>(snip)
> 
>> Do like Glen said, and hard-code one location.
> 
>> Or store values at half-locations, i.e. pi * (1/2048, 3/2048 ... 
>> 2047/2048).  Not only does this now wrap nicer, but you never have to 
>> deal with 1 -- just 0.9999997.
>
>That sounds like the best way for use with phase accumulators.
>
>Somewhere I still have the National Semiconductor data book
>with a ROM sine lookup table.   That was in the NMOS days, so
>it was pretty small, but I am pretty sure it didn't use the
>half location method.  There were additional ROMS to do linear
>interpolation to get more bits.
>
>-- glen
>

Hi Glen,
I think the 1/4 sine wave trick comes pretty much for free (one mux for
which the select line is already available, and negating all bits of a
bus). My understanding is that it should always be used. 

Then, more complicated/costly compression algorithms can be implemented
(Sunderland, Nicholas...). Then one can start dithering or noise shaping
the NCO. It seems to me that the performance trade-off for each of those
methods is not obvious and highly depends on the application and technology
where the DDS is to be implemented.

I think those two papers are really helpful! 

http://www.echelonembedded.com/dsphwlab/files/DDS_Lab_PDFs/DDS1.pdf
http://www.echelonembedded.com/dsphwlab/files/DDS_Lab_PDFs/DDS2.pdf

Let me know if there is the newest and greatest compression method that
I'm not aware of!

Thanks,

On 11/17/2009 11:26 PM, steveu wrote:
>> On 11/17/2009 6:41 PM, gretzteam wrote:
>>>> Do like Glen said, and hard-code one location.
>>>>
>>>> Or store values at half-locations, i.e. pi * (1/2048, 3/2048 ...
>>>> 2047/2048).  Not only does this now wrap nicer, but you never have to
>>>> deal with 1 -- just 0.9999997.
>>> Got it!
>>> I guess this has a bunch of advantages!
>>> 1) Not storing 1.0 is a good one from the ROM width perspective.
>>> 2) The ROM address can be generated with a simple one-complement
> (inverse
>>> all bits) when we detect the 2nd and 4th quadrant! Which also save the
>>> extra address bit I needed!
>>>
>>> Now it all sounds obvious, but I litterally spent the whole day on
>>> this...should have posted earlier!
>>>
>>> Thanks a lot!
>>>
>>> Dave
>> Sounds like a day well spent to me.   Getting those insights into
>> implementation issues can help a lot in building efficient systems.
>
> If you show any inside about efficiency these days, people think you are
> old. :-)
>
> Steve

Unfortunately that's true.  Resources like memory and gates are so cheap 
there's little motivation to be efficient.

Apparently a recent technology blog somewhere was decrying the horrors 
that one of the new high-capability smart phones only has 256 megabytes 
of FLASH memory for user application storage, and clearly that was not 
enough.  I subsequently had to explain to somebody that the only reason 
so many apps need GBytes of disk space is that there's little motivation 
to be efficient so the tools and programmers just waste it.  Development 
cost and time to market are far more important than memory cost.

Fortunately the apps for the handhelds are still, apparently, at least 
for now, reasonably efficient and typically only take up a few MBytes or 
so.  Certainly when handheld devices have cheap gigabytes available the 
apps will bloat to fill it up.

-- 
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

On Nov 18, 11:18&#4294967295;am, Eric Jacobsen <eric.jacob...@ieee.org> wrote:
>
> Apparently a recent technology blog somewhere was decrying the horrors
> that one of the new high-capability smart phones only has 256 megabytes
> of FLASH memory for user application storage, and clearly that was not
> enough. &#4294967295;

And yet, they limit the text message storage to 150 messages on my
phone!  Maybe they *do* need more than 256 MB of storage... ;^)

Rick