[Ovmsdev] SIM808/SIM908 GPS accuracy

[HONDA S-2000]

Sorry to reply to my own (long) message, but I overlooked a few things in my writeup.

I already realized that 32-bit float is limited to between 6 and 9 decimal digits of precision. The reason it varies across such a wide range (6 to 9) is that decimal fractions and binary fractions do not always convert precisely. So, that range really represents worst case and best case limits. This is important because latitude and longitude are reported in decimal degrees and minutes, not binary.

Anyway, there's no way that the SIM908 format of DDDMM.MMMMMM can be represented in 32-bit float without loss of precision. Not even the SIM808 format of DDD.DDDDDD can be represented in 32-bit float, because 9 digits is the best case and isn't always guaranteed. 32-bit float can handle about DDD.DDD, and I haven't taken the time to see how many digits of DDDMM.M… can be handled. You are correct that 64-bit double would handle this easily, except for the fact that the PIC doesn't easily support 64-bit double.

So, while 32-bit float can accurately convert a 0.000001 minute arc to meters as a relative distance, it cannot maintain that precision with larger degrees.

Without getting further distracted, there are math libraries which work on strings of decimal digits, rather than binary words. With such a library, it is probably possible to handle DDDMM.MMMMMM without any loss (but, as you say, is it really necessary to calculate to centimeter accuracy when the open GPS technology is not that precise?).

Finally, to satisfy my curiosity, what are the latitude and longitude angles being converted to? I can see how they can be converted to distance in meters on the surface of the Earth, but those distances would have to be relative to a known position like the North Pole or the Greenwich longitude line. Are maps really using those references? … or does each map have a local reference position where all other positions are relative in degrees and minutes? If the latter case, then some of the burden of resolution is relaxed, since any given map would not cover more than a small number of degrees.

Brian Willoughby
Sound Consulting


