Hammerhead/Protocol

From Openmoko

(Difference between revisions)
Jump to: navigation, search
m (add faqish)
m (Replacing 'Freerunner' with 'FreeRunner')
 
(68 intermediate revisions by 12 users not shown)
Line 1: Line 1:
−
Christian did some stracing on TomTom device, and result is great logs at http://www.maintech.de/download/hammerhead-strace.log .
+
Hammerhead is the GPS receiver chip used in the Neo 1973. The only way currently to use it is via a closed-source binary program. This page describes efforts to write an open source driver. (Mostly abandoned since the release of the Neo FreeRunner which uses a different chipset)
  
−
GPS seems to communicate in packets.
+
== Repository ==
  
−
Direction GPS -> machine
+
We have set up a SCM repository for experimental code and documentation at http://projects.linuxtogo.org/projects/sphyrna.
  
−
read(3, "\xfe\x00\xfd\x80\x16\x19\x0b\x00\x00\xfc", 2048) = 10
+
[[User:mmontour]] has created a quick and dirty gtk program called 'satscan' which performs the first steps of a cold-start acquisition. It scans through the satellite numbers 8 at a time in several different frequency bands, and displays a symbol on the screen indicating the strength of each signal. The program (which includes portions of 'hhtest.c') is available here: [http://members.shaw.ca/mmontour/satscan/]. Description/screenshots are 
  
−
\xfe: begining of packet
+
[http://openmoko.togaware.com/survivor/SatScan.html]
−
\x00: type of packet? seems to determine length.
+
−
\xfd: follows
+
−
....
+
−
\xfc: packet end
+
  
−
GPS signals at wikipedia seems to be required reading: http://en.wikipedia.org/wiki/GPS_signals
+
== Background resources ==
  
−
=== Possible lock scheme that it may use===
+
Christian did some stracing on TomTom device, and result is great logs at http://www.maintech.de/download/hammerhead-strace.log . 'pH5' on IRC has put up some traces at http://linuxtogo.org/~ph5/tmp/gllin (a cold start, a hot start and a somewhat longer trace). He even has a software that can init and send command to phase-1 openmoko device in http://linuxtogo.org/~ph5/tmp/hhtest.c . (Please use strace -s9999 -x to produce traces).  http://folks.o-hand.com/andrew/strace-schwartz-oabi is a log of all library calls (i.e. a superset of system calls) made by gllin during a hot start and acquiring the time (but no fix), except acos() because printing all acos() calls would fill gigabytes per second.
  
−
From reading the published brief information sheets on global locates products, not the patents.
+
A file giving doppler information on the above longtrace NMEA is on [http://www.mauve.plus.com/gps].
−
The global locate chip has massively parallel correlators, and configurable integrators to integrate over a given time.
+
−
I would expect it to do something like - in this case.
+
−
*Load orbit data from file.
+
−
*Look at time.
+
−
*Compute which satellites are up.
+
−
*Init the GPS.
+
−
*Set the hardware to expect to receive from the  set of visible satellites (the hardware is unlikely to be designed to receive them all at once, as you'll never see more than around 12 of the nominal 24).
+
−
*Set the integration time at 10ms-20ms or so - around, or a bit under a data bit.
+
−
*Now, read back the outputs of the integrators, to see if we've got possible data.
+
−
*If we do have data, spend a bit of time working out where the data bits begin and end in the datastream per satellite.
+
−
**it's possible this is done in hardware
+
−
*Now that we've got all the satellites locked in the hardware, simply interrogate the hardware regularly, so that we can read out the 50bps datastream from each satellite.
+
−
**It seems this step takes 19s or so. From the first timestamp in the file, to the first GPGSV line - satellites in view, and their actual signal strengths.
+
−
*Read the navigation messages from each satellite, which cycles every 6 seconds.
+
−
*Compute a position.
+
−
*Output it to NMEA
+
−
** It seems this takes 22 seconds.
+
  
−
=== Analysis ===
+
[http://en.wikipedia.org/wiki/GPS_signals GPS signals at wikipedia] seems to be required reading for very basics, along with  [http://www.colorado.edu/geography/gcraft/notes/gps/gps.html this page from University of Colorado] for more in depth stuff.
  
−
Were there by any chance 8 satellites overhead at the time that log was made?
+
http://home.earthlink.net/~cwkelley/ has sources for open-source GPS receiver, and
 +
http://home.earthlink.net/~cwkelley/documentation.htm is its documentation.
  
−
The protocol appears to be oriented around 32-bit words (the single-byte markers notwithstanding.)  I'm not absolutely certain, but I strongly suspect the byte order is LSB-first.
+
https://okeefesrv.geomatics.ucalgary.ca/essentials/index.html provides a library of useful GPS-related algorithms under a 3-clause BSD license.  
  
−
The first stream of 0x80's to the GPS is simply to synch up the UART in the GPS to the correct baudrate.
+
GP2021 is "dumb" GPS receiver, similar to hammerhead. (But I think it communicates over ISA bus, not over serial). However, its data sheets are freely available. Well, hammerhead marketing tells us that their GPS chip is something special, http://www.gpsworld.com/gpsworld/article/articleDetail.jsp?id=3053 . It seems to differ from "dumb" receivers by doing code phase search in hardware, directly.
  
−
Packet format (same format in both directions):
+
There is an interesting paper on increasing accuracy of commercial GPSs that may be applicable. [http://www.ion.org/search/view_abstract.cfm?jp=j&idno=2439].
−
* The start of a packet is marked by FF or FE.
+
Other interesting papers. [http://gauss.gge.unb.ca/papers.pdf/iongpsgnss2003.beran.pdf] [http://topo.epfl.ch/documents/EuroSDR/beran05.pdf]
−
** FF in packets that do not carry data, but rather explicitly request a response. (This isn't used very often. More often we receive data without explicitly requesting it.)  The response will be an FE-packet with the same length and type as the FF-packet. The GPS does not send any FF packets, only gltt does.
+
−
** FE in packets that carry data sections.
+
−
* The first word (32 bits) following the start-of-packet marker is the header.
+
−
** The first byte (if it's indeed little-endian, the least significant byte) gives the data length, measured as ''the number of data words minus 1.''  For FE-packets, this is the length of the data section of this packet. For FF-packets, it's the length of the data section in the expected response.
+
−
** The second byte of the header is always FD.
+
−
** MS nibble of the third byte might be flags for the packet.
+
−
** LS nibble of the third byte might be an identifying number which is echoed in responses to this packet.
+
−
** The fourth byte is the packet type.
+
−
* In FE-packets only, the data section (''n'' 32-bit words) follows.
+
−
* Finally, FC is sent to mark the end of the packet.
+
−
* After the FC in an FF-packet, gltt sends a bunch of zeroes.  In some cases it sends a number of zeroes equal to the number of bytes in the response packet; in some cases it sends more.  I would guess that these have no effect.
+
  
−
For example:
+
=== Packet format & comm protocol ===
−
ff 04fdc00c fc
+
−
(possibly followed by zeroes), is a request for a packet of type 0C, with length 20d ((4 + 1) * 4), and flags C0.
+
  
−
fe 04fdc00c 0025102a 45dbdd4e 36030000 4b260000 16010000 fc
+
See sphyrna project for up-to-date decoding info.
−
would be an appropriate response.
+
  
−
Packet types:
+
[[Category:GPS]]
−
{|
+
−
| Frequency || Type || Max length || Min length
+
−
|-
+
−
| 9 || 16 || 73 || 11
+
−
|-
+
−
| 86 || 08 || 19 || 11
+
−
|-
+
−
| 8 || e2 || 15 || 15
+
−
|-
+
−
| 7 || 23 || 133 || 101
+
−
|-
+
−
| 63 || 0a || 15 || 15
+
−
|-
+
−
| 6 || 24 || 71 || 39
+
−
|-
+
−
| 52 || 0b || 11 || 11
+
−
|-
+
−
| 4 || 01 || 11 || 11
+
−
|-
+
−
| 263 || 05 || 19 || 15
+
−
|-
+
−
| 24 || 9d || 315 || 19
+
−
|-
+
−
| 2 || 06 || 25 || 19
+
−
|-
+
−
| 16 || e0 || 11 || 11
+
−
|-
+
−
| 13 || 20 || 15 || 15
+
−
|-
+
−
| 13 || 10 || 577 || 59
+
−
|-
+
−
| 128 || 18 || 11 || 11
+
−
|-
+
−
| 12 || 9e || 303 || 15
+
−
|-
+
−
| 117 || 00 || 65 || 39
+
−
|-
+
−
| 11 || 0c || 33 || 11
+
−
|-
+
−
| 10 || 9f || 477 || 61
+
−
|-
+
−
| 10 || 0e || 541 || 31
+
−
|-
+
−
| 1 || e5 || 11 || 11
+
−
|-
+
−
| 1 || 80 || 17 || 17
+
−
|-
+
−
| 1 || 13 || 11 || 11
+
−
|-
+
−
| 1 || 04 || 23 || 23
+
−
|-
+
−
| 1 || 02 || 11 || 11
+
−
|-
+
−
|}
+
−
 
+
−
=== NMEA ===
+
−
 
+
−
It is possible to translate NMEA messages into something readable using script like this:
+
−
<pre>
+
−
#!/bin/bash
+
−
grep -v gettimeofday | \
+
−
sed 's/read.3/read(GPS/' | \
+
−
sed 's/write.3/write(GPS/' | \
+
−
sed 's/write.5/write(NMEA/' | \
+
−
sed 's/\\/\\\\/g' | \
+
−
while read LINE; do
+
−
if echo $LINE | grep write.NMEA; then
+
−
echo -e $LINE
+
−
else
+
−
echo "$LINE"
+
−
fi
+
−
done
+
−
</pre>
+
−
 
+
−
NMEA description is available at http://www.gpsinformation.org/dale/nmea.htm .
+
−
 
+
−
At this point:
+
−
 
+
−
256  write(GPS, "\xfe\x00\xfd\x40\x08\x40\x60\x00\x00\xfc", 10) = 10
+
−
256  write(GPS, "\xfe\x00\xfd\x40\x08\x40\x60\x00\x00\xfc", 10) = 10
+
−
256 write(NMEA, "\x24\x47\x50\x47\x47\x41\x2c\x31\x35\x34\x31\x30\x34\x2e\x39\x35\x2c\x34\x39\x34\x38\x2e\x39\x35\x30\x33\x33\x39\x2c\x4e\x2c\x30\x30\x39\x35\x37\x2e\x39\x35\x35\x39\x37\x39\x2c\x45\x2c\x31\x2c\x30\x36\x2c\x35\x2e\x30\x2c\x32\x32\x30\x2e\x30\x2c\x4d\x2c\x2d\x30\x2e\x35\x38\x31\x30\x31\x34\x2c\x4d\x2c\x2d\x30\x2e\x31\x39\x30\x30\x31\x39\x30\x2c\x2a\x34\x30\x0d\x0a", 91) = 91
+
−
256 write(NMEA, "$GPGGA,154104.95,4948.950339,N,00957.955979,E,1,06,5.0,220.0,M,-0.581014,M,-0.1900190,*40
+
−
", 91) = 91
+
−
 
+
−
...6 satelitte GPS fix was obtained. (And yes, there's big read few lines before that in the log). As far as I can tell, only 5-6 sattelite were _used_ till the end of log.
+
−
 
+
−
GSA sentence looks interesting, too. It tells us satellites #02, #04, #08, #10, #13 and #27 were used at this point.
+
−
 
+
−
256 write(NMEA, "\x24\x47\x50\x47\x53\x41\x2c\x41\x2c\x33\x2c\x30\x32\x2c\x30\x34\x2c\x30\x38\x2c\x31\x30\x2c\x31\x33\x2c\x32\x37\x2c\x2c\x2c\x2c\x2c\x2c\x2c\x36\x2e\x37\x2c\x33\x2e\x30\x2c\x36\x2e\x30\x2a\x33\x45\x0d\x0a", 51) = 51
+
−
256 write(NMEA, "$GPGSA,A,3,02,04,08,10,13,27,,,,,,,6.7,3.0,6.0*3E
+
−
 
+
−
 
+
−
The whole log is
+
−
<pre>
+
−
$GPGGA,154035.21,,,,,00,00,5.0,,M,-0.586099,M,-0.1700199,*6A
+
−
$GPRMC,154035.24,V,,,,,,,240407,,*1A
+
−
$GPGSA,A,1,,,,,,,,,,,,,11.2,5.0,10.0*36
+
−
$GPGGA,154035.61,,,,,00,00,5.0,,M,-0.586099,M,-0.1700199,*6E
+
−
$GPRMC,154035.63,V,,,,,,,240407,,*19
+
−
$GPGSA,A,1,,,,,,,,,,,,,11.2,5.0,10.0*36
+
−
$GPGGA,154038.24,,,,,00,04,300.0,,M,-0.586099,M,0.0000199,*4B
+
−
$GPRMC,154038.29,V,,,,,,,240407,,*1A
+
−
$GPGSA,A,1,02,04,08,10,,,,,,,,,669.0,300.0,600.0*33
+
−
$GPGGA,154038.54,,,,,00,04,300.0,,M,-0.586099,M,0.0000199,*4C
+
−
$GPRMC,154038.56,V,,,,,,,240407,,*12
+
−
$GPGSA,A,1,02,04,08,10,,,,,,,,,669.0,300.0,600.0*33
+
−
$GPGGA,154042.72,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*46
+
−
$GPRMC,154042.74,V,,,,,,,240407,,*1F
+
−
$GPGSV,3,1,09,27,77,114,24,08,59,192,33,10,46,302,33,02,33,244,34*7E
+
−
$GPGSV,3,2,09,04,18,206,33,13,42,076,25,29,11,271,29,24,243,352,*49
+
−
$GPGSV,3,3,09,23,14,085,*49
+
−
$GPGSA,A,1,02,04,08,10,27,,,,,,,,669.0,300.0,600.0*36
+
−
$GPGGA,154043.67,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*43
+
−
$GPRMC,154043.69,V,,,,,,,240407,,*12
+
−
$GPGSA,A,1,02,04,08,10,27,,,,,,,,669.0,300.0,600.0*36
+
−
$GPGGA,154046.89,,,,,00,06,300.0,,M,-0.587100,M,0.0000199,*47
+
−
$GPRMC,154046.93,V,,,,,,,240407,,*12
+
−
$GPGSA,A,1,02,04,08,10,,,,,,,,,669.0,300.0,600.0*33
+
−
$GPGGA,154047.14,,,,,00,06,300.0,,M,-0.587100,M,0.0000199,*42
+
−
$GPRMC,154047.19,V,,,,,,,240407,,*11
+
−
$GPGSA,A,1,02,04,08,10,,,,,,,,,669.0,300.0,600.0*33
+
−
$GPGGA,154050.07,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*47
+
−
$GPRMC,154050.10,V,,,,,,,240407,,*1E
+
−
$GPGSA,A,1,27,,,,,,,,,,,,669.0,300.0,600.0*39
+
−
$GPGGA,154050.45,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*41
+
−
$GPRMC,154050.47,V,,,,,,,240407,,*1C
+
−
$GPGSV,3,1,09,27,77,114,24,08,59,192,26,10,46,302,25,13,42,076,16*78
+
−
$GPGSV,3,2,09,02,33,244,26,04,18,206,25,29,11,271,25,24,243,352,*44
+
−
$GPGSV,3,3,09,23,14,085,*49
+
−
$GPGSA,A,1,27,,,,,,,,,,,,669.0,300.0,600.0*39
+
−
$GPGGA,154053.35,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*45
+
−
$GPRMC,154053.37,V,,,,,,,240407,,*18
+
−
$GPGSA,A,1,27,,,,,,,,,,,,669.0,300.0,600.0*39
+
−
$GPGGA,154058.70,,,,,00,03,300.0,,M,-0.581014,M,0.0000199,*49
+
−
$GPRMC,154058.72,V,,,,,,,240407,,*12
+
−
$GPGSA,A,1,02,,,,,,,,,,,,669.0,300.0,600.0*3E
+
−
$GPGGA,154058.97,,,,,00,03,300.0,,M,-0.581014,M,0.0000199,*40
+
−
$GPRMC,154058.98,V,,,,,,,240407,,*16
+
−
$GPGSA,A,1,02,,,,,,,,,,,,669.0,300.0,600.0*3E
+
−
$GPGGA,154059.38,,,,,00,03,300.0,,M,-0.581014,M,0.0000199,*44
+
−
$GPRMC,154059.40,V,,,,,,,240407,,*12
+
−
$GPGSA,A,1,02,13,,,,,,,,,,,669.0,300.0,600.0*3C
+
−
$GPGGA,154104.95,4948.950339,N,00957.955979,E,1,06,5.0,220.0,M,-0.581014,M,-0.1900190,*40
+
−
$GPRMC,154104.95,A,4948.950339,N,00957.955979,E,000.0,000.0,240407,,*3E
+
−
$GPGSV,3,1,09,08,59,192,42,10,46,302,42,04,18,206,41,27,77,114,16*74
+
−
$GPGSV,3,2,09,13,42,076,18,02,33,244,18,29,11,271,40,24,243,352,*48
+
−
$GPGSV,3,3,09,23,14,085,*49
+
−
$GPGSA,A,3,04,08,10,,,,,,,,,,11.2,5.0,10.0*39
+
−
$GPGGA,154106.52,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.581025,M,-0.1900190,*4A
+
−
$GPRMC,154111.60,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*35
+
−
$GPGSA,A,3,02,04,08,10,27,,,,,,,,6.7,3.0,6.0*3C
+
−
$GPGGA,154122.94,,,,,00,06,3.0,,M,-0.581010,M,-0.1900190,*62
+
−
$GPRMC,154122.96,V,,,,,,,240407,,*14
+
−
$GPGSA,A,1,13,,,,,,,,,,,,6.7,3.0,6.0*36
+
−
$GPGGA,154119.10,4948.936977,N,00957.930742,E,1,05,3.0,245.0,M,-0.576004,M,-0.1870190,*4D
+
−
$GPRMC,154119.10,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*3A
+
−
$GPGSA,A,3,04,08,10,27,,,,,,,,,6.7,3.0,6.0*3E
+
−
$GPGGA,154128.15,4948.936977,N,00957.930742,E,1,06,5.0,245.0,M,-0.587003,M,-0.1860190,*47
+
−
$GPRMC,154128.15,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*3D
+
−
$GPGSV,3,1,09,27,77,114,22,08,59,192,39,10,46,302,39,02,33,244,40*7B
+
−
$GPGSV,3,2,09,04,18,206,38,13,42,076,11,24,243,352,,23,14,085,*48
+
−
$GPGSV,3,3,09,29,11,271,*4F
+
−
$GPGSA,A,3,02,04,08,10,27,,,,,,,,11.2,5.0,10.0*3E
+
−
$GPGGA,154131.86,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.578004,M,-0.1860190,*44
+
−
$GPRMC,154131.86,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*3F
+
−
$GPGSA,A,3,02,04,08,10,13,27,,,,,,,6.7,3.0,6.0*3E
+
−
$GPGGA,154138.55,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.578000,M,-0.1860190,*47
+
−
$GPRMC,154138.55,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*38
+
−
$GPGSA,A,3,02,04,08,10,13,27,,,,,,,6.7,3.0,6.0*3E
+
−
$GPGGA,154141.69,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.583002,M,-0.1840190,*42
+
−
$GPRMC,154141.69,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*39
+
−
$GPGSA,A,3,02,04,08,10,27,,,,,,,,6.7,3.0,6.0*3C
+
−
$GPGGA,154146.16,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.595000,M,-0.1830190,*4F
+
−
$GPRMC,154146.16,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*36
+
−
$GPGSA,A,3,02,04,08,10,27,,,,,,,,6.7,3.0,6.0*3C
+
−
$GPGGA,154151.34,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.587002,M,-0.1860190,*4D
+
−
$GPRMC,154151.34,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*30
+
−
$GPGSV,3,1,09,27,77,114,26,08,59,192,42,10,46,302,41,13,42,076,25*7A
+
−
$GPGSV,3,2,09,02,33,244,42,04,18,206,37,29,11,271,37,24,243,352,*46
+
−
$GPGSV,3,3,09,23,14,085,*49
+
−
$GPGSA,A,3,02,04,08,10,13,27,,,,,,,6.7,3.0,6.0*3E
+
−
$GPGGA,154200.05,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.587002,M,-0.1860190,*48
+
−
$GPRMC,154200.05,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*35
+
−
$GPGSA,A,3,,,,,,,,,,,,,6.7,3.0,6.0*36
+
−
 
+
−
</pre>
+

Latest revision as of 14:39, 31 August 2008

Hammerhead is the GPS receiver chip used in the Neo 1973. The only way currently to use it is via a closed-source binary program. This page describes efforts to write an open source driver. (Mostly abandoned since the release of the Neo FreeRunner which uses a different chipset)

[edit] Repository

We have set up a SCM repository for experimental code and documentation at http://projects.linuxtogo.org/projects/sphyrna.

User:mmontour has created a quick and dirty gtk program called 'satscan' which performs the first steps of a cold-start acquisition. It scans through the satellite numbers 8 at a time in several different frequency bands, and displays a symbol on the screen indicating the strength of each signal. The program (which includes portions of 'hhtest.c') is available here: [1]. Description/screenshots are

[2]

[edit] Background resources

Christian did some stracing on TomTom device, and result is great logs at http://www.maintech.de/download/hammerhead-strace.log . 'pH5' on IRC has put up some traces at http://linuxtogo.org/~ph5/tmp/gllin (a cold start, a hot start and a somewhat longer trace). He even has a software that can init and send command to phase-1 openmoko device in http://linuxtogo.org/~ph5/tmp/hhtest.c . (Please use strace -s9999 -x to produce traces). http://folks.o-hand.com/andrew/strace-schwartz-oabi is a log of all library calls (i.e. a superset of system calls) made by gllin during a hot start and acquiring the time (but no fix), except acos() because printing all acos() calls would fill gigabytes per second.

A file giving doppler information on the above longtrace NMEA is on [3].

GPS signals at wikipedia seems to be required reading for very basics, along with this page from University of Colorado for more in depth stuff.

http://home.earthlink.net/~cwkelley/ has sources for open-source GPS receiver, and http://home.earthlink.net/~cwkelley/documentation.htm is its documentation.

https://okeefesrv.geomatics.ucalgary.ca/essentials/index.html provides a library of useful GPS-related algorithms under a 3-clause BSD license.

GP2021 is "dumb" GPS receiver, similar to hammerhead. (But I think it communicates over ISA bus, not over serial). However, its data sheets are freely available. Well, hammerhead marketing tells us that their GPS chip is something special, http://www.gpsworld.com/gpsworld/article/articleDetail.jsp?id=3053 . It seems to differ from "dumb" receivers by doing code phase search in hardware, directly.

There is an interesting paper on increasing accuracy of commercial GPSs that may be applicable. [4]. Other interesting papers. [5] [6]

[edit] Packet format & comm protocol

See sphyrna project for up-to-date decoding info.

Retrieved from "http://openmoko.org/index.php?title=Hammerhead/Protocol&oldid=51131"
Personal tools

Christian did some stracing on TomTom device, and result is great logs at http://www.maintech.de/download/hammerhead-strace.log .

GPS seems to communicate in packets.

Direction GPS -> machine

read(3, "\xfe\x00\xfd\x80\x16\x19\x0b\x00\x00\xfc", 2048) = 10

\xfe: begining of packet \x00: type of packet? seems to determine length. \xfd: follows .... \xfc: packet end

GPS signals at wikipedia seems to be required reading: http://en.wikipedia.org/wiki/GPS_signals

Possible lock scheme that it may use

From reading the published brief information sheets on global locates products, not the patents. The global locate chip has massively parallel correlators, and configurable integrators to integrate over a given time. I would expect it to do something like - in this case.

  • Load orbit data from file.
  • Look at time.
  • Compute which satellites are up.
  • Init the GPS.
  • Set the hardware to expect to receive from the set of visible satellites (the hardware is unlikely to be designed to receive them all at once, as you'll never see more than around 12 of the nominal 24).
  • Set the integration time at 10ms-20ms or so - around, or a bit under a data bit.
  • Now, read back the outputs of the integrators, to see if we've got possible data.
  • If we do have data, spend a bit of time working out where the data bits begin and end in the datastream per satellite.
    • it's possible this is done in hardware
  • Now that we've got all the satellites locked in the hardware, simply interrogate the hardware regularly, so that we can read out the 50bps datastream from each satellite.
    • It seems this step takes 19s or so. From the first timestamp in the file, to the first GPGSV line - satellites in view, and their actual signal strengths.
  • Read the navigation messages from each satellite, which cycles every 6 seconds.
  • Compute a position.
  • Output it to NMEA
    • It seems this takes 22 seconds.

Analysis

Were there by any chance 8 satellites overhead at the time that log was made?

The protocol appears to be oriented around 32-bit words (the single-byte markers notwithstanding.) I'm not absolutely certain, but I strongly suspect the byte order is LSB-first.

The first stream of 0x80's to the GPS is simply to synch up the UART in the GPS to the correct baudrate.

Packet format (same format in both directions):

  • The start of a packet is marked by FF or FE.
    • FF in packets that do not carry data, but rather explicitly request a response. (This isn't used very often. More often we receive data without explicitly requesting it.) The response will be an FE-packet with the same length and type as the FF-packet. The GPS does not send any FF packets, only gltt does.
    • FE in packets that carry data sections.
  • The first word (32 bits) following the start-of-packet marker is the header.
    • The first byte (if it's indeed little-endian, the least significant byte) gives the data length, measured as the number of data words minus 1. For FE-packets, this is the length of the data section of this packet. For FF-packets, it's the length of the data section in the expected response.
    • The second byte of the header is always FD.
    • MS nibble of the third byte might be flags for the packet.
    • LS nibble of the third byte might be an identifying number which is echoed in responses to this packet.
    • The fourth byte is the packet type.
  • In FE-packets only, the data section (n 32-bit words) follows.
  • Finally, FC is sent to mark the end of the packet.
  • After the FC in an FF-packet, gltt sends a bunch of zeroes. In some cases it sends a number of zeroes equal to the number of bytes in the response packet; in some cases it sends more. I would guess that these have no effect.

For example: 

ff 04fdc00c fc

(possibly followed by zeroes), is a request for a packet of type 0C, with length 20d ((4 + 1) * 4), and flags C0. 

fe 04fdc00c 0025102a 45dbdd4e 36030000 4b260000 16010000 fc

would be an appropriate response.

Packet types:

Frequency Type Max length Min length
9 16 73 11
86 08 19 11
8 e2 15 15
7 23 133 101
63 0a 15 15
6 24 71 39
52 0b 11 11
4 01 11 11
263 05 19 15
24 9d 315 19
2 06 25 19
16 e0 11 11
13 20 15 15
13 10 577 59
128 18 11 11
12 9e 303 15
117 00 65 39
11 0c 33 11
10 9f 477 61
10 0e 541 31
1 e5 11 11
1 80 17 17
1 13 11 11
1 04 23 23
1 02 11 11

NMEA

It is possible to translate NMEA messages into something readable using script like this: 

#!/bin/bash
grep -v gettimeofday | \
	sed 's/read.3/read(GPS/' | \
	sed 's/write.3/write(GPS/' | \
	sed 's/write.5/write(NMEA/' | \
	sed 's/\\/\\\\/g' | \
	while read LINE; do
		if echo $LINE | grep write.NMEA; then
			echo -e $LINE
		else
			echo "$LINE"
		fi
	done

NMEA description is available at http://www.gpsinformation.org/dale/nmea.htm .

At this point:

256 write(GPS, "\xfe\x00\xfd\x40\x08\x40\x60\x00\x00\xfc", 10) = 10 256 write(GPS, "\xfe\x00\xfd\x40\x08\x40\x60\x00\x00\xfc", 10) = 10 256 write(NMEA, "\x24\x47\x50\x47\x47\x41\x2c\x31\x35\x34\x31\x30\x34\x2e\x39\x35\x2c\x34\x39\x34\x38\x2e\x39\x35\x30\x33\x33\x39\x2c\x4e\x2c\x30\x30\x39\x35\x37\x2e\x39\x35\x35\x39\x37\x39\x2c\x45\x2c\x31\x2c\x30\x36\x2c\x35\x2e\x30\x2c\x32\x32\x30\x2e\x30\x2c\x4d\x2c\x2d\x30\x2e\x35\x38\x31\x30\x31\x34\x2c\x4d\x2c\x2d\x30\x2e\x31\x39\x30\x30\x31\x39\x30\x2c\x2a\x34\x30\x0d\x0a", 91) = 91 256 write(NMEA, "$GPGGA,154104.95,4948.950339,N,00957.955979,E,1,06,5.0,220.0,M,-0.581014,M,-0.1900190,*40 ", 91) = 91

...6 satelitte GPS fix was obtained. (And yes, there's big read few lines before that in the log). As far as I can tell, only 5-6 sattelite were _used_ till the end of log.

GSA sentence looks interesting, too. It tells us satellites #02, #04, #08, #10, #13 and #27 were used at this point.

256 write(NMEA, "\x24\x47\x50\x47\x53\x41\x2c\x41\x2c\x33\x2c\x30\x32\x2c\x30\x34\x2c\x30\x38\x2c\x31\x30\x2c\x31\x33\x2c\x32\x37\x2c\x2c\x2c\x2c\x2c\x2c\x2c\x36\x2e\x37\x2c\x33\x2e\x30\x2c\x36\x2e\x30\x2a\x33\x45\x0d\x0a", 51) = 51 256 write(NMEA, "$GPGSA,A,3,02,04,08,10,13,27,,,,,,,6.7,3.0,6.0*3E


The whole log is 

$GPGGA,154035.21,,,,,00,00,5.0,,M,-0.586099,M,-0.1700199,*6A
$GPRMC,154035.24,V,,,,,,,240407,,*1A
$GPGSA,A,1,,,,,,,,,,,,,11.2,5.0,10.0*36
$GPGGA,154035.61,,,,,00,00,5.0,,M,-0.586099,M,-0.1700199,*6E
$GPRMC,154035.63,V,,,,,,,240407,,*19
$GPGSA,A,1,,,,,,,,,,,,,11.2,5.0,10.0*36
$GPGGA,154038.24,,,,,00,04,300.0,,M,-0.586099,M,0.0000199,*4B
$GPRMC,154038.29,V,,,,,,,240407,,*1A
$GPGSA,A,1,02,04,08,10,,,,,,,,,669.0,300.0,600.0*33
$GPGGA,154038.54,,,,,00,04,300.0,,M,-0.586099,M,0.0000199,*4C
$GPRMC,154038.56,V,,,,,,,240407,,*12
$GPGSA,A,1,02,04,08,10,,,,,,,,,669.0,300.0,600.0*33
$GPGGA,154042.72,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*46
$GPRMC,154042.74,V,,,,,,,240407,,*1F
$GPGSV,3,1,09,27,77,114,24,08,59,192,33,10,46,302,33,02,33,244,34*7E
$GPGSV,3,2,09,04,18,206,33,13,42,076,25,29,11,271,29,24,243,352,*49
$GPGSV,3,3,09,23,14,085,*49
$GPGSA,A,1,02,04,08,10,27,,,,,,,,669.0,300.0,600.0*36
$GPGGA,154043.67,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*43
$GPRMC,154043.69,V,,,,,,,240407,,*12
$GPGSA,A,1,02,04,08,10,27,,,,,,,,669.0,300.0,600.0*36
$GPGGA,154046.89,,,,,00,06,300.0,,M,-0.587100,M,0.0000199,*47
$GPRMC,154046.93,V,,,,,,,240407,,*12
$GPGSA,A,1,02,04,08,10,,,,,,,,,669.0,300.0,600.0*33
$GPGGA,154047.14,,,,,00,06,300.0,,M,-0.587100,M,0.0000199,*42
$GPRMC,154047.19,V,,,,,,,240407,,*11
$GPGSA,A,1,02,04,08,10,,,,,,,,,669.0,300.0,600.0*33
$GPGGA,154050.07,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*47
$GPRMC,154050.10,V,,,,,,,240407,,*1E
$GPGSA,A,1,27,,,,,,,,,,,,669.0,300.0,600.0*39
$GPGGA,154050.45,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*41
$GPRMC,154050.47,V,,,,,,,240407,,*1C
$GPGSV,3,1,09,27,77,114,24,08,59,192,26,10,46,302,25,13,42,076,16*78
$GPGSV,3,2,09,02,33,244,26,04,18,206,25,29,11,271,25,24,243,352,*44
$GPGSV,3,3,09,23,14,085,*49
$GPGSA,A,1,27,,,,,,,,,,,,669.0,300.0,600.0*39
$GPGGA,154053.35,,,,,00,06,300.0,,M,-0.586100,M,0.0000199,*45
$GPRMC,154053.37,V,,,,,,,240407,,*18
$GPGSA,A,1,27,,,,,,,,,,,,669.0,300.0,600.0*39
$GPGGA,154058.70,,,,,00,03,300.0,,M,-0.581014,M,0.0000199,*49
$GPRMC,154058.72,V,,,,,,,240407,,*12
$GPGSA,A,1,02,,,,,,,,,,,,669.0,300.0,600.0*3E
$GPGGA,154058.97,,,,,00,03,300.0,,M,-0.581014,M,0.0000199,*40
$GPRMC,154058.98,V,,,,,,,240407,,*16
$GPGSA,A,1,02,,,,,,,,,,,,669.0,300.0,600.0*3E
$GPGGA,154059.38,,,,,00,03,300.0,,M,-0.581014,M,0.0000199,*44
$GPRMC,154059.40,V,,,,,,,240407,,*12
$GPGSA,A,1,02,13,,,,,,,,,,,669.0,300.0,600.0*3C
$GPGGA,154104.95,4948.950339,N,00957.955979,E,1,06,5.0,220.0,M,-0.581014,M,-0.1900190,*40
$GPRMC,154104.95,A,4948.950339,N,00957.955979,E,000.0,000.0,240407,,*3E
$GPGSV,3,1,09,08,59,192,42,10,46,302,42,04,18,206,41,27,77,114,16*74
$GPGSV,3,2,09,13,42,076,18,02,33,244,18,29,11,271,40,24,243,352,*48
$GPGSV,3,3,09,23,14,085,*49
$GPGSA,A,3,04,08,10,,,,,,,,,,11.2,5.0,10.0*39
$GPGGA,154106.52,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.581025,M,-0.1900190,*4A
$GPRMC,154111.60,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*35
$GPGSA,A,3,02,04,08,10,27,,,,,,,,6.7,3.0,6.0*3C
$GPGGA,154122.94,,,,,00,06,3.0,,M,-0.581010,M,-0.1900190,*62
$GPRMC,154122.96,V,,,,,,,240407,,*14
$GPGSA,A,1,13,,,,,,,,,,,,6.7,3.0,6.0*36
$GPGGA,154119.10,4948.936977,N,00957.930742,E,1,05,3.0,245.0,M,-0.576004,M,-0.1870190,*4D
$GPRMC,154119.10,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*3A
$GPGSA,A,3,04,08,10,27,,,,,,,,,6.7,3.0,6.0*3E
$GPGGA,154128.15,4948.936977,N,00957.930742,E,1,06,5.0,245.0,M,-0.587003,M,-0.1860190,*47
$GPRMC,154128.15,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*3D
$GPGSV,3,1,09,27,77,114,22,08,59,192,39,10,46,302,39,02,33,244,40*7B
$GPGSV,3,2,09,04,18,206,38,13,42,076,11,24,243,352,,23,14,085,*48
$GPGSV,3,3,09,29,11,271,*4F
$GPGSA,A,3,02,04,08,10,27,,,,,,,,11.2,5.0,10.0*3E
$GPGGA,154131.86,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.578004,M,-0.1860190,*44
$GPRMC,154131.86,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*3F
$GPGSA,A,3,02,04,08,10,13,27,,,,,,,6.7,3.0,6.0*3E
$GPGGA,154138.55,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.578000,M,-0.1860190,*47
$GPRMC,154138.55,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*38
$GPGSA,A,3,02,04,08,10,13,27,,,,,,,6.7,3.0,6.0*3E
$GPGGA,154141.69,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.583002,M,-0.1840190,*42
$GPRMC,154141.69,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*39
$GPGSA,A,3,02,04,08,10,27,,,,,,,,6.7,3.0,6.0*3C
$GPGGA,154146.16,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.595000,M,-0.1830190,*4F
$GPRMC,154146.16,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*36
$GPGSA,A,3,02,04,08,10,27,,,,,,,,6.7,3.0,6.0*3C
$GPGGA,154151.34,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.587002,M,-0.1860190,*4D
$GPRMC,154151.34,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*30
$GPGSV,3,1,09,27,77,114,26,08,59,192,42,10,46,302,41,13,42,076,25*7A
$GPGSV,3,2,09,02,33,244,42,04,18,206,37,29,11,271,37,24,243,352,*46
$GPGSV,3,3,09,23,14,085,*49
$GPGSA,A,3,02,04,08,10,13,27,,,,,,,6.7,3.0,6.0*3E
$GPGGA,154200.05,4948.936977,N,00957.930742,E,1,06,3.0,245.0,M,-0.587002,M,-0.1860190,*48
$GPRMC,154200.05,A,4948.936977,N,00957.930742,E,000.0,000.0,240407,,*35
$GPGSA,A,3,,,,,,,,,,,,,6.7,3.0,6.0*36