this *should* be a relatively simple issue, but i am confused
On 3/16/13 6:30 PM, rickman wrote:
I've been studying an approach to implementing a lookup table (LUT) to
implement a sine function. The two msbs of the phase define the
quadrant. I have decided that an 8 bit address for a single quadrant is
sufficient with an 18 bit output.
10 bits or 1024 points. since you're doing linear interpolation, add one
more, copy the zeroth point x[0] to the last x[1024] so you don't have
to do any modulo (by ANDing with (1023-1) on the address of the second
point. (probably not necessary for hardware implementation.)
x[n] = sin( (pi/512)*n ) for 0 <= n <= 1024
So you are suggesting a table with 2^n+1 entries? Not such a great idea
in some apps, like hardware.
i think about hardware as a technology, not so much an app. i think that
apps can have either hardware or software realizations.
Ok, semantics. What word should I use instead of "app"?
in *software* when using a LUT *and* linear interpolation for sinusoid
generation, you are interpolating between x[n] and x[n+1] where n is
from the upper bits of the word that comes outa the phase accumulator:
#define PHASE_BITS 10
#define PHASE_MASK 0x001FFFFF // 2^21 - 1
#define FRAC_BITS 11
#define FRAC_MASK 0x000007FF // 2^11 - 1
#define ROUNDING_OFFSET 0x000400
long phase, phase_increment, int_part, frac_part;
long y, x[1025];
...
phase = phase + phase_increment;
phase = phase & PHASE_MASK;
int_part = phase >> FRAC_BITS;
frac_part = phase & FRAC_MASK;
y = x[int_part];
y = y + (((x[int_part+1]-y)*frac_part + ROUNDING_OFFSET)>>FRAC_BITS);
now if the lookup table is 1025 long with the last point a copy of the
first (that is x[1024] = x[0]), then you need not mask int_part+1.
x[int_part+1] always exists.
Also, why 10 bit
address for a 1024 element table?
uh, because 2^10 = 1024?
that came from your numbers: 8-bit address for a single quadrant and
there are 4 quadrants, 2 bits for the quadrant.
No, that didn't come from my numbers, well, not exactly. You took my
numbers and turned it into a full 360 degree table. I was asking where
you got 10 bits, not why a 1024 table needs 10 bits. Actually, in your
case it is a 1025 table needing 11 bits.
why wouldn't you use those extra bits in the linear interpolation if
they are part of the phase word? not doing so makes no sense to me at
all. if you have more bits of precision in the fractional part of the phase
Because that is extra logic and extra work. Not only that, it is beyond
the capabilities of the DAC I am using. As it is, the linear interp
will generate bits that extend below what is implied by the resolution
of the inputs. I may use them or I may lop them off.
not in software. i realize that in hardware and you're worried about
real estate, you might want only one quadrant in ROM, but in software
you would have an entire cycle of the waveform (plus one repeated point
at the end for the linear interpolation).
and if you *don't* have the size constraint in your hardware target and
you can implement a 1024 point LUT as easily as a 256 point LUT, then
why not? so you don't have to fiddle with reflecting the single quadrant
around a couple of different ways.
OK, thanks for the insight.
i read this over a couple times and cannot grok it quite. need to be
more explicit (mathematically, or with C or pseudocode) with what your
operations are.
It is simple, the LUT gives values for each point in the table, precise
to the resolution of the output. The sin function between these points
varies from close to linear to close to quadratic. If you just
interpolate between the "exact" points, you have an error that is
*always* negative anywhere except the end points of the segments. So it
is better to bias the end points to center the linear approximation
somewhere in the middle of the real curve. Of course, this has to be
tempered by the resolution of your LUT output.
If you really want to see my work it is all in a spreadsheet at the
moment. I can send it to you or I can copy some of the formulas here.
My "optimization" is not nearly optimal. But it is an improvement over
doing nothing I believe and is not so hard. I may drop it when I go to
VHDL as it is iterative and may be a PITA to code in a function.
not with defining the points of the table. you do that in MATLAB or in C
or something. your hardware gets its LUT spec from something you create
with a math program.
I don't think I'll do that. I'll most likely code it in VHDL. Why use
yet another tool to generate the FPGA code? BTW, VHDL can do pretty
much anything other tools can do. I simulated analog components in may
last design... which is what I am doing this for. My sig gen won't work
on the right range and so I'm making a sig gen out of a module I build.
BTW, to do the calculation you describe above, it has to take into
account that the end points have to be truncated to finite resolution.
Without that it is just minimizing noise to a certain level only to have
it randomly upset. It may turn out that converting from real to finite
resolution by rounding is not optimal for such a function.
i'm just thinking that if you were using LUT to generate a sinusoid that
is a *signal* (not some parameter that you use to calculate other
stuff), then i think you want to minimize the mean square error (which
is the power of the noise relative to the power of the sinusoid). so the
LUT values might not be exactly the same as the sine function evaluated
at those points.
I don't get your point really. The LUT values will deviate from the sin
function because of one thing, the resolution of the output. The sin
value calculated will deviate because of three things, input resolution,
output resolution and the accuracy of the sin generation.
I get what you are saying about the mean square error. How would that
impact the LUT values? Are you saying to bias them to minimize the
error over the entire signal? Yes, that is what I am talking about, but
I don't want to have to calculate the mean square error over the full
sine wave. Curently that's two million points. I've upped my design
parameters to a 512 entry table and and 10 bit interpolation.
what are "lines"? not quite following you.
Segments. I picture the linear approximations between end points as
lines. When you improve one line segment by moving one end point you
also impact the adjacent line segment. I have graphed these line
segments in the spread sheet and looked at a lot of them. I think the
"optimizations" make some improvement, but I'm not sure it is terribly
significant. It turns out once you have a 512 entry table, the sin
function between the end points is pretty close to linear or the
deviation from linear is in the "noise" for an 18 bit output. For
example, between LUT(511) and LUT(512) is just a step of 1. How
quadratic can that be?
if you want to define your LUT to minimize the mean square error,
assuming linear interpolation between LUT entries, that can be a little
complicated, but i don't think harder than what i remember doing in grad
school. want me to show you? you get a big system of linear equations to
get the points. if you want to minimize the maximum error (again
assuming linear interpolation), then it's that fitting a straight line
to that little snippet of quadratic curve bit that i mentioned.
God! Thanks but no thanks. Is this really practical to solve for the
entire curve? Remember that all points affect other points, possibly
more than just the adjacent points. If point A changes point A+1, then
it may also affect point A+2, etc. What would be more useful would be
to have an idea of just how much *more* improvement can be found.
sin(t) = t + ... small terms when t is small
cos(t) = 1 - (t^2)/2 + ... small terms when t is small
but they beat you by a few hundred years.
Blame my parents!