On Feb 6, 2017, at 9:33 PM, HONDA S-2000 <s2000 at audiobanshee.com> wrote:
> I don't have a PhD on this topic, either, so here's my best shot.
> 
> Please note that floating point numbers only represent a potential for loss of precision when adding very large numbers to very small numbers. In those cases, the very small numbers can completely disappear from the total. Multiplication doesn't affect the precision at all - nothing is usually lost because there are rarely that many significant digits to start with.
> 
> I briefly got distracted by the calculations done within the GPS unit itself, even though they're not the same calculations that are done of the latitude+longitude results. If you'll indulge the distraction, it might illuminate the subject. Navigation equations involve calculating the square root of a sum of several squares and a product involving the speed of light. The speed of light is defined as 299,792,458 meters per second. That number cannot be represented in 32-bit - it becomes 299,792,448 meters per second, for a loss of 10 meters per second. That might seem rather large, but many scientific calculations approximate the speed of light as 300,000,000 meters per second, which is off by 207,542 meters. Note that the common approximation is four orders of magnitude larger than the loss of precision due to 32-bit float. So, basically, if you're starting with fewer digits of precision in the first place, then floating point is not going to cause any additional loss of precision. However, if you need the full precision of the speed of light, as an example, then 32-bit floating point starts out with a loss of precision (but at least it doesn't get any worse after that).
> 
> Getting back to the positioning, it looks to me like the resolution would be in millimeters, even with 32-bit float. The SIM908 format of DDDMM.MMMMMM would seem to allow for the smallest angle (of 0 degrees, 0.000001 minutes) to be precise to 0.00185531 meters, or 1.85531 millimeters. That number can be obtained with 32-bit float as precisely as with 64-bit float. The largest angle of 180 degrees corresponds to 20037392.103861 meters as a double, or 20037392.0 meters as a float. Thus, using 32-bit float seems to mean that the worst case latitude error would be 0.1 meters or a centimeter. Sounds like you may have come to the same conclusion, unless I misread your message. I assume that for longitude it could be twice as bad (2 centimeters!) in parts of the world.
> 
> I do not follow your comments about the scaling factor of 3600*2048. Floating point does not lose accuracy when scaled - at least not unless small, unscaled values are added to large (scaled) values with the expectation that those small values will be retained. I haven't looked at all of the code, but where does the 3600*2048 scaling factor come into play? Maybe I just misunderstand what you're referring to. I disagree that every floating point calculation causes additional errors. Can you explain how you came to that conclusion?
> 
> It's standard scientific and engineering practice to assume that the precision of any final product is no greater than the precision of any input factor. Apart from the example of the speed of light, which is more precise than 32-bit float can represent, I can't see any numbers in the realm of GPS calculations that would lose precision. And, even with the speed of light, once the precision is reduced to fit within 32-bit float at the beginning of the calculations, there would be no further loss of precision - at least not in terms of standard, accepted scientific and engineering precision. Floating point is actually great for just this sort of thing.
> 
> Brian Willoughby
> Sound Consulting
> 
> 
> On Feb 6, 2017, at 6:00 PM, Edward Cheeseman <cheesemanedward at gmail.com> wrote:
>> Float gets slightly worse when it gets multiplied by 3600*2048.
>> 
>> 180*3600*2048 = 1327104000, represented in IEEE754 as 0x4E9E3400. 0x4E9E33FF is 1327103872, 128 less, giving a resolution of 1.9meters
>> Every calculation with float can cause 1m order errors. Having resolution in the centimetre range puts calculation error well under the inaccuracy of the GPS.
>> 
>> This is still only critical if you need to know which lane you are in :)
>> 
>> 
>> Oh, good time to point out that C18 actually doesn’t follow IEEE754 exactly: rather than the usual [sign, exponent, fraction] notation, it swaps the bit order to [exponent, sign, fraction].
>> I can kind of see why - with the 8bit processor, having the 8 bit exponent aligned with the MSbyte could save a number of bit shift operations among many other byte aligned actions.
>> Sign becomes the MSB of the three remaining bytes.
>> I wonder if this is the source of error in the original atof()?
>> 
>> On 7/02/2017, at 12:47 PM, Edward Cheeseman wrote:
>>> So, while I’ve dabbled in this stuff I didn’t get a PhD in its analysis! Lets give it a go: (please point out any errors found)
>>> 
>>> ---------
>>> OVMS native format:
>>> Appears to be signed seconds * 2048. I haven’t delved into documentation here, just what I saw in the gps2latlon().
>>> Circumference at Equator is worst case. So a native unit represents a maximum of 40,075,017m / ( 360d * 60m * 60s *2048) = 15mm.
>>> Certainly enough, and just fits into 32bit at 31.3bits. Looks like someone designed it that way.
>>> 
>>> Floating point number accuracy:
>>> Worst case accuracy is at 180degrees. IEEE754 binary32 is: 0x43340000 -> +(s) 0x86(e) 0x340000(f). One less is 0x4333FFFF -> 179.999985 degrees. 
>>> Worst case resolution is 0.000015 degrees or 40,075,017(m) / 360(d) * 0.000015(d) = 1.670m
>>> By implied bit, I gather this relates to the fact that at close to 0degrees, the precision would be much greater. I live near 180degrees so this has less relevance to me than say someone in the UK.
>>> 
>>> SIM908 reports DDDMM.MMMMMM, a resolution of 0.0000000167 degrees or 1.9mm
>>> SIM808 reports DDD.DDDDDD, a resolution of 0.000001 degrees or 111mm
>>> 
>>> Clearly going through floating point is throwing away some information, but there is no way we can use all the resolution reported by the SIM908.
>>> 
>>> Is this worth the reduction in code readability (and maintainability)?
>>> is the integer math any better? On the SIM908 version, the worst I’ve seen is 0.00000025deg error -> 28mm. That’s not to say I’ve done much testing by any means.
>>> 
>>> Adopting the change probably comes down to other considerations than resolution.
>>> 
>>> Edward
>>> 
>>> On 7/02/2017, at 10:53 AM, Brian wrote:
>>>> 32-bit float does indeed store 23 bits of significand, but there is an additional implicit bit, making the total 24 bits. When you also consider the separate sign bit, 32-bit float has as much precision as a 25-bit signed fixed-point integer.
>>>> 
>>>> Adjusting your math without any other adjustments, that would imply a resolution of 1.2 meters and perhaps 2.5 meters unrounded.
>>>> 
>>>> However, I don't quite follow your calculations since floating point always carries a certain number of significant digits, regardless of the exponent. Can you show why the circumference divided by a fixed precision would reflect the ability and precision of a floating point calculation? It's a snowy day here, and I don't have my floating point thinking cap…