[time-nuts] Receiving the MSF time signal on cheap radio modules

[Poul-Henning Kamp]

--------
In message <CAGJ4F+6Nvic=RoUH7EozhKLCDziBTorMGu0iKj-sK6iXjw+zsQ at mail.gmail.com>
, "Deirdre O'Byrne" writes:

>I've been trying to see if I could design a decoding algorithm that
>would be more noise-tolerant than the algorithms I've seen out in
>the wild.

You can: I baptised it "the blame algoritm".

The trick is not to try to accept pulses as valid but to try to
throw out pulses which are impossible.

Imagine you have a 120 second long shift-register, and you feed
your received pulses into it.

Then try brute force, for every one of the newest 60 positions if
that can be the start of a minute or not, by testing all the
constraints you can think of, and there are surprisingly many.

Some are obvious, the bits encoding the hour cannot contain "39",
but that is a remarkable weak filter that seldom kicks in.

A much stronger filter is that the bits encoding the hour must be
the same as in the previous minute *unless* minutes were 59 in the
previous minute *and* zero in this minute.

If you count it up, that is a strong and very peculiar relationship
on all the hour-bits and all the minutes-bits and if even one single
of them are wrong, you can definitively discard that theory for the
start of the minute.

A similar thing holds for the date bits, the time in the
previous minute must be 23:59:59 and in this 00:00:00 for
there to be any difference between the dates, and even
then, only a small number of possible changes in the date
bits are valid.

If you look in http://phk.freebsd.dk/phkrel/NTPns.20080902.tgz
you will find a file called dcf77_blame.c with my code,
here is a couple of the simpler tests:

        /* LSB of minutes must be different from previous minute */
        j = ip->shiftprev[(offset + 21) % 60];
        if (j * ip->shiftreg[(offset + 21) % 60] > 0)
                FAIL((why, " 0"));

        /*
         * If the LSB of minutes was '1' in previous minute
         * the next higher bit must have changed, if it was
         * a '0' it must not.
         */
        if (j *
            ip->shiftreg[(offset + 22) % 60] *
            ip->shiftprev[(offset + 22) % 60] > 0)
                FAIL((why, " 1"));

When using this algorithm, missing pulses is almost a
non-issue up to around 40% of them missing, and even
in an enviroment like that, it is not uncommon to see
the algorithm lock on to the minute in about 34 seconds
and know the full time in less than 3 minutes.

If you make your pulse width discriminator *really* selective,
which you might as well, you can "blacklist" disproved
minute positions for the next many minutes as the
risk of a '1' and '0' being confused is close to zero.

That will get you minute lock, even with 70%-90% missing
pulses, in a matter of minutes if you use a longer
shift register.

I did a parallel prototype for MSF, but I didn't need it
so I never completed it, not sure I have it around any
more.

I should really write an article about that code...

Poul-Henning

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
phk at FreeBSD.ORG         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.