GPS resolution planning & Floating Point Avoidance

Avoiding Floats

So, the ARM Cortex M3 processor does not include an FPU.  Any floating point operations would require emulation libraries to be linked in and used.  This increases the size of the code and reduces performance.  Thus, I'm trying to avoid floating point math in the tracker.

GPS Strings

The GPS strings include latitude and longitude which are presumed to be floating point.

$GPGGA,204403.00,4226.59508,N,07628.88487,W,1,06,2.83,283.3,M,-34.5,M,,*66

These numbers need to be converted to decimal degrees for use in grid square math, and also for the math used by the geofencing code.  They have a fair amount of precision, but the question is "How much do we need?"

Grid Square Precision

A 6-character grid square has a precision of about 3x4 miles.   Each degree of latitude and longitude is about 69 miles.  So, if we used 1/10th of a degree resolution, we would have a resolution of about 7 miles.  That's not sufficient.  However, if we use 1/100th of a degree, we would then have a resolution of about 0.69 miles.  That's more than adequate for a 6 character grid square.

Geofencing precision

The generally available geofencing polygons are composed of relatively few points enclosing the countries on the map.  They're not drawn with a great deal of precision near the borders.  A resolution of 0.69 miles should be sufficient to fence off areas in which transmission is prohibited.   So, 1/100th of a degree would work fine here, as well.

Assuring 1/100 degree is safe for int32_t

The latitude and longitude numbers, when in decimal degree will range from -180.00 to 180.00.  By shifting the decimal point two places, we can represent these as integer values from -18000 to 18000.

Grid square calculations begin with the latitude and longitude and do divisions and modulo operations to build the grid square representation. Those won't present any difficulties for 32 bit integer math.

The Geofencing logic is more complicated.  The heart of the "PointInPoly" routine, used by the geofencing logic, looks like this:

