Monday, November 29, 2010

Some Garmin GPS receivers output wrong coordinates in NMEA sentence

Executive Summary

Some Garmin GPS receivers get a simple mathematical conversion wrong that causes them output incorrect coordinates in their NMEA sentences. The only NMEA data streams I looked at are those of the Garmin GPS 16 and Garmin GPS 18 OEM, and those suffer from the software bug described below.
Example: walking slowly and logging one coordinate pair per second as output in the NMEA sentences of the GPS 16, the following records were obtained.
29 March 2009
Latitude (N)   Longitude (W)
7122.0816      15631.9960
7122.0815      15631.9978
7122.0810      15632.9996
7122.0806      15632.0016
7122.0804      15632.0025

And another example, walking even slower.
12 May 2010
Latitude (N)  Longitude (W)
7122.2581     15630.9982
7122.2583     15630.9989
7122.2584     15630.9991
7122.2585     15630.9990
7122.2585     15630.9989
7122.2587     15630.9991
7122.2590     15631.9996
7122.2590     15631.9996
7122.2591     15630.9995
7122.2593     15631.9999
7122.2595     15631.0000
7122.2596     15631.0002


GPS receivers calculate their position relative to a set of satellites in Euclidean space, i.e. the same coordinate space we are familiar with since high school. I think Garmin receivers do a nice job at that, in particular considering their price. In my limited experience, all Garmin GPS receivers seem to do this correctly. While presumably all Garmin receivers display and store correct coordinates, at least some receivers occasionally (but systematically) output wrong coordinates through their serial interface. If you do not connect anything to your Garmin that receives GPS coordinates in real time then you can stop reading here and continue enjoying your purchase. Have fun.

For those of use who do connect stuff to our Garmin receivers, we can sometimes choose between two data formats: the proprietary Garmin binary format, and the standard (ASCII) NMEA sentences. This blurb applies to data transferred from the GPS receiver in NMEA sentences, only. From what I can tell, the binary data stream is correct.

Some Garmin GPS receivers are able to output data through a serial (and recently USB) interface. The non-proprietary format used follows NMEA 0183 specifications. In this standard, data are transmitted as plain ASCII text. Coordinates are represented in a somewhat peculiar format as DDMM.FFFF, where D is decimal degrees, M is minutes, and F is fractional minutes. For example, consider 71.36 degrees. This is 71 degrees 21 minutes and 36 seconds, i.e. 71 degrees 21.6 minutes, and would be transmitted as 7121.6000. At least the following OEM receivers have a software bug that does the conversion to the DDMM.FFFF NMEA format wrong: Garmin GPS 16 (discontinued) and Garmin GPS 18 OEM-PC (still available as of 2010). Note that I am not familiar with the NMEA output of the Garmin GPS 18x or any other Garmin receiver.

At the heart of the issue seems to be a combination of sloppy programming in conjunction with the use of low resolution (single-precision, IEEE 754) floating point arithmetic.

Consider the following case: we attach an external data logger to a Garmin receiver that reads the NMEA sentences to keep track of our position while we walk very slowly, at something like 0.5 meters per second, due North. We may find the following (this result is simulated with the script below):
actual latitude   output in NMEA sentence
in degrees        in DDMM.FFFF format
71.359976         7121.5986
71.359982         7121.5991
71.359988         7121.5991
71.359994         7121.5995
71.360000         7121.6000
71.360006         7121.6004
71.360012         7121.6004
71.360018         7121.6009
So far so good. We see that the conversion took place with limited precision but otherwise everything is fine.

Doing the same experiment a bit further to the South we find (this result is simulated with the script below):
actual latitude   output in NMEA sentence
in degrees        in DDMM.FFFF format
71.349982         7120.9989
71.349988         7120.9994
71.349994         7120.9994
71.350000         7121.9999
71.350006         7121.0003
71.350012         7121.0008
71.350018         7121.0012
Clearly, a rounding error occurred in the conversion that increased the minutes from 20 to 21 before the fractional minutes actually rolled over to 0.

I have seen this error occur over and over again in both latitude and longitude in the region around Barrow, Alaska. However, I bet this problem is more general and will be observable at certain minutes all around the world, including in San Francisco (37° 46' N), and New York (40° 31' N) — in case somebody would like to check.

Reverse Engineering

How can we reproduce this error? Well, for example with the following Python 2.x script:
import numpy as np
# simulate the roll-over error in
# Garmin's degree / minute conversion
# script written by Chris Petrich, 2010

# this seems to happen if minutes are calculated in two
# different ways in conjunction with limited precision

def convert(degrees):
    # enforce use of single precision (i.e. f4)
    degrees = degrees.astype('f4')
    v60 = np.array(60., dtype='f4')
    # integer degrees
    deg = np.floor(degrees)
    # get fractional minutes:
    minute = (degrees - deg) * v60    
    frac = minute - np.floor(minute)
    # now calculate whole minutes differently:
    minute = np.floor( degrees*v60 - deg*v60 )

    # get the number before the dot:
    whole = int( deg ) * 100 + int( minute )
    return '%.4i.%.4i' % (whole, int(frac*10000))

# generate a few coordinates:
delta = .000006
ref = 71 + 21/60.
test_degrees = np.arange(ref-5*delta, ref+5*delta, delta)
# and output data
print "GARMIN's rounding error"
print 'decimal deg,  DDMM.FFFF (NMEA)'
for deg in  test_degrees:
    print deg, '%s' % convert(deg)


The remedy may be obvious: if this bugs you then write to Garmin and request a firmware patch for your receiver. Happy geo-locating!

No comments: