GPS interface using uLisp


#1

In this post I’m going to write about my experiments with interfacing a low-cost serial GPS module directly to uLisp, to create projects such as a GPS clock:

I’ll also describe a GPS speedometer and odometer, and a simple navigator, in later posts.

The module I used is the GP-20U7, a small GPS module available for under $20 from SparkFun GPS Receiver - GP-20U7 (56 Channel), but almost any other GPS module should be suitable.

gp-20u7

The GPS Clock and GPS Speedometer/Odometer will work on any version of uLisp, with sufficient memory, such as the Arduino Mega 2560. The simple navigator requires a 32-bit version of uLisp, running on a board such as the Adafruit ItsyBitsy M0.

Getting started

The first step is to connect the GPS module to your microcontroller’s Rx input; see Language reference - with-serial for details of which pin to use on your board. Then run the following echo program:

(defun echo ()
  (with-serial (str 1 96)
    (loop
     (print (read-line str)))))

At first, before the GPS module has locked onto any satellites, you’ll see something like:

$GPRMC,,V,,,,,,,,,,N*53

If all is well, after a few seconds you should see lines with the time, followed after a minute or so by lines with location data:

$GPGSV,4,4,13,31,13,032,29*41
$GPGLL,5213.12861,N,00008.23883,E,111152.00,A,A*6D
$GPRMC,111153.00,A,5213.12851,N,00008.23852,E,0.408,,101119,,,A*7F
$GPVTG,,T,,M,0.408,N,0.756,K,A*2B
$GPGGA,111153.00,5213.12851,N,00008.23852,E,1,07,1.26,9.2,M,45.7,M,,*59

GPS modules output the GPS information as a series of text strings, called NMEA sentences. 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 the RMC (Recommended Minimum C) one:

$GPRMC,113211.00,A,5213.12667,N,00008.22177,E,4.955,266.36,101119,,,A*64

This contains all the most important navigational parameters: time, latitude, longitude, speed, course, and date. The fields in the above example are as follows:

  • 113211.00 - Time is 11:32:11 and 00 milliseconds UTC
  • A - Status, A=active or V=void
  • 5213.12667,N - Latitude 52° 13.12667’ N
  • 00008.22177,E - Longitude 0° 8.22177’ E
  • 4.955 - Ground speed 4.955 knots
  • 266.36 - Course 266.36°
  • 101119 - Date 10th November 2019
  • A - Mode, A=autonomous, D=differential, E=estimated
  • *64 - The checksum

Note that most fields are fixed width, but the ground speed and course are variable width, and if the GPS module is stationary the course may be blank.

Selecting the RMC sentences

The next step is to select just the RMC sentences; here’s the revised version of echo :

(defun echo ()
  (with-serial (str 1 96)
    (loop
     (let ((line (read-line str)))
       (when (and (> (length line) 7) (string= (subseq line 0 7) "$GPRMC,"))
         (print line))))))

You should now get just one RMC sentence printed every second.

Parsing the RMC sentences

The third step is to parse the parameters from the RMC sentence by extracting the substrings between successive commas. This new version of echo now calls a function parse on each RMC sentence:

(defun echo (fun)
  (with-serial (str 1 96)
    (loop
     (let ((line (read-line str)))
       (when (and (> (length line) 7) (string= (subseq line 0 7) "$GPRMC,"))
         (parse line fun))))))

Here’s the definition of parse :

