[gpsd-dev] Time autonomy

[Eric S. Raymond]

This is a proposed way to handle the era-detection problem that is
intended to make it possible for GPSD to be time-autonomous - that is, 
not have to rely on the host system clock or NTP time.

This is me engineering for the SBC-a-thousand-miles-at-sea case.
Besides, if we're going to take the role of feeding NTP seriously,
it's circular to rely on NTP.

For purposes of this dicussion, WEEK is 7 * 24 * 60 *60 and
ROLLOVER_PERIOD is your GPS's era length in seconds.  It is presently
1024 * WEEK (10 bit week counter); your device may optionally tell you
it's 8192 * WEEK (13-bit week counter).

1. Compile the century and GPS week of the current build time into
   GPSD as two constants, BUILD_CENTURY and BUILD_WEEK. Compile in the
   date of the last rollover as BUILD_EPOCH. Compile in the leapsecond
   offset as BUILD_LEAPOFFSET. With these, initialize four variables:
   saved_century, saved_week, saved_epoch, and leap_offset.

2. Update leap_offset as the device makes it available.  For purposes
   of later discussion, the "leap residual" at any given time is the
   unknown difference between the current actual leap offset and our
   saved leap_offset.  The difference will be > 0 if the device's
   almanac is stale.  We will say that time is "nearly correct" if
   the time error is bounded by the leap residual.

3. When an NMEA device gives you a UTC time/date t, apply the saved
   century if it has only a two-digit year.  Then compute from that
   time as follows

   week = (t + leap_offset - saved_epoch) / WEEK
   tow = (t + leap_offset - saved_epoch) % WEEK

   A binary device will give you (week, tow) directly.

3. You now have a (week, tow) pair. If week < saved_week, increment
   saved_epoch by ROLLOVER_PERIOD, then copy week into saved_week.

4. Now report GPS time as :

        t = saved_epoch + week * WEEK + tow - leap_offset.

   Save the computed century in saved_century.

This will yield nearly correct time provided the device is on
continuously on from a date during its build era (e.g. before the
first rollover after BUILD_EPOCH), and gets at least one valid fix
per week.

To upgrade so the algorithm can handle shutdown periods, add two
steps:

1a. If /var/run/gps-epoch exists, initialize saved_epoch from it ar
startup time.

5. If you had to increment saved_epoch in step 3, write it
/var/run/gps-epoch at shutdown time.

Note that you are guaranteed nearly correct time for one full era from
BUILD_EPOCH (a minimum of 19 years) even if you cannot write
/var/run/gps-epoch.  If you can write it, you get nearly correct time
forever (or until various quantities overflow, anyway).

There is one odd case: if NMEA device time is not correctly
leap-second compensated (e.g. because the device's almanac is stale),
there is a very window equal to the leap second residual, just before
midnight of a new rollover period, during which it will compute (week,
tow) incorrectly.

There are some obvious complications when dealing with 13-bit week
counters.

Please criticize and correct.
-- 
                <a href="http://www.catb.org/~esr/";>Eric S. Raymond</a>

I have never made but one prayer to God, a very short one: "O Lord,
make my enemies ridiculous." And God granted it.
        --Voltaire