if ( ((verty[i]>testy) != (verty[j]>testy)) &&
    (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
         c = !c;

I want to remove the division.  There's a risk that the denominator may be negative.  If it is, it will switch the case of the test from "Less Than" to "Greater Than".  Modifying the code as I implement this algebra yields this:

if  ((verty[i]>testy) != (verty[j]>testy)) {
   denominator =  verty[j]-verty[i];
   if (denominator > 0) {
      if ( (testx - vertx[i]) * denominator < (testy-verty[i]) ) {
         c = !c;
      }
   } else if ( (testx - vertx[i]) * denominator > (testy-verty[i]) ) {
      c = !c;
   }
}

Denominator worst case:  18000 - -18000 == 36000

So, the worst case math is this:

(testx - vertx[i]) * denominator

IE:  

(( 18000 --18000) * 36000) == 36000 * 36000 = 1,296,000,000

The max value of a signed 32 bit integer is:

2^^31 == 2,147,483,647

So, the worst case scanario in the PointInPoly routine, assuming we use integers from -18,000 to 18,000, fits comfortably inside a 32 bit signed number.

Conclusion

I'll be using Latitude and Longitude to the 1/100th of a degree. I'll represent the values as signed 32 bit integers by multiplying the values by 100 and rounding.  By doing so, I can completely avoid using floating point math and/or 64 bit numbers.  This should keep the tracker code lean and mean.

Borrowed routines for SI5351 and WSPR encoding

Borrowed routines

The interwebz are a wonderful place.  People publish their software for others to use.  I took advantage of this to get a driver for the Si5351 chip, and also to find code to encode my WSPR strings.

SI5351 library

I ported code written by Jason Milldrum & Dana H. Myers.  This code was written for Arduino. Fortunately, the Arduino specifics were isolated to a few functions.  

si5351_read

si5351_write

si5351_write_bulk

One little issue that I ran into was that the I2C bus address in arduino is automatically shifted by the Arduino libraries, but it is not by the HAL libraries for STM.  So, where these routines used "addr", I basically had to use "addr <<1".

I had some initial issues with timing in I2C.  Things would work fine if I had lots of debugging turned on, but would fail if I removed debugging.  Then, I found a sparsely documented HAL_I2C_IsDeviceReady() routine.  By adding this call before all of my I2C reads and writes, the problems cleared up.  At some point, I'll investigate this more thoroughly to make sure that I understand exactly what the issue was.

Below is a before/after sample of one of the changes to get a feel for the changes required:

Vanilla:

uint8_t Si5351::si5351_read(uint8_t addr)

{

uint8_t reg_val;

Wire.beginTransmission(SI5351_BUS_BASE_ADDR);

Wire.write(addr);

Wire.endTransmission();

Wire.requestFrom(SI5351_BUS_BASE_ADDR, 1, false);

while(Wire.available())

{

reg_val = Wire.read();

}

return reg_val;

}

My Version:

uint8_t Si5351::si5351_read(uint8_t addr)
{
uint8_t buffer[] = {addr};
uint8_t value;

    if (HAL_I2C_IsDeviceReady(&Globals.I2cHandle, (uint16_t)SI5351_BUS_BASE_ADDR<<1, 2, I2CTIMEOUT) != HAL_OK) {
    Error_Handler();
    }

while(HAL_I2C_Master_Transmit(&Globals.I2cHandle, (uint16_t)SI5351_BUS_BASE_ADDR<<1, (uint8_t*)&buffer, sizeof(buffer), I2CTIMEOUT)!= HAL_OK)
{
/* Error_Handler() function is called when Timeout error occurs.
      When Acknowledge failure occurs (Slave don't acknowledge it's address)
      Master restarts communication */
   if (HAL_I2C_GetError(&Globals.I2cHandle) != HAL_I2C_ERROR_AF)
   {
    Error_Handler();
   }
}

    if (HAL_I2C_IsDeviceReady(&Globals.I2cHandle, (uint16_t)SI5351_BUS_BASE_ADDR<<1, 2, I2CTIMEOUT) != HAL_OK) {
    Error_Handler();
    }

while(HAL_I2C_Master_Receive(&Globals.I2cHandle, (uint16_t)SI5351_BUS_BASE_ADDR<<1, (uint8_t *)&value, 1, I2CTIMEOUT) != HAL_OK)
{
/* Error_Handler() function is called when Timeout error occurs.
          When Acknowledge failure occurs (Slave don't acknowledge it's address)
          Master restarts communication */
if (HAL_I2C_GetError(&Globals.I2cHandle) != HAL_I2C_ERROR_AF)
{
Error_Handler();
}
  }

  return value;
}

WSPR Encoding routine

I poked around and found a few different options for WSPR encoding.  I found some truly wretched code in a few Arduino samples I found.  I'm always nervous about code with malloc() and free() calls.  One particularly good looking implementation, however, includes support for JT65, JT9, JT4 and WSPR can be found at this link right here.

Ultimately, though, being the contrarian that I am, I found an even leaner and meaner encoding routine written by Mark VandeWettering called "genwspr".

The code is VERY small and lean, with no malloc() or free() calls, which made me happy.  I can't say that I understand it one tiny bit, but it creates a tone array of values to use for making the WSPR signal.  It was trivial to just pick up his code and port it into my project. 

I was able to take the output of his routine and compare it to output from the "wsprcode.exe" program documented in the WSPR_2.0 User manual, and found it matched exactly.  Good 'nuff for me!

Wisp1 Telemetry Revisited

Wisp1 Telemetry Revisited

So, in my previous blog post about telemetry, I outlined a WSPR telemetry scheme to maximize the amount of data packed into the few bits available.  Alan Adamson (W7QO) and I were both thinking of using it.  However, after some initial implementation, Alan realized it required a hefty bit of coding.  He counter-proposed a more "positional" concept.  We went back and forth for a day or two, and came up with the scheme below.  It's agreeable to both of us, so we each intend to use it on our trackers.  Since he did the heavy lifting with most of the design, I'm writing it up for the interwebz to enjoy.

First Packet

     KD2EAT FN12 37

The fields include Callsign, Grid locator, and a power level.  There are 19 discrete values permitted in in the power level field.

The first modification is to re-purpose the power level field in the WSPR packet as an "Altitude" indicator. Each of the 19 discrete values will represent 1000 meters of altitude.   The altitude mapping ends up looking like this:

DBM	Encoded Altitude Meters
0	0
3	1,000
7	2,000
10	3,000
13	4,000
17	5,000
20	6,000
23	7,000
27	8,000
30	9,000
33	10,000
37	11,000
40	12,000
43	13,000
47	14,000
50	15,000
53	16,000
57	17,000
60	18,000

So, the packet above indicates that the balloon is flying at, at least, 11,000 meters.  This provides altitude data in one packet with no additional modifications to the protocol, if desired.  It provides for altitudes from 0-18,000 meters (59,055 feet).

Second Packet

This is where the rubber meets the road.  We are encoding a lot of data in the callsign field, as well as the power field.  However, the grid square field is NOT used to carry telemetry data.  This means that, though the callsign will be bogus, the telemetry data will appear in the same grid square as the primary packet.  It is assumed that the same data will be used to generate BOTH the primary and secondary packet, since the altitude encoding in the primary packet is refined by the telemetry packet.

We'll illustrate the encoding scheme by decoding an example.

     QK1SKN FN12 33

The callsign consists of 6 positions with potential values as follows:

Position	Possible Values	Use in Scheme (number of values)	Number of Used Values / Number of Possible Values
Callsign 1	Q,0	Telemetry Channel (2)	2 / 2
Callsign 2	0-9,A-Z	Battery volts (12), Altitude_fine(3)	36 / 36
Callsign 3	0-9	Telemetry Channel (10)	10 / 10
Callsign 4	A-Z	Grid Square 5th char (A-X) (24)	24 / 26
Callsign 5	A-Z	Grid Square 6th char (A-X) (24)	24 / 26
Callsign 6	A-Z, space	Temp (9), Altitude_super_fine(3)	27 / 27
Gridsquare 1	A-R	Same as Packet 1	n/a
Gridsquare 2	A-R	Same as Packet 1	n/a
Gridsquare 3	0-9	Same as Packet 1	n/a
Gridsquare 4	0-9	Same as Packet 1	n/a
DBM	0-18	Solar_volts(6), Sats(3)	18 / 19

Callsign Positions 1 & 3: Telemetry "Flight" or "Channel" number

Positions 1 & 3 allow for 2*10 = 20 possible values.  This allows for up to 20 pico flights to be in operation simultaneously without telemetry confusion, provided everyone cooperates and uses a unique pair of characters in those two positions.  In the example above, the two telemetry channel bytes are "Q" and "1". We can interpret a "Q" in position 1 as the 10's value, so this is "Flight Number 11" or "Channel 11".

Altitude encoding

Altitude is encoded across both the first and second WSPR packet.  The first WSPR packet gives us the altitude with 1 km of granularity, from 0-18,000 meters, as described above in the first packet.

The second packet, gives us two more levels of granularity:

Altitude_fine:  0, 333, 666.

Altitude_super_fine: 0, 111, 222

Balloon altitude is thus calculated by adding the three values together.  As we expand the telemetry below, we'll see in this example that:

Altitude_fine = 2, so we add 666 to the altitude.

Altitude_super_fine = 1, so we add another 111 to the altitude.

Actual Altitude = 11,000 (first packet) + 666 (second packet) + 111 (second packet) = 11,777 meters.

Callsign Position 2: Battery volts, and "fine" altitude

We encode volts and altitude fine as:

Volts	Encoded Volts
3.0 or lower	0
3.2	1
3.4	2
3.6	3
3.8	4
4.0	5
4.2	6
4.4	7
4.6	8
4.8	9
5.0	10
5.2 or higher	11

Altitude Fine	Encoded Altitude Fine
0	0
333	1
666	2

Having the two encoded values, we calculate the value for this "character" as follows:

value = (EncodedVolts * 3) + EncodedAltitudeFine.

Conversely, to get the Encoded values, you do the following:

EncodedVolts = value / 3

EncodedAltitudeFine = value % 3

The value of the second column is a letter 'A' - 'Z', or number '0' - '9'.

Encoded Value	Letter
0	0
1	1
...	...
9	9
A	10
B	11
...	...
K	20
...	...
Z	36

In our example, we have the letter "K" in position 2, which represents "20".

EncodedVolts = 20 / 3 = 6.  So, our Volts = 4.2v.

EncodedAltitudeFine = 20 % 3 = 2.  So, our AltitudeFine is 666.  Added to our 11,000 meters from the first packet, our altitude is at least 11,666 feet.

Callsign Position 4&5: Grid Square 5&6.

This is straightforward.  We simply take these two characters, and append them to the grid square. 

     QK1SKN FN12 33

"SK" is added to our grid square "FN12".  By convention, the last two characters of the grid square are in lower case, so our 6-character grid square is "FN12sk".  

Callsign Position 6: Temperature and Altitude "super fine"

This position is permitted the characters 'A' - 'Z', or a space, making 27 total values.  We reserve 9 values for Temperature, and 3 values for "super fine" altitude, as follows.

Temperature (c)	Encoded Temperature
-35 or less	0
-30	1
-25	2
-20	3
-15	4
-10	5
-5	6
0	7
5 or more	8

Altitude Super Fine	Encoded Altitude Super Fine
0	0
111	1
222	2

Having the two encoded values, we calculate the value for this "character" as follows:

value = (EncodedTemperature * 3) + EncodedAltitudeSuperFine.

Conversely, to get the Encoded values, you do the following:

EncodedTemperature = value / 3

EncodedAltitudeSuperFine = value % 3

The value of the second column is a letter 'A' - 'Z', or a space.

Encoded Value	Letter
A	0
B	1
...	...
N	13
...	...
Z	25
(space)	26

In our example, we have the letter "N" in position 6, which represents "13".

EncodedTemperature = 13 / 3 = 4.  So, our Temperature = -15c.

EncodedAltitudeSuperFine = 13 % 3 = 1.  So, our AltitudeSuperFine is 111.  Added to our 11,666 meters from above, our altitude is at least 11,777 feet.

DBM value: Solar Volts, Number of Satellites

The DBM field has 19 potential values, which we consider 0..18 (as in the Altitude table in the first packet above).  We use 18 of these 19 values.

We encode 6 values for Solar Voltage, and 3 values for Number of Satellites as follows:

Solar Volts	Encoded Solar Volts
0.2 or lower	0
0.4	1
0.6	2
0.8	3
1.0	4
1.2 or greater	5

Number of Satellites	Encoded Number of Satellites
0 or no fix	0
4 - 7	1
8 or more	2

Having the two encoded values, we calculate the value for this field as follows:

value = (EncodedSolarVolts * 3) + EncodedSatellites.

Conversely, to get the Encoded values, you do the following:

EncodedSolarVolts= value / 3

EncodedSatellites = value % 3

We follow the same DBM to Encoded Value scheme as the Altitude does in packet 1.

In our example, we have a DBM of 33, which represents a "value" of 10.

EncodedSolarVolts = 10 / 3 = 3.  Solar Volts = 0.8v.

Encoded Satellites = 10 % 3 = 1.  Satellites = 1.  4-7 satellites.