[time-nuts] Linear or quadractic fit algorithms for small microcontrollers?

[Tim Shoppa]

Thanks to Magnus and Ulrich for their high-powered math, but I was playing
around with "Double Exponential Smoothing" and it seems to work well for my
application almost zero storage requirements.

Below I toss around constants like alpha and beta - I use them in the same
sense as shown here:
https://en.wikipedia.org/wiki/Exponential_smoothing#Double_exponential_smoothing

You don't actually need floating point at all if you choose your smoothing
constants appropriately. For example the next smoothed value can be
calculated as

s = (1-alpha)*s + alpha*x

If you choose alpha as say 1/128, then you can do multiplications using 7
right shifts (127/128) or 7-right-shifts-and-subtract (127/128).

And to reject outliers, I just predict the next value. If the value sampled
is too far off, I throw it out and use the predicted next value instead,
just the same way as if no data was available at all.

Using alpha as 1/128, and beta as 1/1024, it seems to work well with the
ES100 WWVB BPSK "tracking mode" data I've acquired. In tracking mode I get
one data point every minute. Alpha of 1/128 works out to a roughly 2-hour
exponential smoothing for the time, and beta of 1/1024 works out to a
nearly one-day exponential smoothing for the drift of the microprocessor's
crystal oscillator. The 2-hour exponential smoothing of the time reduces
the raw +/-100 ms jitter of the ES100 by better than a factor of ten. And
the roughly one day smoothing of the drift seems about right too (although
maybe I should go shorter or longer to avoid diurnal pumping).

Getting rid of the outliers turns out to be important when using the ES100
in tracking mode. It turns out that in my noisy household environment here
on the east coast, every few hundred attempts, the ES100 tracking attempt
will return as a claimed success BUT it is off by way more than 100ms,
often by an integer number of seconds (say 1-3 seconds).

Tim N3QE

On Thu, Dec 27, 2018 at 7:24 PM Magnus Danielson <magnus at rubidium.dyndns.org>
wrote:

> Hi Tim,
>
> On 12/26/18 4:53 PM, Tim Shoppa wrote:
> > I know we discussed this many years ago, probably in context of the HP
> > Smartclock patent, but I've forgotten all the details.
> >
> > Say I have a circular buffer of up to several dozen time and offset
> values.
> > The intent was to sample at regular intervals but some samples are
> missing.
> > Are there simple microcontroller-oriented algorithms - integer math, no
> big
> > scratch arrays - for doing linear or quadractic fits and maybe even
> > excluding some outliers?
> >
> > Instead of using arrays for circular buffers, if there are algorithms
> that
> > "age out" the older samples so that they get lesser and lesser weight,
> and
> > also give linear and/or quadractic fit coefficients, that's even neater.
> > For example exponential smoothing.
>
> You could either do linear regression or the type of least square
> fitting that I did, which did away with the large matrixes altogether.
>
> Here is one variant of the article:
> https://arxiv.org/abs/1604.01004
>
> The benefit is that you only need to build the sums C and D, and using
> knowledge about how many N samples, you can do both phase and frequency
> estimation from the same values. This should work very well in a small
> microcontroller.
>
> What is not covered in the above article is linear drift, but it can be
> approximated using two frequency readings. I've developed an extension
> for linear drift, it's just not published yet.
>
> The HP SmartClock used least-square estimation, but as far as I have
> been able to reverse-engineer, it was not very fancy but more classical
> matrix stuff.
>
> Cheers,
> Magnus
>
> _______________________________________________
> time-nuts mailing list -- time-nuts at lists.febo.com
> To unsubscribe, go to
> http://lists.febo.com/mailman/listinfo/time-nuts_lists.febo.com
> and follow the instructions there.
>