-------- In message <CAGJ4F+6Nvic=rouh7eozhklcdzibtormgu0ikj-sk6ixjw+...@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 p...@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. _______________________________________________ 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.
