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.
/* Multiplierless 1024-sample, 24-bit sine table generator
*
* by Olli Niemitalo in 2010-03-07.
* This work is placed in the public domain.
*/
#include <stdio.h>;
/* Sine table with one extra sample to enable interpolation
*
* Sine with amplitude -0x800000 .. 0x800000 was rounded to
* nearest integer and truncated to -0x800000 .. 0x7fffff.
* int data type must be at least 24-bit.
*/
int sineTable[1025];
void generateTable() {
int i, j, k;
const int magic[33] = {
0x691864, 0x622299, 0x2CB61A, 0x461622,
0x62165A, 0x85965A, 0x0D3459, 0x65B10C,
0x50B2D2, 0x4622D9, 0x88C45B, 0x461828,
0x6616CC, 0x6CC2DA, 0x512543, 0x65B69A,
0x6D98CC, 0x4DB50B, 0x86350C, 0x7136A2,
0x6A974B, 0x6D531B, 0x70D514, 0x4EA714,
0x5156A4, 0x393A9D, 0x714A6C, 0x755555,
0x5246EB, 0x916556, 0x7245CD, 0xB4F3CE,
0x6DBC7A
};
k = 0;
for (i = 0; i < 33; i++) {
for (j = 0; j < 24; j += 3) {
sineTable[k++] = ((magic[i] >> j) & 7) - 4;
}
}
sineTable[1] = 51472;
for (i = 3; i > 0; i--) {
for (j = i; j <= 256; j++) {
k = sineTable[j - 1];
sineTable[j] = k + sineTable[j];
sineTable[513-j] = k;
sineTable[511+j] = -k;
sineTable[1025-j] = -k;
}
}
sineTable[768] = -0x800000;
}
int main() {
int i;
generateTable();
/* Printout */
for (i = 0; i < 1025; i++) {
printf("%d\t%d\n", i, sineTable[i]);
}
return 0;
} |
Here is a spreadsheet that illustrates the algorithm: sinetable.xls. The above implementation additionally embeds the seeds 0 and -3 in the magic data
Very nice!
Comment by Rich Geldreich — 2012-05-20 @ 23:21