Re: [time-nuts] PLL Math Question
You don't really shift so much as just change the way you think about it.
The way to think about it is not that you have "16th" but that you have the
"binary point" force places over. It works just like a decimal point. If
you multiply two numbers each that has four places to the right of the
point you have now eight places to the right. You can shift it or not. If
you use 64 bit "longs" you sand up not having to shift so much because
those can cary up to about 32 binary places.
On Thu, Mar 13, 2014 at 12:10 PM, Bob Stewart bob@evoria.net wrote:
Dennis,
I just realized that I could do the math in sixteenths. So, for 7/16ths
multiply by 7 before shifting(i.e. dividing) and rounding. That would
probably give enough granularity. I'll have to think about it. It does
open new doors.
thanks,
Bob
From: Dennis Ferguson dennis.c.ferguson@gmail.com
To: Discussion of precise time and frequency measurement <
Cc: Hal Murray hmurray@megapathdsl.net
Sent: Thursday, March 13, 2014 1:58 PM
Subject: Re: [time-nuts] PLL Math Question
Note that you can't do fixed-point computations exactly the same way
you would do it in floating point, you often need to rearrange the
equations
a bit. You can usually find a rearrangement which provides equivalent
results, however. Let's define an extra variable, x_sum, where
x_avg = x_sum * a_avg;
The equation above can then be rewritten in terms of x_sum, i.e.
x_sum = x_sum * (1 - a_avg) + x;
With an a_avg of 1/8 you'll instead be multiplying x_sum by 7, shifting
it right 3 bits (you might want to round before the shift) and adding x.
The new value of x_avg can be computed from the new value of x_sum with a
shift (you might want to round that too), or you could pretend that x_sum
is a fixed-point number with the decimal point 3 bits from the right.
In either case x_sum carries enough bits that you don't lose precision.
time-nuts mailing list -- time-nuts@febo.com
To unsubscribe, go to
https://www.febo.com/cgi-bin/mailman/listinfo/time-nuts
and follow the instructions there.
--
Chris Albertson
Redondo Beach, California
OK, gotcha. But, this is in assembler, and anything wider than 3 bytes becomes tedious. Also, anything larger than 3 bytes starts using a lot of space in a hurry. Three byte fields allow me to use 256ths for gain and take the result directly from the two high order bytes without any shifting. And as I mentioned to Hal in a separate post: when I hand-coded the exponential averager the results were actually good. I was forgetting to convert to decimal to compare values to the decimal run. For example: 0x60 doesn't look like 0.375 until you convert to decimal and divide by 256.
This has been most informative and certainly gives me more options.
Bob
From: Chris Albertson albertson.chris@gmail.com
To: Bob Stewart bob@evoria.net; Discussion of precise time and frequency measurement time-nuts@febo.com
Sent: Thursday, March 13, 2014 5:42 PM
Subject: Re: [time-nuts] PLL Math Question
You don't really shift so much as just change the way you think about it. The way to think about it is not that you have "16th" but that you have the "binary point" force places over. It works just like a decimal point. If you multiply two numbers each that has four places to the right of the point you have now eight places to the right. You can shift it or not. If you use 64 bit "longs" you sand up not having to shift so much because those can cary up to about 32 binary places.
On Thu, Mar 13, 2014 at 12:10 PM, Bob Stewart bob@evoria.net wrote:
Dennis,
I just realized that I could do the math in sixteenths. So, for 7/16ths multiply by 7 before shifting(i.e. dividing) and rounding. That would probably give enough granularity. I'll have to think about it. It does open new doors.
thanks,
Bob
From: Dennis Ferguson dennis.c.ferguson@gmail.com
To: Discussion of precise time and frequency measurement time-nuts@febo.com
Cc: Hal Murray hmurray@megapathdsl.net
Sent: Thursday, March 13, 2014 1:58 PM
Subject: Re: [time-nuts] PLL Math Question
Note that you can't do fixed-point computations exactly the same way
you would do it in floating point, you often need to rearrange the equations
a bit. You can usually find a rearrangement which provides equivalent
results, however. Let's define an extra variable, x_sum, where
x_avg = x_sum * a_avg;
The equation above can then be rewritten in terms of x_sum, i.e.
x_sum = x_sum * (1 - a_avg) + x;
With an a_avg of 1/8 you'll instead be multiplying x_sum by 7, shifting
it right 3 bits (you might want to round before the shift) and adding x.
The new value of x_avg can be computed from the new value of x_sum with a
shift (you might want to round that too), or you could pretend that x_sum
is a fixed-point number with the decimal point 3 bits from the right.
In either case x_sum carries enough bits that you don't lose precision.
time-nuts mailing list -- time-nuts@febo.com
To unsubscribe, go to https://www.febo.com/cgi-bin/mailman/listinfo/time-nuts
and follow the instructions there.
--
Chris Albertson
Redondo Beach, California
Hi
Either grab a math pack (there are several for the PIC) or go to C.
Timing at the Time Nuts level is about precision. We need lots of digits past the binary point :)
Bob
On Mar 13, 2014, at 7:19 PM, Bob Stewart bob@evoria.net wrote:
OK, gotcha. But, this is in assembler, and anything wider than 3 bytes becomes tedious. Also, anything larger than 3 bytes starts using a lot of space in a hurry. Three byte fields allow me to use 256ths for gain and take the result directly from the two high order bytes without any shifting. And as I mentioned to Hal in a separate post: when I hand-coded the exponential averager the results were actually good. I was forgetting to convert to decimal to compare values to the decimal run. For example: 0x60 doesn't look like 0.375 until you convert to decimal and divide by 256.
This has been most informative and certainly gives me more options.
Bob
From: Chris Albertson albertson.chris@gmail.com
To: Bob Stewart bob@evoria.net; Discussion of precise time and frequency measurement time-nuts@febo.com
Sent: Thursday, March 13, 2014 5:42 PM
Subject: Re: [time-nuts] PLL Math Question
You don't really shift so much as just change the way you think about it. The way to think about it is not that you have "16th" but that you have the "binary point" force places over. It works just like a decimal point. If you multiply two numbers each that has four places to the right of the point you have now eight places to the right. You can shift it or not. If you use 64 bit "longs" you sand up not having to shift so much because those can cary up to about 32 binary places.
On Thu, Mar 13, 2014 at 12:10 PM, Bob Stewart bob@evoria.net wrote:
Dennis,
I just realized that I could do the math in sixteenths. So, for 7/16ths multiply by 7 before shifting(i.e. dividing) and rounding. That would probably give enough granularity. I'll have to think about it. It does open new doors.
thanks,
Bob
From: Dennis Ferguson dennis.c.ferguson@gmail.com
To: Discussion of precise time and frequency measurement time-nuts@febo.com
Cc: Hal Murray hmurray@megapathdsl.net
Sent: Thursday, March 13, 2014 1:58 PM
Subject: Re: [time-nuts] PLL Math Question
Note that you can't do fixed-point computations exactly the same way
you would do it in floating point, you often need to rearrange the equations
a bit. You can usually find a rearrangement which provides equivalent
results, however. Let's define an extra variable, x_sum, where
x_avg = x_sum * a_avg;
The equation above can then be rewritten in terms of x_sum, i.e.
x_sum = x_sum * (1 - a_avg) + x;
With an a_avg of 1/8 you'll instead be multiplying x_sum by 7, shifting
it right 3 bits (you might want to round before the shift) and adding x.
The new value of x_avg can be computed from the new value of x_sum with a
shift (you might want to round that too), or you could pretend that x_sum
is a fixed-point number with the decimal point 3 bits from the right.
In either case x_sum carries enough bits that you don't lose precision.
time-nuts mailing list -- time-nuts@febo.com
To unsubscribe, go to https://www.febo.com/cgi-bin/mailman/listinfo/time-nuts
and follow the instructions there.
--
Chris Albertson
Redondo Beach, California
time-nuts mailing list -- time-nuts@febo.com
To unsubscribe, go to https://www.febo.com/cgi-bin/mailman/listinfo/time-nuts
and follow the instructions there.
On 13/03/14 07:35, Daniel Mendes wrote:
Em 13/03/2014 01:35, Bob Stewart escreveu:
Hi Daniel,
re: FIR vs IIR
I'm not a DSP professional, though I do have an old Smiths, and I've
read some of it. So, could you give me some idea what the FIR vs IIR
question means on a practical level for this application? I can see
that the MA is effective and easy to code, but takes up memory space I
eventually may not have. Likewise, I can see that the EA is hard to
code for the general case, but takes up little memory. Any thoughts
would be appreciated unless this is straying too far from time-nuts
territory.
FIR = Finite Impulse Response
It means that if you enter an impulse into your filter after some time
the response completely vanishes. Let´s have an example:
your filter has coefficients 0.25 ; 0.25 ; 0.25 ; 0.25 (a moving
average of length 4)
instead we could define this filter by the difference equation:
y[n] = 0.25x[n] + 0.25x[n-1] + 0.25x[n-2] + 0.25x[n-3] (notice that
Y[n] can be computed by looking only at present and past values of x)
your data is 0; 0; 1; 0; 0; 0; 0 ...... (there´s an impulse of
amplitude 1 at n= 2)
your output will be:
0; 0; 0.25; 0.25; 0.25; 0.25; 0; 0; 0; ..... (this is the convolution
between the coefficients and the input data)
after 4 samples (the length of the filter) your output completely
vanishes. This means that all FIR filters are BIBO stable (BIBO =
bounded input, bounded output... if you enter numbers not infinite in
the filter the output never diverges)
IIR = infinite Impulse Response
It means that if you enter an impulse into your filter the response
never settle down again (but it can converge). Let´s have an example:
your filter cannot be described by coefficients anymore because it has
infinite response, so we need a difference equation. Let´s use the one
provided before for the exponential smoothing with a_avg = 1/8:
x_avg = x_avg + (x - x_avg) * 1/8;
this means:
y[n] = y[n-1] + (x[n] - y[n-1]) * 1/8
y[n] = y[n-1] - 1/8y[n-1] + 1/8x[n]
y[n] = 7/8y[n-1] + 1/8x[n]
you can see why this is different from the other filter: now the output
is function not only from the present and past inputs, but also from the
past output(s).
Lets try the same input as before:
your data is 0; 0; 1; 0; 0; 0; 0 ...... (there´s an impulse of
amplitude 1 at t= 2)
your output will be:
y[0] = 0 = 7/8y[-1] + 1/8x[0] (i´m assuming that y[-1] = 0.. and x[0]
is zero)
y[1] = 0 = 7/8y[0] + 1/8x[1]
y[2] = 1/8 = 7/8y[1] + 1/8x[2] (x[2] = 1)
y[3] = 7/64 = 7/8y[2] + 1/8x[3] (x[3] = 0) = 0.109
y[4] = 49/512 = 7/8y[3] + 1/8x[4] (x[4] = 0) = 0.095
y[5] = 343/4096 = 7/8y[4] + 1/8x[5] (x[5] = 0) = 0.084
You can see that without truncation this will never go to zero again.
Usually you can get more attenuation with a IIR filter having the same
computational complexity than a FIR filter but you need to take care
about stability and truncation. Well, i´ll just copy here the relevant
part from wikipedia about advantages and disadvantages:
Advantages and disadvantages
The main advantage digital IIR filters have over FIR filters is their
efficiency in implementation, in order to meet a specification in terms
of passband, stopband, ripple, and/or roll-off. Such a set of
specifications can be accomplished with a lower order (/Q/ in the above
formulae) IIR filter than would be required for an FIR filter meeting
the same requirements. If implemented in a signal processor, this
implies a correspondingly fewer number of calculations per time step;
the computational savings is often of a rather large factor.
On the other hand, FIR filters can be easier to design, for instance, to
match a particular frequency response requirement. This is particularly
true when the requirement is not one of the usual cases (high-pass,
low-pass, notch, etc.) which have been studied and optimized for analog
filters. Also FIR filters can be easily made to be linear phase
http://en.wikipedia.org/wiki/Linear_phase (constant group delay
http://en.wikipedia.org/wiki/Group_delay vs frequency), a property
that is not easily met using IIR filters and then only as an
approximation (for instance with the Bessel filter
http://en.wikipedia.org/wiki/Bessel_filter). Another issue regarding
digital IIR filters is the potential for limit cycle
http://en.wikipedia.org/wiki/Limit_cycle behavior when idle, due to
the feedback system in conjunction with quantization.
You need to understand that the PI loop already is a IIR filter in
itself, and you need to understand what the averager you add inside that
loop does to the loop properties. Generic discussions on IIR vs FIR does
not cut it. If you do a FIR averager then you need to consider what the
poles and zeros (yes it has both) of that do inside the PI-loop.
Cheers,
Magnus
On 13/03/14 13:57, Jim Lux wrote:
On 3/12/14 10:06 PM, Chris Albertson wrote:
On Wed, Mar 12, 2014 at 9:13 PM, Daniel Mendes dmendesf@gmail.com
wrote:
This is a FIR x IIR question...
moving average = FIR filter with all N coeficients equalling 1/N
exponential average = using a simple rule to make an IIR filter
Isn't his "moving average" just a convolution of the data with a box car
function? That treats the last N samples equally and is likely not
optimal. I think why he wants is a low pass filter.
A moving average (or rectangular impulse response) is a low pass
filter. The frequency response is of the general sin(x)/x sort of
shape, and it has deep nulls, which can be convenient (imagine a moving
average covering 1/60th of a second, in the US.. it would have strong
nulls at the line frequency and harmonics)
This method is like
the hockey player who skates to where to puck was about 5 seconds
ago. It
is not the best way to play the game. He will in fact NEVER get to the
puck if the puck is moving he is domed to chase it forever.. Same here
you will never get there.
That distinction is different than the filter IIR vs FIR thing. Filters
are causal, and the output always lags the input in time. if you want
to predict where you're going to be you need a different kind of model
or system design. Something like a predictor corrector, for instance.
But if you have a long time constant on the control loop you have in
effect
the kind of "averaging" you want, one that tosses out erratic noisy data.
A PID controller uses only three memory locations and is likely the best
solution.
PID is popular, having been copiously analyzed and used over the past
century. It's also easy to implement in analog circuitry.
ANd, there's long experience in how to empirically adjust the gain
knobs, for some kinds of controlled plant.
However, I don't know that the simplicity justifies its use in modern
digital implementations: very, very few applications are so processor or
gate limited that they couldn't use something with better performance.
If you are controlling a physical system with dynamics that are well
suited to a PID (e.g. a motor speed control) then yes, it's the way to
go. But if PIDs were so wonderful, then there wouldn't be all sorts of
"auto-tuning" PIDs out there (which basically complexify things by
trying to estimate the actual plant model function, and then optimize
the P,I, and D coefficients).
PID controllers don't do well when there's a priori side knowledge
available. For instance, imagine a thermostat kind of application where
you are controlling the temperature of an object outside in the sun. You
could try to control the temperature solely by measuring the temp of the
thing controlled, and comparing it against the setpoint (a classic PID
sort of single variable loop). Odds are, however, that if you had
information about the outside air temperature and solar loading, you
could hold the temperature a lot more tightly and smoothly, because you
could use the side information (temp and sun) to anticipate the
heating/cooling demands.
This is particularly the case where the controlled thing has long time
lags, but low inertia/mass.
Extending a PI or PID loop to incorporate aiding signals isn't hard. In
fact that's what happens in GPS receivers. Properly done aiding signals
will reduce the phase errors to do loop stress and allow for even
tighter bandwidth.
Each GPS channel in a receiver contains a carrier and a code loop. The
carrier loop aids the code loop in frequency tracking. It is also common
to have both a frequency and phase detector and then aid the normal
phase-driven PI loop with a frequency detector hint.
A nice aspect about frequency aiding is that it has a strong pull-in
property when the input signal and loop is far away, and that's when the
phase-lock-in is very weak. As the pull-in progresses, the frequency
aiding gets weaker while the phase locked becomes stronger, as the
Bessel polynom gets higher for the beat frequency. Eventually the
phase-locking takes over in strength and the frequency aiding
essentially dismisses itself. This is a great example of how a classical
loop can be extended without getting into very esoteric systems.
We have to define "best". I'd define it as "the error integrated over
time
is minimum". I think PiD gets you that and it is also easy to program
and
uses very little memory. Just three values (1) the error, (2) the
total of
all errors you've seen (in a perfect world this is zero because the
positive and negative errors cancel) and (3) the rate of change in the
error (is it getting bigger of smaller and how quickly?) Multiply
each of
those numbers by a constant and that is the correction to the output
value.
It's maybe 6 or 10 lines of C code. The "magic" is finding the
right
values for the constants.
And that magic is sometimes a lot of work.
And practical PID applications also need things like integrator reset to
prevent wind-up issues, and clamps, or variable gains.
PID, or PI, is, as you say, easy to code, and often a good first start,
if you have a system with fast response, and lots of gain to work with.
It's like building circuits with an opamp: big gain bandwidth product
makes it more like an ideal amplifier where the feedback components
completely determine the circuit behavior. Put in hysteresis, or a time
delay, and things start to not look so wonderful.
There is a limit to how high the bandwidth-delay product can be for a
certain damping. This is covered in literature and I actually used one
of those articles in an article I wrote. Adding deep moving averagers
behaves like a delay, so there is a limit on how long moving averager
you can have in your loop before it destabilizes that loop.
I would guestimate that the effective delay of a moving average is half
it's length, and the product it has with the bandwidth of the loop may
not be too high, which means that there is a practical limit to how
"deep" it can filter. The exponential average filter has a practical
limit too, which is kind of similar and a fairly simple rule of thumb
makes sure it doesn't move the dominant pole-pair too much. On the other
hand, following that rule of thumb, you can have multiple filters or for
that matter higher grade filters without too much interference to how
dimensioning is done and stability is maintained.
There is also the higher integration variants.
The traditional PI/PID loop allows for a whole variant of extensions if
you just play around a little.
Cheers,
Magnus
On 14/03/14 00:39, Bob Camp wrote:
Hi
Either grab a math pack (there are several for the PIC) or go to C.
Timing at the Time Nuts level is about precision. We need lots of digits past the binary point :)
Indeed. Throwing bits at the problems is relatively cheap today.
Besides, you don't process it that often, so you can afford to let a few
cycles bring you design margin.
Remember, you want the internal resolution to have many bits below the
single-shot resolution. Lack of bits in frequency resolution tends to
get you doing bang-bang regulations to approximate the frequency. With
sufficient resolution other noise sources will assist to average out
that quantization step. The bang-bang regulations naturally give you an
idle-frequency, and both frequency and amplitude depends on the
quantization step.
Cheers,
Magnus