bob@evoria.net said:

That's just rounding up at an important place.  It's probably a good idea,
but doesn't cover the area I was trying to point out.  Let me try again...

Suppose you are doing:
x_avg = x_avg + (x - x_avg) * a_avg;

For exponential smoothing, a_avg will be a fraction.  Let's pick a_avg to be
1/8.  That's a right shift by 3 bits.  I don't think there is anything magic
about shifting, but that makes a particular case easy to spot and discuss.

Suppose x_avg is 0 and x has been 0 for a while.  Everything is stable.  Now change x to 2.  (x - x_avg) is 2, the shift kicks it off the edge, so x_avg doesn't change.  (It went 2 bits off, so your round up doesn't catch it.)  The response to small steps is to ignore them.

If you have noisy data, things probably work out OK.  If you need to process low level (very) low frequency changes (which seems desirable for a GPSDO) you probably want some fractional bits.  For me, the easy way to do that is to use
y = x * k
Let's use k = 16, a 4 bit left shift.
For the same step of x=2, y= 32, (y - y_avg) is 32, shifted right by 3 that's 4, so y_avg is 4.

I'm sure this is all business-as-usual for the people who write control loops in small CPUs using fixed point arithmethic.  Of course, you have to worry about shifting too far left (overflow) and things like that.

If you have enough cycles, you can use floating point.  :)

--
These are my opinions.  I hate spam.

Hal says: "For exponential smoothing, a_avg will be a fraction.  Let's pick a_avg to be 1/8.  That's a right shift by 3 bits.  I don't think there is anything magic about shifting, but that makes a particular case easy to spot and discuss."

Hi Hal,

Yeah, I've been sitting here manually running some sample data and I haven't been happy with my efforts so far.  I think I'll just stay with what I know for now: moving averages.  I've got a number of places I can reduce memory usage when I run a bit shorter, so I think it'll work out.  And I suspect I'm being far too conservative; i.e. averaging way too long  If not, maybe there will be a good gain value that will be convenient to code the exponential average.

Thanks for the help,

Bob

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

Daniel

Em 13/03/2014 00:55, 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.

Bob

On Wed, Mar 12, 2014 at 9:13 PM, Daniel Mendes dmendesf@gmail.com wrote:

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.  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.

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.

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.

This is worth reading
PIDforDummies.html http://www.csimn.com/CSI_pages/PIDforDummies.html

--

Chris Albertson
Redondo Beach, California

Em 13/03/2014 01:35, Bob Stewart escreveu:

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.

Daniel

On 3/12/14 10:06 PM, Chris Albertson wrote:

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

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.

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.

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.

Hi Jim,

Thanks for your thoughts.  Perhaps there are a few things that I know about my particular system that have been discounted.  I have mentioned them in passing, but haven't collected them coherently for this thread.  It's an 8-bit PIC, thus floating point calculations have to be "improvised", and memory is limited to 4096 total instructions with 512 bytes of variable space.  I'm using a nav receiver at the moment (no sawtooth correction), and the 1PPS is pretty noisy.  The hardware is a fixed quantity, which includes a 10-bit PWM dithered to 14 bits.  There is a voltage divider on the EFC to limit the range, and a thermistor for thermal correction.  Think of it as a contest or a challenge.  The only prize is success.

The noisy 1PPS has been a big concern, and the reason for the moving average/low-pass filter.  I have considered using a slotted-disk instead, or at least a smaller MA with a slotted-disk.  The OCXO has shown itself to be extremely stable in both phase and frequency.  Without eliminating the noise from the 1PPS, the OCXO would be needlessly moved around thus passing that noise through.  Given the stability of the OCXO, I don't think that being 32 seconds behind (two 16 second moving averages at the moment) creates a problem.  I do actually have a usable integrator designed for a  PI system, but I'm trying to avoid using it.  My preference is a state machine implementation.

My approach to this is along the lines of

1. Warmup
2. Check and adjust the frequency "close enough"
3. If there is a frequency adjustment, decide when to (re)enable phase control
4. Compare the phase angle to the setpoint to discover which way to herd the phase
5. Use the smoothed slope and distance from setpoint to control the gain of any change applied to the DAC
6. Adjust for temperature change
7. Rinse and repeat from 2.

Perhaps this is so close to PI that it makes no difference that I'm not using a transliteration of Wescott's code?  I really do not relish the idea of implementing floating point operations in 8-bit unsigned characters on someone else's control code on this PIC if I can get it to work properly my way.

Bob

On 12 Mar, 2014, at 23:08 , Hal Murray hmurray@megapathdsl.net wrote:

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.

Dennis Ferguson

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