iki.fi/o

Sine wave look-up table generation

Created by Olli Niemitalo on 2010-03-05, last modified 2012-08-11

2010-03-05

Here is a method for generating a sine look-up table in case you have little (a few kilobytes of) program memory. The idea goes like this: Let's say you have a sine wave lookup table of length 1024 with a 24-bit amplitude range. If you take the difference between successive samples, the range of the numbers is reduced. If you repeat the process a total of 3 times, the data will be dominated by the 3rd differential of the quantization noise and will have a range of -4 to 3, which can be conveniently stored in 3 bits only. This program below does the reverse, it generates the sine table from the 3-bit values, and also takes advantage of the symmetry properties of sine. So, instead of wasting 1024 program memory words for storing the original sine table, in the c-language implementation below, the compressed data takes only 35 24-bit words and the decompression code hopefully not too much more.

Here is a spreadsheet that illustrates the algorithm: sinetable.xls. The above implementation additionally embeds the seeds 0 and -3 in the magic data

7 Comments »

  1. Very nice!

    Comment by Rich Geldreich — 2012-05-20 @ 23:21

  2. Why are you using 24-bit words, when they’ll almost always be stored as 32-bit integers? Surely you could save another 25% by using the high byte of each word as well?

    Comment by Matthew — 2014-09-08 @ 12:55

  3. Matthew: I used a processor with 24-bit program memory words when I wrote this. Yeah someone could write a 32-bit version…

    Comment by Olli Niemitalo — 2014-09-08 @ 18:37

  4. I have another solution. You know how you can approximate the cosine/sine using polynomials? And how every time you halve the range your polynomial covers you multiply the precision by 2^(degree of the polynomial + 1)? So you got your x = [0, 2^32-1] input that represents the angle in turns, do the symmetry thing to turn it into a value in the first quadrant, take the top N bits, use them as the index for your array of polynomial coefficients, compute the polynomial by doing (((c2 * xl >> fmt) + c1) * xl >> fmt) + c0; (for quadratic approximations), change the sign depending on the input quadrant, and there’s your result!

    If you go with quadratic approximations and 32 segments then you only need a 384 byte pre-computed table (32 segments, 3 coefficients per segment, coefficients are 32 bits) and you get max error of 1/1,450,000 (-123 dB), and on a modern computer it runs in about 15 cycles (I don’t use symmetry so it goes even faster). You can save more memory using a smaller table (at the cost of a max of 8x precision for each 2x decrement) or using higher degree polynomials (at the expense of CPU time).

    Comment by Michel Rouzic — 2014-11-15 @ 18:34

  5. Michel, I believe your performance figures, they sound very plausible. Here’s more on using polynomials for sin cos generation: http://www.rossbencina.com/code/sinusoids

    Comment by Olli Niemitalo — 2015-02-20 @ 15:30

  6. Hello
    Can you advise how to make 2 channels , DAC , Sine wave look-up table for 14.kHz with resolution 1mV for STM32T100 ?

    Comment by ted — 2017-08-21 @ 05:37

  7. Hallo
    How I can use this table to produce 15 kHz sine wave ?

    Comment by ted — 2017-08-21 @ 15:25

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress