rickman <gnuarm@gmail.com> wrote:>You aren't understanding. The value of cos(b) is ~1.0 at all values of >(b) (I said nothing about the lsb of b). This is determined by how many >bits are in (a) which determines the max value of (b).>Look at the diagram in my post 2/7/2017 at 9:46 PM EST.I'm not sure if this is tangential (not pun intended), but I would proceed as follows. sin(a+b), where a is N bits and b is M bits, is being approximated by sin(a) + cos(a)*b, with the sin() and cos() values coming from LUT's of width W1 and W2. Select W1 and W2 so that these quantizations add a negligible amount of noise relative to that contributed by the step-size of the LSB of b. (e.g. 6 dB or 10 dB less). The result y = sin(a) + cos(a)*b now exists as a fixed point value whose width W3 is a function of N, M, W2 and W3. But almost certainly it can be rounded to a smaller width, say W4, removing one or more MSB's, again without adding significant added noise. So... there is there some sort of factor-of-two relationship between some of these values N, M, W1, W2, W3 and W4, and if so, what is it? Steve
DDS LUT Size Calculation
Started by ●February 7, 2017
Reply by ●February 8, 20172017-02-08
Reply by ●February 9, 20172017-02-09
> >Arbitrary distinction. I can put any values into the table I wish. If >I floor the index I can use sin(index + 0.5) as my table entry or any >other value I choose to optimize the resulting calculations. Regardless>there will be a curve that is approximated by a straight line. That >straight line in the range is the important part. > >-- > >Rick CI don't see it as an arbitrary distinction, I see it as two different methods (among many possible ones). Either you are defining your line as the tangent line at a known point or you are using line segments that connect one known point to the next. Another way to say it is using a truncated Taylor's expansion or linear interpolation. You can arbitrarily define the offset of your index calculation any way you want and you can independently select your residual range to any values you want. However, if you want the most accurate results, you will use the Taylor's expansion with a residual range of -.5 to .5, and linear interpolation with a residual range of 0 to 1. Here's a numerical example with a 0 to 1 residual range: Deg Sine Interpolation Taylor ---- -------- ------------- ------------- 24.0 0.406737 0.406737 0.0 0.406737 0.0 24.1 0.408330 0.408325 0.6 0.408331 -0.1 24.2 0.409923 0.409913 1.0 0.409926 -0.2 24.3 0.411514 0.411501 1.3 0.411520 -0.6 24.4 0.413104 0.413089 1.5 0.413114 -1.0 24.5 0.414693 0.414677 1.6 0.414709 -1.6 24.6 0.416281 0.416266 1.5 0.416303 -2.2 24.7 0.417867 0.417854 1.3 0.417898 -3.1 24.8 0.419452 0.419442 1.0 0.419492 -4.0 24.9 0.421036 0.421030 0.6 0.421087 -5.1 25.0 0.422618 0.422618 0.0 0.422681 -6.3 The table lookup values are at 24 and 25 degrees. The second column is the error times 100000. It is clear from the data that you will be better off with a Taylor expansion and a residual range of -.5 to .5. If you are going to have a residual range of 0 to 1, whether your table goes on whole degrees (or whatever your scale) or on the halves (or first quarter, or whatever), interpolation is the better choice. I sure hope this effort is beneficial to some one. Ced --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●February 9, 20172017-02-09
On Thu, 09 Feb 2017 03:44:25 +0000, Steve Pope wrote:> rickman <gnuarm@gmail.com> wrote: > >>You aren't understanding. The value of cos(b) is ~1.0 at all values of >>(b) (I said nothing about the lsb of b). This is determined by how many >>bits are in (a) which determines the max value of (b). > >>Look at the diagram in my post 2/7/2017 at 9:46 PM EST. > > I'm not sure if this is tangential (not pun intended), but I would > proceed as follows. > > sin(a+b), where a is N bits and b is M bits, is being approximated by > sin(a) + cos(a)*b, with the sin() and cos() values coming from LUT's of > width W1 and W2. > > Select W1 and W2 so that these quantizations add a negligible amount of > noise relative to that contributed by the step-size of the LSB of b. > (e.g. 6 dB or 10 dB less). > > The result y = sin(a) + cos(a)*b now exists as a fixed point value whose > width W3 is a function of N, M, W2 and W3. But almost certainly it can > be rounded to a smaller width, say W4, removing one or more MSB's, again > without adding significant added noise. > > So... there is there some sort of factor-of-two relationship between > some of these values N, M, W1, W2, W3 and W4, and if so, what is it? > > SteveThe only mite that I can add that might be pertinent is that cos(theta) is approximately equal to 1 - theta^2/2 for small theta (0th & 2nd Taylor's series terms). This might make everything work the way Rick is describing. -- Tim Wescott Control systems, embedded software and circuit design I'm looking for work! See my website if you're interested http://www.wescottdesign.com
Reply by ●February 9, 20172017-02-09
On 2/9/2017 12:22 AM, Tim Wescott wrote:> On Thu, 09 Feb 2017 03:44:25 +0000, Steve Pope wrote: > >> rickman <gnuarm@gmail.com> wrote: >> >>> You aren't understanding. The value of cos(b) is ~1.0 at all values of >>> (b) (I said nothing about the lsb of b). This is determined by how many >>> bits are in (a) which determines the max value of (b). >> >>> Look at the diagram in my post 2/7/2017 at 9:46 PM EST. >> >> I'm not sure if this is tangential (not pun intended), but I would >> proceed as follows. >> >> sin(a+b), where a is N bits and b is M bits, is being approximated by >> sin(a) + cos(a)*b, with the sin() and cos() values coming from LUT's of >> width W1 and W2. >> >> Select W1 and W2 so that these quantizations add a negligible amount of >> noise relative to that contributed by the step-size of the LSB of b. >> (e.g. 6 dB or 10 dB less). >> >> The result y = sin(a) + cos(a)*b now exists as a fixed point value whose >> width W3 is a function of N, M, W2 and W3. But almost certainly it can >> be rounded to a smaller width, say W4, removing one or more MSB's, again >> without adding significant added noise. >> >> So... there is there some sort of factor-of-two relationship between >> some of these values N, M, W1, W2, W3 and W4, and if so, what is it? >> >> Steve > > The only mite that I can add that might be pertinent is that cos(theta) > is approximately equal to 1 - theta^2/2 for small theta (0th & 2nd > Taylor's series terms). This might make everything work the way Rick is > describing.That is *exactly* what is going on. I realized there are a number of interesting relationships that allow this to work. One is that the cos(a) is proportional to the slope of sin(a). So cos(a)*b is simply a linear interpolation using the slope of the curve at (a). Steve's analysis is very general, I think a bit more so than needed, but if it makes sense to others, great! BTW, on an off note, it's not even the middle of February and I just got bit by a damn mosquito!!! I'm near Washington DC where blizzards are not unusual at this time of year. -- Rick C
Reply by ●February 9, 20172017-02-09
>cos(a) is proportional to the slope of sin(a). So cos(a)*b is simply a >linear interpolation using the slope of the curve at (a). >Small pedantic correction: interpolation --> approximation A "you know what I meant" here would be true, but since we are having a technical discussion and can't make that assumption about everyone reading this I think it is important to use technical terms precisely. For those who may be interested, here is the source code for the data in my prior post with a quadratic Taylor value also included. In this particular example, the values you get from both the linear methods are accurate to about 17 bits, and the quadratic Taylor is accurate to about at least 23 bits. Ced #include <math.h> #include <stdio.h> //============================================================================ int main( int argCount, char *argValues[] ) { double base = 24 * M_PI / 180.0; double cap = 25 * M_PI / 180.0; double delta = cap - base; double y0 = sin( base ); double y1 = sin( cap ); double yp0 = cos( base ); double span = y1 - y0; for( int d = 240; d <= 250; d++ ) { double degree = d / 10.0; double radian = degree * M_PI / 180.0; double sine = sin( radian ); double diff = ( radian - base ); double frac = diff / delta; double interpolated = y0 + span * frac; double taylor1 = y0 + yp0 * diff; double taylor2 = y0 * ( 1.0 - diff * diff / 2.0 ) + yp0 * diff; double errori = 100000.0 * ( sine - interpolated ); double errort1 = 100000.0 * ( sine - taylor1 ); double errort2 = 100000.0 * ( sine - taylor2 ); printf( "%4.1f %8.6f %8.6f %4.1f %8.6f %4.1f %8.6f %8.5fn", degree, sine, interpolated, errori, taylor1, errort1, taylor2, errort2 ); } return 0; } //============================================================================ --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●February 9, 20172017-02-09
On Thu, 09 Feb 2017 09:27:26 -0600, Cedron wrote:>>cos(a) is proportional to the slope of sin(a). So cos(a)*b is simply a >>linear interpolation using the slope of the curve at (a). >> >> > Small pedantic correction: interpolation --> approximation > > A "you know what I meant" here would be true, but since we are having a > technical discussion and can't make that assumption about everyone > reading this I think it is important to use technical terms precisely.For that matter, if you make some statement and nine out of ten get it but the tenth is puzzled, then the tenth guy might have a problem. But if you make some statement and ten out of ten _don't_ get it -- well... -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
Reply by ●February 9, 20172017-02-09
On 2/9/2017 10:27 AM, Cedron wrote:>> cos(a) is proportional to the slope of sin(a). So cos(a)*b is simply a >> linear interpolation using the slope of the curve at (a). >> > > Small pedantic correction: interpolation --> approximationWhat exactly is your point about this?> A "you know what I meant" here would be true, but since we are having a > technical discussion and can't make that assumption about everyone reading > this I think it is important to use technical terms precisely. > > For those who may be interested, here is the source code for the data in > my prior post with a quadratic Taylor value also included. > > In this particular example, the values you get from both the linear > methods are accurate to about 17 bits, and the quadratic Taylor is > accurate to about at least 23 bits. > > Ced > > #include <math.h> > #include <stdio.h> > > //============================================================================ > int main( int argCount, char *argValues[] ) > { > double base = 24 * M_PI / 180.0; > double cap = 25 * M_PI / 180.0; > double delta = cap - base; > > double y0 = sin( base ); > double y1 = sin( cap ); > > double yp0 = cos( base ); > double span = y1 - y0; > > for( int d = 240; d <= 250; d++ ) > { > double degree = d / 10.0; > double radian = degree * M_PI / 180.0; > double sine = sin( radian ); > > double diff = ( radian - base ); > double frac = diff / delta; > > double interpolated = y0 + span * frac; > double taylor1 = y0 + yp0 * diff; > double taylor2 = y0 * ( 1.0 - diff * diff / 2.0 ) + yp0 * diff; > > double errori = 100000.0 * ( sine - interpolated ); > double errort1 = 100000.0 * ( sine - taylor1 ); > double errort2 = 100000.0 * ( sine - taylor2 ); > > printf( "%4.1f %8.6f %8.6f %4.1f %8.6f %4.1f %8.6f %8.5fn", > degree, sine, > interpolated, errori, > taylor1, errort1, > taylor2, errort2 ); > } > > return 0; > } > //============================================================================ > > > > --------------------------------------- > Posted through http://www.DSPRelated.com >-- Rick C
Reply by ●February 9, 20172017-02-09
>On 2/9/2017 10:27 AM, Cedron wrote: >>> cos(a) is proportional to the slope of sin(a). So cos(a)*b is simplya>>> linear interpolation using the slope of the curve at (a). >>> >> >> Small pedantic correction: interpolation --> approximation > >What exactly is your point about this? >Nice pun. The point is you are using one point and a slope to define a line segment. Linear interpolation means using two end points to define the line segment. https://en.wikipedia.org/wiki/Linear_interpolation When it comes to finding the values between your table entries you aren't interpolating, you are approximating. Ced --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●February 9, 20172017-02-09
On 2/9/2017 4:01 PM, Cedron wrote:>> On 2/9/2017 10:27 AM, Cedron wrote: >>>> cos(a) is proportional to the slope of sin(a). So cos(a)*b is simply > a >>>> linear interpolation using the slope of the curve at (a). >>>> >>> >>> Small pedantic correction: interpolation --> approximation >> >> What exactly is your point about this? >> > > Nice pun. > > The point is you are using one point and a slope to define a line segment. > Linear interpolation means using two end points to define the line > segment. > > https://en.wikipedia.org/wiki/Linear_interpolation > > When it comes to finding the values between your table entries you aren't > interpolating, you are approximating.Linear interpolation uses two points connected by a straight line. There are many forms of interpolation. https://en.wikipedia.org/wiki/Interpolation -- Rick C
Reply by ●February 10, 20172017-02-10
>On 2/9/2017 4:01 PM, Cedron wrote: >>> On 2/9/2017 10:27 AM, Cedron wrote: >>>>> cos(a) is proportional to the slope of sin(a). So cos(a)*b issimply>> a >>>>> linear interpolation using the slope of the curve at (a). >>>>> >>>> >>>> Small pedantic correction: interpolation --> approximation >>> >>> What exactly is your point about this? >>> >> >> Nice pun. >> >> The point is you are using one point and a slope to define a line >segment. >> Linear interpolation means using two end points to define the line >> segment. >> >> https://en.wikipedia.org/wiki/Linear_interpolation >> >> When it comes to finding the values between your table entries youaren't>> interpolating, you are approximating. > >Linear interpolation uses two points connected by a straight line. >There are many forms of interpolation. > >https://en.wikipedia.org/wiki/Interpolation > >-- > >Rick CRick, Honestly, I don't understand what you aren't understanding. I sure hope you are one in ten and not ten in ten. I am also considering the possibility that you are just toying with me. Oh well. Strictly speaking, you are interpolating, even interpolating linearly, but not are not doing a linear interpolation. In the numerical example I provided, "Linear Interpolation" corresponds to the column labeled "Interpolation" and "interpolation using the slope of the curve at (a)" corresponds to the column labeled "Taylor". They are not the same, nor can they be made the same by shifting where the sampled points are taken. I misspoke earlier about interpolating with a polynomial and matching the endpoints and their first derivatives. Generally, this requires a third degree equation and not a second degree one as I stated. Since you intend on having two lookup tables, one for the value, one for the slope, the optimal solution in terms of a least squares fit of a uniformly distributed input variable is to do linear regression of your function on each interval. This will only improve your accuracy by about a factor of two, or one bit's worth. Now, I'm dropping the mic and walking away. Ced --------------------------------------- Posted through http://www.DSPRelated.com
