Minimal GPS Parser [Updated]
28th November 2014
This article describes a simple GPS parsing routine designed to run on any AVR processor, including the ATtinys such as the ATtiny85 or ATtiny2313. The code is completely self-contained and doesn't require any additional GPS or floating-point library.
NMEA sentences
GPS modules output the GPS information as a series of text strings, called NMEA sentences [1]. Each NMEA sentence starts with an identifier such as $GPRMC, to identify the sentence, followed by the GPS parameters such as latitude and longitude, separated by commas. The string is terminated by an asterisk and two-digit checksum.
The most useful NMEA sentence is RMC (Recommended Minimum C), which contains all the most important navigational parameters: time, latitude, longitude, speed, course, and date. Here's a typical example of the RMC sentence:
$GPRMC,194509.000,A,4042.6142,N,07400.4168,W,2.03,221.11,160414,,,A*77
The fields are as follows:
- 194509.000 - Time is 19:45:09 and 000 milliseconds UTC
- A - Status, A=active or V=void
- 4042.6142,N - Latitude 40° 42.6142' N
- 07400.4168,W - Longitude 74° 00.4168' W
- 2.03 - Ground speed 2.03 knots
- 221.11 - Course 221.11°
- 160414 - Date 16th April 2014
- A - Mode, A=autonomous, D=differential, E=estimated
- *77 - The checksum
Most of the fields are fixed width, with a fixed number of decimal places. If your GPS module outputs the data with a different number of decimal places you will need to adjust the format string in the following routine; check the module's datasheet for details. In the module I used the speed was variable format, and the following routine takes account of this.
Decoding the GPS string
The routine ParseGPS() decodes the information in the NMEA string from the GPS module. It takes the unusual approach of decoding each character as it is received, rather then buffering the characters and then using string operations on them like other GPS libraries. It uses a simple state machine to ensure that each character is processed quickly, so the work can be done in the time between each received character:
// Example: $GPRMC,194509.000,A,4042.6142,N,07400.4168,W,2.03,5.84,160412,,,A*77
char fmt[]="$GPRMC,dddtdd.ddm,A,eeae.eeee,l,eeeae.eeee,o,djdk,djdc,dddy??,,,?*??";
int state = 0;
unsigned int temp;
long ltmp;
// GPS variables
volatile unsigned int Time, Msecs, Knots, Course, Date;
volatile long Lat, Long;
volatile boolean Fix;
void ParseGPS (char c) {
if (c == '$') { state = 0; temp = 0; }
char mode = fmt[state++];
// If received character matches format string, or format is '?' - return
if ((mode == c) || (mode == '?')) return;
// d=decimal digit
char d = c - '0';
if (mode == 'd') temp = temp*10 + d;
// e=long decimal digit
else if (mode == 'e') ltmp = (ltmp<<3) + (ltmp<<1) + d; // ltmp = ltmp*10 + d;
// a=angular measure
else if (mode == 'a') ltmp = (ltmp<<2) + (ltmp<<1) + d; // ltmp = ltmp*6 + d;
// t=Time - hhmm
else if (mode == 't') { Time = temp*10 + d; temp = 0; }
// m=Millisecs
else if (mode == 'm') { Msecs = temp*10 + d; ltmp=0; }
// l=Latitude - in minutes*1000
else if (mode == 'l') { if (c == 'N') Lat = ltmp; else Lat = -ltmp; ltmp = 0; }
// o=Longitude - in minutes*1000
else if (mode == 'o') { if (c == 'E') Long = ltmp; else Long = -ltmp; temp = 0; }
// j/k=Speed - in knots*100
else if (mode == 'j') { if (c != '.') { temp = temp*10 + d; state--; } }
else if (mode == 'k') { Knots = temp*10 + d; temp = 0; }
// c=Course (Track) - in degrees*100
else if (mode == 'c') { Course = temp*10 + d; temp = 0; }
// y=Date - ddmm
else if (mode == 'y') { Date = temp*10 + d ; Fix = 1; }
else state = 0;
}
Routine to parse the RMC NMEA sentence from the GPS module.
Here's how it works:
As each character is received from the GPS sentences it is checked against the format string fmt[], which is a RMC (Recommended Minimum) NMEA sentence with the data replaced by lower-case letters. Each character is tested as follows:
- If the received character is a '$' the state pointer is reset to the start of the fmt[] string.
- If the received character matches the next character in the fmt[] string the match succeeds.
- If the character in the fmt[] string is a lower-case letter it specifies how to process the received character, and the match succeeds.
- Otherwise, the match fails and the state pointer is reset to the start of the string.
The letters 'd', 'e', and 'a' read a received digit and accumulate the value in one of the temporary variables temp or ltmp. For example, a 'd' in the fmt[] string reads a decimal digit into the variable temp.
The letter 'j' keeps accumulating digits until a decimal point is encountered. This caters for fields with a variable number of digits before the decimal point.
The last letter in each field copies the temporary variable into an appropriate GPS variable; for example, the letter 'l' copies ltmp into the latitude variable, Lat.
The routine stores the angular measures, latitude or longitude, in units of 1e-4 arc minutes. Thus one degree is represented as 600,000 units:
const long DEGREE = 600000;
This is designed to allow the arithmetic to be done using long integers, and is ideal for parsing the values returned by the GPS module. If you prefer to work in millionths of a degree like the other GPS libraries simply multiply by 5/3.
The routine decodes the time, latitude, longitude, speed, track, and date. It ignores the checksum.
The routine currently only decodes the RMC string, but it could easily be extended to decode other NMEA strings, such as the GGA string if you want to read the altitude information.
With an 8MHz clock the ParseGPS() routine takes at most about 20µsec to process one character. For comparison, at 9600 baud the characters arrive at intervals of approximately 1000µsec.
Applications
The routine ParseGPS() is designed to be called from an interrupt service routine that receives each character from the GPS module. Because the GPS variables are updated under interrupt they are declared volatile, to tell the compiler that they can change under interrupt.
To read one of the integer or long GPS variables you need to disable interrupts around the call; for example:
long temp; cli(); temp = Knots; sei();
If you don't do this you run the risk of reading a partially-updated value.
To detect whether the GPS module has a fix, use:
while(!Fix);
For applications see:
- Tiny GPS Speedometer [Updated], a speedometer based on an ATtiny85 driving a serial seven-segment display.
- Simple GPS Odometer, an odometer based on an ATtiny2313, driving a four-digit seven-segment display.
- Odometer/Speedometer Pendant [Updated], an odometer/speedometer based on an ATtiny84, driving a four-digit seven-segment display.
- TinyNav Simple GPS Navigator [Updated], a GPS navigator based on an ATtiny85, using four LEDs as a direction display.
Update
10th March 2017: I have updated ParseGPS() to use shifts and adds for the 32-bit multiplications, reducing the worst case execution time by a factor of ten. This avoids problems where the execution time is critical, such as when using a software UART.
- ^ GPS - NMEA sentence information on aprs.gids.nl.
blog comments powered by Disqus