I just wrote a program to calculate the size of the LUT required to generate the coarse sin/cos values (a in the following equation) to use the trig identity sin(a+b) = sin(a)cos(b) + cos(a)sin(b), meaning the max value of b is sufficiently small that cos(b) is 1.0 to within one lsb of the output sine word. The size of a and b (meaning the number of bits) always turns out to be half of the total. Obviously there is something guiding this. But I don't know of any trig rules that would make it so. -- Rick C
DDS LUT Size Calculation
Started by ●February 7, 2017
Reply by ●February 7, 20172017-02-07
On Tue, 07 Feb 2017 07:09:24 -0500, rickman wrote:> I just wrote a program to calculate the size of the LUT required to > generate the coarse sin/cos values (a in the following equation) to use > the trig identity sin(a+b) = sin(a)cos(b) + cos(a)sin(b), meaning the > max value of b is sufficiently small that cos(b) is 1.0 to within one > lsb of the output sine word. > > The size of a and b (meaning the number of bits) always turns out to be > half of the total. Obviously there is something guiding this. But I > don't know of any trig rules that would make it so.So you're saying that the size of a and b is always equal? Interesting. No, I have no clue of why that is, but it's probably buried in the trig someplace. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
Reply by ●February 7, 20172017-02-07
On Tue, 07 Feb 2017 12:53:27 -0600, Tim Wescott wrote:> On Tue, 07 Feb 2017 07:09:24 -0500, rickman wrote: > >> I just wrote a program to calculate the size of the LUT required to >> generate the coarse sin/cos values (a in the following equation) to use >> the trig identity sin(a+b) = sin(a)cos(b) + cos(a)sin(b), meaning the >> max value of b is sufficiently small that cos(b) is 1.0 to within one >> lsb of the output sine word. >> >> The size of a and b (meaning the number of bits) always turns out to be >> half of the total. Obviously there is something guiding this. But I >> don't know of any trig rules that would make it so. > > So you're saying that the size of a and b is always equal? > > Interesting. No, I have no clue of why that is, but it's probably > buried in the trig someplace.Not enough information. What criteria are you using to choose the size of a? Because your criteria on b just sets the weight of your overall LSB -- without any other rules, you could choose the dividing line between a and b arbitrarily. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
Reply by ●February 7, 20172017-02-07
On Tuesday, February 7, 2017 at 4:09:36 AM UTC-8, rickman wrote:>...> > The size of a and b (meaning the number of bits) always turns out to be > half of the total. Obviously there is something guiding this. But I > don't know of any trig rules that would make it so. >... There must be further unstated requirements or assumptions because, in general, the size of the lookup table addresses and the value of the lsb of the looked up data are independent. You might get different results from 16 bit fixed point and 64 bit float data. Dale B. Dalrymple
Reply by ●February 7, 20172017-02-07
dbd <d.dalrymple@sbcglobal.net> wrote:>There must be further unstated requirements or assumptions because, in >general, the size of the lookup table addresses and the value of the lsb >of the looked up data are independent. You might get different results >from 16 bit fixed point and 64 bit float data.I agree, I am curious as to what exactly is being observed here. Steve
Reply by ●February 7, 20172017-02-07
On 2/7/2017 2:34 PM, Tim Wescott wrote:> On Tue, 07 Feb 2017 12:53:27 -0600, Tim Wescott wrote: > >> On Tue, 07 Feb 2017 07:09:24 -0500, rickman wrote: >> >>> I just wrote a program to calculate the size of the LUT required to >>> generate the coarse sin/cos values (a in the following equation) to use >>> the trig identity sin(a+b) = sin(a)cos(b) + cos(a)sin(b), meaning the >>> max value of b is sufficiently small that cos(b) is 1.0 to within one >>> lsb of the output sine word. >>> >>> The size of a and b (meaning the number of bits) always turns out to be >>> half of the total. Obviously there is something guiding this. But I >>> don't know of any trig rules that would make it so. >> >> So you're saying that the size of a and b is always equal? >> >> Interesting. No, I have no clue of why that is, but it's probably >> buried in the trig someplace. > > Not enough information. What criteria are you using to choose the size > of a? Because your criteria on b just sets the weight of your overall LSB > -- without any other rules, you could choose the dividing line between a > and b arbitrarily.I gave the criteria above. "cos(b) is 1.0 to within one lsb of the output sine word." I doubt anyone here can read Forth, but here is the program I wrote to do the calculations. For even values of output bits the result was always half that number of bits with the resulting accuracy just a bit worse than the requirement, e.g. for a 32 bit phase step word and 32 bit output word it says to use 16 msbs to drive the LUT address lines yielding 31.697 bits of accuracy. For odd word sizes the LUT address is the larger half, e.g. 16 bits for a 31 bit word. The program is very simple. Each word (separated by spaces) does something with the data currently on the stack and leave a result on the stack (all implicit rather than explicit as in other languages). A word is defined by : (colon) and ; (semicolon) with the name immediately after the colon. Thing in parentheses () are comments as well as anything between \ and the end of the line. Everything else is either a number or a word (subroutine). Inside of definitions (remember : and ;?) words are strung together to define the word (subroutine) rather than executed. Outside of definitions they are directly executed. This code defines the words 2^F F2LOG OutBitCountToOutRes OutResToPhaseStep LUTResolutionToBits LUTAddrBitsToOutRes and puts them all together with SinLUTSize Each word can be tested interactively from the command line by typing parameters to push on the stack then invoking the word and printing the result like... 3e0 2^F F. What you will see on the console is... 3e0 2^F F. 8.00000 ok Isn't that easy? F. prints a floating point number. Many of the predefined words are easy to figure out. FSWAP swaps the top two floating point numbers on the stack. FACOS is floating point arccos(). Floating point literals are entered with an exponent, 1e0 for example. The decimal point is not enough in most Forth tools. \ calculates the number of bits needed to address the LUT \ in a DDS for a given number of output bits \ To preserve the assumption that COS(b) is ~= 1.0 the minimum step of \ COS in the LUT should be no more than one lsb. \ FPI/2 is not ANS standard, you may need to add it to your system. MARKER SINE : 2^F ( F: f1 -- f2 ) \ Raise 2 to a power, floating point 2.0e0 FLN F* FEXP ; : F2LOG ( F: f1 -- f2 ) \ Log base 2 FLN 2.0e0 FLN F/ ; \ Turn output bit count into output resolution : OutBitCountToOutRes ( n -- ) ( F: -- f ) S>F 2^F 1.0e0 FSWAP F/ ; \ Output resolution to phase angle step in 90 deg LUT : OutResToPhaseStep ( -- ) ( F: f1 -- f2 ) 1.0e0 FSWAP F- FACOS FPI/2 F/ ; \ LUT input resolution to number of bits : LUTResolutionToBits ( -- n ) ( F: f -- ) 1.0e0 FSWAP F/ F2LOG 0.5e0 F+ F>S ; \ round to integer \ Address bit count to output resolution : LUTAddrBitsToOutRes ( n -- ) ( F: -- f ) S>F 2^F 1.0e0 FSWAP F/ FPI/2 F* FCOS 1.0e0 FSWAP F- ; : SinLUTSize ( n1 -- n2 ) \ n1 is number of bits out, n2 is LUT address bits PRECISION SWAP 11 SET-PRECISION DUP OutBitCountToOutRes CR ." Required resolution " . ." bits or " FDUP F. OutResToPhaseStep CR ." Target phase angle step size in LUT " FDUP F. LUTResolutionToBits CR ." Number of bits required in LUT address " DUP . DUP LUTAddrBitsToOutRes CR ." Resolution with " DUP . ." bit address " FDUP F. 1.0e0 FSWAP F/ CR ." Accuracy of 1 part in " FDUP F. ." or " 5 SET-PRECISION F2LOG F. ." bits" SWAP SET-PRECISION ; 32 SinLUTSize Result on running this.... FLOAD 'C:\Arius\Projects\Forth\SinLUTSize.f' Required resolution 32 bits or .00000000023 Target phase angle step size in LUT .00001373774 Number of bits required in LUT address 16 Resolution with 16 bit address .00000000029 Accuracy of 1 part in 3481368790.7 or 31.697 bits ok. . 16 ok 18 SinLUTSize Required resolution 18 bits or .00000381470 Target phase angle step size in LUT .00175843086 Number of bits required in LUT address 9 Resolution with 9 bit address .00000470619 Accuracy of 1 part in 212486.08959 or 17.697 bits ok. 2 SinLUTSize Required resolution 2 bits or .25000000000 Target phase angle step size in LUT .46010691233 Number of bits required in LUT address 1 Resolution with 1 bit address .29289321881 Accuracy of 1 part in 3.4142135624 or 1.7716 bits ok.. . . 1 9 ok 50 SinLUTSize . Required resolution 50 bits or .00000000000 Target phase angle step size in LUT .00000002683 Number of bits required in LUT address 25 Resolution with 25 bit address .00000000000 Accuracy of 1 part in 900719925470000. or 49.678 bits25 ok You just completed Forth 101 -- Rick C
Reply by ●February 7, 20172017-02-07
On 2/7/2017 2:48 PM, dbd wrote:> On Tuesday, February 7, 2017 at 4:09:36 AM UTC-8, rickman wrote: >> > .... >> >> The size of a and b (meaning the number of bits) always turns out to be >> half of the total. Obviously there is something guiding this. But I >> don't know of any trig rules that would make it so. >> > .... > > There must be further unstated requirements or assumptions because, in general, the size of the lookup table addresses and the value of the lsb of the looked up data are independent. You might get different results from 16 bit fixed point and 64 bit float data.Not sure what you are thinking here. The sine table is used to obtain sin(a) and cos(a) in sin(a)cos(b) + cos(a)sin(b). The number of address bits into the lookup table are chosen so that the remaining bits, (b) make cos(b) adequately small so it does not limit the accuracy of the calculations. The other requirement is that So then the calculation is sin(a) + cos(a)*b. Both sin(a) and cos(a) come from a lookup table. sin(a) is full bit width. cos(a) only needs to be half width as the value of b will always have the top half filled with zeros. cos(a) can't come from the same table as sin(a) because b is a fraction of 90 degrees and needs a multiplier to turn it into radians as required by the equation. Easiest way is to add the product (pi/2)cos(a) to the lookup table extending the width by half. This reminds me that there is one thing I neglected to account for, the sign bit. The output word range is twice the range of the the LUT output because the output is bipolar ± while the LUT only outputs positive values which must be negated. So the result of 31.xxx bits is actually 32.xxx bits once the sign bit is added giving more than the required amount of accuracy. :) Does the curve of the sine function approach x^2 at 90 degrees? -- Rick C
Reply by ●February 7, 20172017-02-07
On 2/7/2017 3:42 PM, Steve Pope wrote:> dbd <d.dalrymple@sbcglobal.net> wrote: > >> There must be further unstated requirements or assumptions because, in >> general, the size of the lookup table addresses and the value of the lsb >> of the looked up data are independent. You might get different results >>from 16 bit fixed point and 64 bit float data. > > I agree, I am curious as to what exactly is being observed here.What part don't you understand? -- Rick C
Reply by ●February 7, 20172017-02-07
>I just wrote a program to calculate the size of the LUT required to >generate the coarse sin/cos values (a in the following equation) to use >the trig identity sin(a+b) = sin(a)cos(b) + cos(a)sin(b), meaning the >max value of b is sufficiently small that cos(b) is 1.0 to within one >lsb of the output sine word. > >The size of a and b (meaning the number of bits) always turns out to be >half of the total. Obviously there is something guiding this. But I >don't know of any trig rules that would make it so. > >-- > >Rick CHi Rick, I'm going to take a stab here. The Taylor's series for cosine is cos( b ) ~=~ 1 - b^2/2 + b^4/4! - ... So if b is very small then 1 - cos( b ) ~=~ b^2/2 b takes roughly half a many bits as b^2. The division by two will alter the bit count by one. Hope this is even close and it helps. Ced --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●February 7, 20172017-02-07
On 2/7/2017 7:09 AM, rickman wrote:> I just wrote a program to calculate the size of the LUT required to > generate the coarse sin/cos values (a in the following equation) to use > the trig identity sin(a+b) = sin(a)cos(b) + cos(a)sin(b), meaning the > max value of b is sufficiently small that cos(b) is 1.0 to within one > lsb of the output sine word. > > The size of a and b (meaning the number of bits) always turns out to be > half of the total. Obviously there is something guiding this. But I > don't know of any trig rules that would make it so.Just to clarify, here is a drawing of the circuit... +------+ | | sin(a) |\ a | |----------------------->| \ | | | \ sin(x) +---->| LUT | pi/2 * | | N bits | | | cos(a) +------+ | + |----/---> Phase | | |--------->| | | | ----->>--+ | | | | | / Word | +------+ | MULT |----->| / x | b | | : |/ +---------------------->| | : +------+ cos(a)sin(b) When I looked at the resulting accuracy possible with different address widths, I realize it is changing by the square. Does the shape of cos(x) approach a quadratic in the region of x = 0 degrees? Hmmm... I think I can see that. cos and sin are related as derivatives. sin(x) is nearly linear at 0 degrees, so cos(x) would have to approach x^2 at 0 degrees. -- Rick C