(defun parse (line fun)
  (let ((start 7)
        (end (length line))
        i result)
    (loop
     (setq i start)
     ; Find comma
     (loop
      (when (or (= i end) (eq (char line i) #\,)) (return))
      (incf i))
     ; Extract parameter
     (push (if (= start i) nil (subseq line start i)) result)
     (setq start (1+ i))
     (when (= i end) (return)))
    ; Call function on result
    (funcall fun (reverse result))))

It splits the string into a list of substrings, one for each parameter. Finally, it calls the function you provide as a parameter on the list of strings. For example, if you do:

(echo print)

it will simply print the list of strings for each RMC sentence, one per second:

("193409.00" "A" "5213.12667" "N" "00008.22177" "E" "2.881" nil "271119" nil nil "A*7D")

Our GPS applications can now simply get the appropriate GPS data from this list; for example the latitude is:

(third lst)

GPS Clock

The first project is a GPS clock that takes advantage of the accuracy of the atomic clocks used by the GPS system to provide an accurate time display in hours, minutes, and seconds on an eight digit 7-segment display.

Driving the 7-segment displays

An ideal display for the GPS clock is the 8-digit seven-segment display module available very cheaply from sites such as AliExpress MAX7219 8 Digit LED Display:

They are based on the MAX7219 display driver MAX7219 Datasheet and are easy to control using SPI.

The MAX7219 is specified as operating from 4.0 V to 5.5 V, but it seems to work fine from 3.3 V. For a brighter display when using it with a 3.3 V board connect VCC on the MAX7219 to the +5 V pin on the board.

Connecting the display

Connect the display using the appropriate SPI pins as follows:

VCC +5V
GND GND
DIN MOSI
CS Enable
CLK SCK

For details of which pins are used for the SPI interface on different processors see Language reference: with-spi.

You can use any suitable pin as the Enable pin; specify it as follows:

(defvar en 10)

Display command

Every command written to the display is a 16-bit word, consisting of an address or command code followed by a data value:

(defun cmd (a d)
  (with-spi (str en)
    (write-byte a str)
    (write-byte d str)))

Initialising the display

The following routine on turns on the display and sets the brightness; the parameter can be from 0 (dimmest) to 15 (brightest):

(defun on (bri)
  (cmd #xF 0)    ; Test mode off
  (cmd #x9 #xFF) ; Code B mode
  (cmd #xB 7)    ; 8 digits
  (cmd #xC 1)    ; Enable display
  (cmd #xA bri))

It set the display in “Code B” mode, which uses an internal lookup table to give the segments for the digits 0 to 9, “-”, and space.

Clearing the display

The following function clr clears the display:

(defun clr ()
  (dotimes (d 8) (cmd (1+ d) #xF)))

Displaying a string

The following routine show writes a text string containing up to eight digits right-aligned on the display:

(defun show (text)
  (let ((len (length text))
        (d 1) (b 0))
    (dotimes (i len)
      (let ((c (char-code (char text (- len i 1)))))
        (cond
         ((= (char-code #\.) c) 
          (incf b #x80))
         (t
          (cond
           ((<= (char-code #\0) c (char-code #\9))
            (incf b (- c (char-code #\0))))
           ((= (char-code #\-) c)
            (incf b #xA))
           (t (incf b #xF)))
          (cmd d b) (incf d) (setq b 0)))))))

It handles decimal points, dashes, and spaces in the string. For example, to display “1234.5678” give the command:

(show "1234.5678")

Displaying the time

To show the time on the 7-segment displays we simply need to call echo with a function that calls show on the first element of the RMC list:

(echo (lambda (lst) (show (first lst))))

To format the time into a more readable display, with the hours, minutes, and seconds separated by dashes, we can define this routine time:

(defun time (lst)
  (let ((tim (first lst)))
    (when tim
      (show
       (concatenate
        'string
        (subseq tim 0 2) "-"
        (subseq tim 2 4) "-"
        (subseq tim 4 6))))))

To display the time from each RMC sentence now call:

(echo time)

Here’s a program go that initialises the display and runs the GPS clock:

(defun go () (on 15) (sho "-- -- --") (echo time))

Making a stand-alone GPS clock

To make a stand-alone GPS clock from this project, proceed as follows:

Uncomment the following preprocessor statement from the uLisp source:

#define resetautorun

and upload uLisp to the ItsyBitsy M0 board, or whatever board you are using.

Enter the program for the GPS clock; here’s the full listing: GPS clock program.

Save the image using the command:

(save-image 'go)

The clock will now run automatically when you apply power to the board.


Read-time evaluation
#2

GPS Speedometer/Odometer

My second GPS project is a GPS Speedometer/Odometer that displays the speed in miles per hour, up to 999 mph, and the distance travelled in miles to one decimal place, up to 999.9 miles:

Note that this is the total distance travelled, not the distance from the starting position, so this application doesn’t need the GPS latitude and longitude readings; the only GPS data we need is the instantaneous speed, in knots, and we integrate this over time to get the distance.

It does the calculations using 32-bit integers, and so requires a 32-bit board such as the Adafruit ItsyBitsy M0. It could also probably be rewritten to work with 16-bit integers.

Calculating and displaying the speed and distance

Here’s the routine speed-dist to calculate and display the speed and distance:

(defvar *dist* 0)

(defun speed-dist (lst)
  (let ((knots (nth 6 lst))
        (dp 3))
    (when knots
      (let* ((len (length knots))
             (k (read-from-string (subseq knots 0 (- len dp 1))))
             (mk (read-from-string (subseq knots (- len dp))))
             (k1000 (+ (* k 1000) mk))
             (mph (truncate (+ (* k1000 38) 19) 33000))
             (m10 (truncate (* *dist* 19) 5943800))
             (miles (truncate m10 10))
             (tenths (mod m10 10))
             (smph (princ-to-string mph))
             (smiles (princ-to-string miles)))
        (when (>= k1000 1000) (incf *dist* k1000))
        (show
         (concatenate
          'string
          (align 3 smph)
          smph
          (align 4 smiles)
          smiles
          "."
          (princ-to-string tenths)))))))

It uses this additional function align to format the display nicely:

(defun align (width str)
  (subseq "   " 0 (- width (length str))))

Run it by passing it as the function argument to echo, defined earlier:

(echo speed-dist)

I took my prototype for a drive to check that it was working correctly.

Description

The leftmost three digits of the display will show the speed in mph. The GPS module I used gives the speed in knots to three decimal places. The speed-dist routine extracts the integer part of the knots string, in k, and the decimal part in mk, and combines these to give thousandths of a knot in k1000. Set dp and change these other variables as appropriate if your GPS module gives a different number of decimal places.

The speed in knots is converted to mph in the variable mph by multiplying by 38/33, which is a good approximation to the conversion factor 1.151. The +19 rounds to the nearest mph value.

The rightmost four digits of the display will show the distance in miles, up to 999.9 miles. To calculate this the program sums the instantaneous speed in the global variable dist, in thousandths of a knot. To convert this to miles you need to multiply the result by 1.151 and divide by 3600; a good rational approximation to this is 19/59438. The variable m10 contains the converted value in tenths of a mile.

If you want to display the speed in km/h and the distance in km change the appropriate lines to:

(kmph (truncate (+ (* k1000 50) 25) 27000))
(km10 (truncate (* *dist* 13) 2527000))

The GPS module can give small speed values even when you are stationary; to avoid these accumulating to give an apparent distance reading the program ignores values of k1000 less than 1000 (1 knot).

Making a stand-alone version

Finally, here’s a function go2 that runs the GPS Speedometer/Odometer:

(defun go2 () (on 15) (show "  -   --") (echo speed-dist))

As before, save the image using:

(save-image 'go2)

The application will then run automatically on reset.

Here’s the full listing: GPS Speedometer/Odometer program.


#3

Simple GPS Navigator

My final project is a simple navigator that displays how far you are from home, in km to the nearest metre, up to 999.999 km. It also displays an arrowhead icon showing the direction you need to travel to get home:

It could be used to help you find your way home when exploring on foot or by bicycle, or back to your hotel when on holiday, or could be used to navigate a robot. You could also use it to find your way to a specified destination, such as for a treasure-hunt.

How it works

This project is the most complicated of the three projects I’ve described here because it needs to calculate the distance and direction from the latitude and longitude in the RMC sentence. Usually these calculations need double-precision floating-point arithmetic, but I’ve used simplified routines that use 32-bit fixed-point arithmetic:

  • distance calculates the distance between two points, specified by their latitude and longitude. It ignores the curvature of the earth, a valid approximation for small distances.

  • course calculates the course from one point to another, assuming the distance between them is small.

The routines are accurate for distances of up to several hundred kilometers. For an explanation of these routines see A Simple GPS Library on Technoblogy.

GPS coordinates

The following routines represent a GPS coordinate as a list of two integers:

(latitude longitude)

These helper routines will be used to extract the latitude and longitude:

(defun lat (c) (first c))
(defun long (c) (second c))

The latitude or longitude are given in units of 10^-4 arc minutes, which I’ll call dimiminutes after the obsolete SI prefix dimi- for 10^-4. Thus one degree is represented as 600,000 dimiminutes:

(defvar *degree* 600000)

This allows the arithmetic to be done using 32-bit integers, and is ideal for parsing the values returned by the GPS module.

Converting to and from decimal degrees (DD)

The standard representation for GPS coordinates, used by Google Maps, is decimal degrees. The latitude coordinate is between -90 and 90 and the longitude coordinate is between -180 and 180.

The following routines convert between dimiminutes and decimal degrees:

(defun degree-dimiminute (n)
  (* n *degree*))

(defun dimiminute-degree (n)
  (/ n *degree*))

Utilities

The routines dist and course use the following utility routines.

The function diff calculates the difference between two angular measures:

(defun diff (deg1 deg2)
  (let ((result (- deg2 deg1)))
    (cond
     ((> result (* *degree* 180)) (- result (* 360 *degree*)))
     ((< result (* *degree* -180)) (+ result (* 360 *degree*)))
     (t result))))

The function cosfix gives a fixed-point approximation to cos:

(defun cosfix (angle)
  (let ((u (ash (abs angle) -16)))
    (setq u (ash (* u u 6086) -24))
    (- 246 u)))

It returns a result scaled by 2^8.

The routine cartesian returns the cartesian difference between two GPS coordinates:

(defun cartesian (from to)
  (let* ((dx (ash (* (diff (long to) (long from)) 
                     (cosfix (ash (+ (lat to) (lat from)) -1))) -8))
         (dy (diff (lat to) (lat from))))
    (list dx dy)))

Distance between two points

The routine distance calculates the distance between two GPS coordinates and returns the result in metres:

(defun distance (from to) 
  (let* ((dxdy (cartesian from to))
         (adx (abs (first dxdy)))
         (ady (abs (second dxdy)))
         (b (max adx ady))
         (a (min adx ady)))
    (if (= b 0) 0
      (ash (* 95 (+ b (ash (+ (* 110 (truncate a b) a) 128) -8))) -9))))

Course from one point to another

The routine course calculates the course from one GPS coordinate to another:

(defun course (from to)
  (let* ((dxdy (cartesian from to))
         (dx (first dxdy))
         (dy (second dxdy))
         (adx (abs dx))
         (ady (abs dy))
         (c (cond
             ((zerop adx) 0)
             ((< adx ady) (course2 adx ady))
             (t (- 90 (course2 ady adx))))))
    (cond
     ((and (<= dx 0) (< dy 0)) c)
     ((and (< dx 0) (>= dy 0)) (- 180 c))
     ((and (>= dx 0) (>= dy 0)) (+ 180 c))
     (t (- 360 c)))))

It returns the result in degrees, from 0 to 359. It uses this auxiliary function, course2:

(defun course2 (adx ady)
  (truncate (* adx (+ 45 (truncate (* 16 (- ady adx)) ady))) ady))

Cardinal direction

Finally, cardinal gives the cardinal direction from a direction in degrees:

(defun cardinal (dir)
  (logand (truncate (+ (* 2 dir) 45) 90) #x7))

This returns 0=N, 1=NE, 2=E, 3=SE, 4=S, 5=SW, 6=W, or 7=NW.

Converting the GPS coordinates

The navigator first needs to read the string version of the GPS coordinates, and convert them to the integer units we are using, dimiminutes. It uses the function angular to do this:

(defun angular (n lst)
  (let ((str (nth n lst))
        (dir (nth (1+ n) lst)))
    (let* ((len (length str))
           (deg (read-from-string (subseq str 0 (- len 8))))
           (min (read-from-string (subseq str (- len 8) (- len 6))))
           (fra (read-from-string (subseq str (- len 5) (- len 1))))
           (sgn (if (or (string= dir "N") (string= dir "E")) 1 -1)))
      (* (+ (* (+ (* deg 60) min) 10000) fra) sgn))))

It assumes the GSP module gives the latitude and longitude with 5 decimal places. You’ll need to modify it slightly if your module is different.

You can test it as follows. To display the latitude in decimal degrees call:

(echo (lambda (lst) (print (dimiminute-degree (angular 2 lst)))))

and to display the longitude call:

(echo (lambda (lst) (print (dimiminute-degree (angular 4 lst)))))

Displaying the distance and direction

The final routine, dist-direction, displays the distance from home and an arrowhead icon showing the direction you need to travel to get there, calling the routine show I defined earlier to show it on the seven-segment displays:

(defun dist-direction (lst)
  (when (string= (second lst) "A")
    (let ((coord (list (angular 2 lst) (angular 4 lst))))
      (cond
       ((null *home*) (setq *home* coord))
       (t (let* ((dist (distance coord *home*))
                 (wayhome (course coord *home*))
                 (gpscourse (nth 7 lst))
                 (skm (princ-to-string (truncate dist 1000)))
                 (sdist (princ-to-string (+ dist 1000)))
                 (seg #x00))
            (when gpscourse
                 (let* ((dir (read-from-string 
                              (subseq gpscourse 0 (- (length gpscourse) 3))))
                        (correction (mod (- wayhome dir -360) 360)))
                   (setq seg (nth (cardinal correction) *segs*))))
            (cmd #x9 #x7F) ; Custom segment pattern for leftmost display
            (show
             (concatenate
              'string
              (align 3 skm)
              skm
              "."
              (subseq sdist (- (length sdist) 3))))
            (cmd 8 seg)))))))

The coordinates of the starting position are stored in *home*:

(defvar *home* nil)

If your application is a treasure hunt, set *home* to the coordinates of the treasure. For example:

(defvar *home* (list (degree-dimiminute 37.9161) (degree-dimiminute -85.9562)))

The function dist-direction first checks that the status field is “A”, indicating that the latitude and longitude strings are valid. Then it calculates the distance and course, and formats them for the display.

The rightmost six displays will show the distance, in km, to the nearest metre.

The leftmost display will show the direction from your current position to home. To calculate this it subtracts your current course, given by the course parameter in the RMC sentence, from the course between your current GPS position and *home*. The resulting direction is converted to one of 8 segment patterns representing the direction:

(defvar *segs* '(#x62 #x60 #x61 #x21 #x23 #x03 #x43 #x42))

Note that when you’re stationary the GPS module can’t calculate the course, so the leftmost display is blanked.

I took the Simple GPS Navigator for a walk around my neighbourhood to check that it was working correctly.

Making a stand-alone version

Finally, here’s a function go3 that runs the Simple GPS Navigator:

(defun go3 () (on 15) (show "-- --.---") (echo dist-direction))

As before, save the image using:

(save-image 'go3)

The application will then run automatically on reset.

Here’s the full listing: Simple GPS Navigator program.