Fixed Point - GPS Decimal Degrees

Posted on November 21, 2017 by Jimmy Carter

This posts is intended as an introduction to working with fixed point numbers. In working on a recent project I wanted to save code space by not using floating point operations. I needed to do math on latitude and longitude reported by a GPS. I explain my process here.

In the past month I’ve been working on a small, cheap, disposable telemetry board with the idea that if the flights are cheaper it will be easier to fly them more often. I also just wanted to play around with ASK on ham radio, and possibly use this for other cheap telemetry projects in the future.

The project is based on the MAX1472 ASK transmitter, an ATtiny4313, a LPS25HB barometric pressure sensor, a PCT2075 temperature sensor, and a LTR-329ALS-01 ambient light sensor. Optionally a GPS can be added for precision location data. The whole thing runs off of a single AAA and uses a boost converter to raise this to 3.3V.

Currently I’m building the board up slowly. I have it transmitting packets and reporting temperature. For the pressure sensor and ambient light sensor I have to reflow the parts for which I’m building a Controleo3 reflow oven, but that’s another project!

I decided to try and reduce the size of the transmitted packets by using a binary format. For GPS location, after parsing, we have to convert ASCII latitude and longitude to a binary representation of the numbers. I’ve decided to use a decimal degrees format. NEMA 0183 protocol gives us a degrees decimal minutes location.

Fixed point primer.

Fixed point arithmetic is a way to represent integer fractions. Not all decimal numbers can be represented by fixed point so when using fixed point there often is a loss of some resolution but this can be made arbitrarily small.

With fixed point we have integer and fractional bits. The integer bits count up just like you’re used to. The least significant bit is 2^0 every digit to the right of that is 2^n counting up.

The fractional bits add digits to the right counting down: 2^-1, 2^-2 etc. Ex:

Binary Decimal
0.1 0.5
0.01 0.25
0.001 .125
0.101 0.625

Usually we note how many fractional bits there are with Q notation: a Q followed by the number of fractional bits we have (this locates the radix point). If we have three fractional bits we would say Q3. I also enjoy noting how many bits I’m using for the integer numbers. This is done with Q, the number of integer bits, a period, the number of fractional bits. If we had 8 bits for integers and 12 bits for the fractional content: Q8.12. This last notation is what I’ll use.

-Some notes-

Adding/Subtracting: If we add or subtract two fixed point numbers they should have the same number of fractional bits.

Multiplication: When we multiply two fixed point numbers we end up with a number that has the sum of the fractional digits. ( Q0.8*Q0.8 = Q0.16 )

Choosing a fixed point format

I wanted to have a resolution down to 1m which is about 1E-5 degrees. Latitude is +-90 and longitude +-180. This means we need

log2(9000000) = 23.1015

and

log2(18000000) = 24.1015

bits for each respectively. I used 25 bits and decided on Q8.17 fixed point for the data representation. With 17 fractional bits we have a resolution to 0.763E-5 degrees, slightly better than our 1E-5 target.

Conversion to fixed point.

To convert degrees minutes we need to take the minutes, divide by 60, and add the result to the degrees:

Decimal Degrees = Degrees + Minutes/60

I take the location from the GPS as three separate parts: degrees, minutes, and decimal minutes. I’ll denote this as D M and m respectively. When parsing I take the first five digits of m. I need to divide this by 1E5 to scale it back to minutes.

My formula is thus:

Dd = D + M/60 + m/1E5/60

I notice that M should always be less than 60 and m less than 99999.

Calculating M/60.

To get plenty of resolution I use Q0.32 for my division. This is a resolution of 2.33E-10. I don’t need any integer digits because this number should always be less than 1. To divide M we multiply by 1/60 in Q0.32.

factor1 = (1/60) * (2^32) = 71582788.26666 = 71582788

We round for an integer number. Now we can multiply M by this factor and our result will be M/60 in Q0.32.

M/60 = M * factor1 (in Q0.32)

To show that this works let’s show a quick example. Say we had a value of 42 minutes:

M * factor1
42 * 71582788
3006477107 (in Q0.32)

We divide 3006477107 by 2^32 to convert back to decimal representation:

3006477107 / (2^32) = 0.699999999953434

Now 42/60 = 0.7 . This is a difference of 4.6566E−11 or well within our desired resolution of 1E-5. In fixed point we have traded exactness for speed of execution.

Conversion from Q0.32 to Q0.17 is painless as we just shift the result down 15 bits. We don’t care about those last 15 bits as they are more resolution than we need and simply discarded in this operation.

Calculating m/1E5/60

This second calculation is much the same as above but adds one additional step.

To achieve the resolution desired again we use Q0.32 format for our divisions. To divide by 1E5 we will multiply by 1/1E5 as represented in Q0.32.

factor2 = 42949.67296 = 42950

Rounding here again for an integer number. In our previous step we found 1/60 in Q0.32 which was 71582788.

When we combine the two Q0.32 multiplications our result will be in Q0.64. We will eventually convert this to Q0.17 with a large downshift.

Combining these produces:

m/(1E5)/60 = m * 42950 * 71582788 (in Q0.64)

Again to show this works let’s try an example. Say we had 98765 as our decimal part of the minutes reported by the GPS.

98765 * 42950 * 71582788 = 303651090740419000 (in Q0.64)

Dividing this by 2^64 to show the decimal result:

0.0164609586129177…

Checking:

98765/1E5/60 = 0.016460833333

This is a difference of about 1.252796E-7 which is again within our desired resolution of 1E-5.

Putting it all together.

We now have three numbers, all now degrees, in three formats:

Number Format
D Q8.0
M/60 Q0.32
m/1E5/60 Q0.64

We will shift m, the contribution from decimal minutes, down 32 bits so we can add it to M. After adding these together we will shift this number down 15 to end at Q0.17.

We need to add this decimal degree result to our degrees and end in Q8.17 so we shift D up by 17, as them together, and we are done! Decimal degrees in Q8.17, enough for a resolution of 1m!

In C all of this comes to:

``latitude = (D<<17) + (((M*factor1) + ((m*factor2*factor1)>>32))>>15);``

where `factor1` is 71582788 and `factor2` is 42950.

Just remember to use datatypes that are large enough to not overflow!

This was a bit verbose but I hope it helps in your fixed point endeavors and was a good introduction. Enjoy!

KG4SGP - Jimmy Carter

Found an error? Contact me and let me know! :)