Calculating position from raw GPS data (2017) | Hacker News Reader

Calculating position from raw GPS data (2017)

telesens.co

244 pointsfanf251 comments

Android provides carrier phase access for a while now, and with that relative positioning between such devices in about the same neighborhood can be done with enough precision that you have to care about where in the device the GNSS antenna lurks.

That alone isn't too fancy; it gets good once you throw in the accelerometer and gyroscope in each device. Because with that you get this not only in realtime, but also with only minor degradation due to the changes in the GNSS pseudo-range measurements being predictable despite not holding still.

Other interesting things enabled by it are e.g. auto-land of a model plane in a truck bed without needing wheels on the plane (and still preventing it from getting scratched up/depending on a grass landing strip).

Even fairly good GNSS receivers aren't expensive to build, as long as power consumption isn't very critical, so why can't I just buy a pair for a hundred bucks?

Sounds interesting! Does this approach work in indoor scenarios? Would you mind to provide some further links/papers to this topic?

Combining GPS with accelerometer and gyroscope is sometimes called "sensor fusion" - one common way of doing it is with a "Kalman filter" and if you google that you'll find a wealth of information.

If you've got plenty of money, companies like https://www.oxts.com/ have working systems available off the shelf. They're used for things like measuring the dynamic performance of cars.

Such systems will sorta work indoors but not very well. The gyroscope/accelerometer will gradually drift; when you're outdoors with a clear view of the sky, the GPS can compensate for that but when you're indoors that isn't possible. How fast the drift happens depends on how much money you spend to get the highest performance gyroscopes and accelerometers.

It's also possible to integrate other sensors, but that's application-dependent; for a car going through a tunnel, an odometer is a great addition, for a smartphone not so much.

GPS-denied navigation is the search term. It works well enough for driving through a tunnel, because eventually you get a known location to correct previous estimates. For a fully-indoor environment it's very difficult to get good results and the technique depends on the use-case.

"Indoor GPS" using bluetooth beacons is technically possible but the space is filled with proprietary protocols/apps that try to make money by serving ads. It unfortunately doesn't seem to be evolving into a more useful extension of google maps.

For indoor, there's UWB, ultra wide band. Can also use Bluetooth or even lights blinking at different (high, non-humanly-visible) frequencies to do indoor positioning.

For indoor you will prefer UWB[0] where you can set up base stations yourself that offer a service pretty much like GNSS signals (i.e., you can passively receive them from 4+ base stations and turn those pseudoranges into a position, provided you are told where they are and kept updated about their clock drift relative to each other (e.g. by them listening to their neighbors and piggybacking 2-way-ranging sessions on top of the beacons they already broadcast, each offering the clock offset to their neighbors in the data payload of their own beacon)), with the added benefit that by using a shared-key CSPRNG to generate the bitstream of the ranging code instead of a fixed known sequence, you can get authenticated ranging where MITM attacks are limited to artificially inflating the range (i.e., a trigger of "has to be close enough to the door handle that e.g. a pair of cameras looking at the areas right in front of either side of the door have it in view" can't be faked with a wireless MITM).

There are some links/papers in the publications section[2] of [1].

[0]: https://www.firaconsortium.org/ [1]: https://developer.android.com/develop/sensors-and-location/s... [2]: https://developer.android.com/develop/sensors-and-location/s...

Can‘t you? https://www.mouser.de/ProductDetail/u-blox/ZED-F9P-02B?qs=DP...

They are 114.62 USD each if you buy at least 100 of them. And you still need to add an active antenna and a good crystal. Considering those, this module is about 3x the price I asked.

The crystal is already included. Of course you need an antenna and several other parts and most importantly communication between base and rover for correction data. Integration is the elephant in the room here. Ready to use boards go for like US$ ~ 300 (without board to board communication).

Admittedly I misread your post - you asked for $ 100 a pair. But a few hundreds is possible - at least in costs.

I misread the block diagram. It indeed only needs power communications and an antenna.

https://www.bestbuy.com/site/tracfone-blu-view-5-64gb-prepai...

Here's a GNSS receiver for $30. It comes with some other junk you don't really need though.

For anyone wanting to build their own GPS receiver, here's a fully open source project that explains a great deal of the theory too: http://www.aholme.co.uk/GPS/Main.htm

Just remember to intentionally handicap yourself as to not infringe upon ITAR restrictions.

Can you explain what you mean by that? The only thing I can think of is that GPS has 2 modes : one civilian and other military use. But military use-case uses encryption so civilians can't use that mode anyway.

GPS was built primarily for the military and the signals available for civilian use were crippled to reduce accuracy. GPS receivers that provided high accuracy fell under the ITAR rules (ie you needed proper licensing to trade them)

Over time such restrictions have largely been lifted, but there are still US export controls on GPS receivers with particular features, such as those designed for use in high speed aircraft, those able to decode the still-military-only encrypted signals that piggyback GPS and provide greater positioning precision, or those designed for use in rockets/UAVs.

So, it's reasonable to assume that if you were to build your own, and do too good of a job, you would accidentally become subject to arms trade regulations, and that's probably not a place you want to unintentionally find yourself, particularly if you're publishing it as open source on the Internet :)

> those able to decode the still-military-only encrypted signals

How? I was under the impression that military-only signal was encrypted. And if someone breaks that encrpytion, blame should go to the poor handling of encryption rather than the person breaking it? Analogy : if you leave a classified document on the train and a passenger reads it, whose fault is it?

Technological restrictions and Legal restrictions not always aligns.

That's where the "restrictions have largely been lifted" part comes in.

You can decrypt most of them, but it is illegal to export without a license.

Actually you can use the phase information in the encrypted signals to improve RTK stability, without decrypting them.

The Kraken RF project, which has multiple SDR radios next to each other, had demo code of a passive radar: the slight time delay by which signals arrived at the antennas could be used to detect large metal bodies (IOW: planes) in the sky.

They took down the demo code they were informed that they were violating ITAR regulations.

https://www.reddit.com/r/RTLSDR/comments/yu9rei/krakenrf_pul...

I'm relatively certain that the US government will be unmoved by your argument that it would be their fault if you built a GPS receiver that could decrypt the precise positioning signals ;)

Well, consider another analogy: a person leaves their door unlocked and another person goes in their home. It is still trespassing, even though the physical barrier has been intentionally disabled.

I'm not sure even what section of US code to check but it is certainly plausible that you can (for example) find a surplus device that decodes the signals on EBay and it's actually illegal to do it. You can find radios on EBay that broadcast on bands that are unlawful to use (or unlawful without certain licenses, &c).

Not GP but modern GPS / GNSS manufacturers intentionally do not allow their devices to function over some speed (1000 mph or something like that).

So they won't work on warheads as part of a guidance system.

I never really thought of that. That's a pretty interesting restriction. Although any party with access to warheads that can fly 1000+ mph probably can bypass the GPS restriction, no?

Not if they buy an off-the-shelf solution.

correct. and the idea here is to put up at least some form of barrier to entry, because any good guidance is also nuclear warhead delivery guidance at a certain point.

Just don't let some future party use your code to do it.

There was a guy in NZ (Bruce Simpson) who detailed on his blog how to make a DIY cruise missile. I think he got politely asked to stop doing so at some point.

BPS.Space on youtube is working on a DIY space-capable rocket and in a recent video he mentioned that he is not doing this as a tutorial and that his guidance system likely already wanders into ITAR territory, and thus he's self-censoring which parts he shares and which parts happen off-camera.

Ultimately these kinds of regulations are fairly silly because a sufficiently determined smart person can recreate the covered technologies from scratch, but here we are.

Any sufficiently smart person can accomplish the same original work as any other sufficiently smart person.

But when the details of these things are published or otherwise made openly available, it doesn't take nearly as many smarts to duplicate these accomplishments.

Quite often, that's good: It's easy for a dullard like me to build a circuit or to re-use some clever assembler code when someone else has published it for my own tinkering around the house. In this way, it's a pretty great world to live in; it is often very simple to stand on the shoulders of giants and get some things done that I could probably never do on my own.

But sometimes, that's bad: We don't live in a perfect world. Enemies exist. Things like ITAR can't prevent a sufficiently smart person from doing anything, but they do make it a lot harder for them to get started.

I launched a high altitude balloon as part of a summer school program over a decade ago and we checked on edge cases. Off the shelf GPS are supposed to not work beyond a certain height 18,000 m and/or speed 515 m/s to be a barrier for use as a weapon. Some hardware treat that as AND; some treat that condition as OR. The term to look up is “CoCom Limits”.

"The vast majority of civil and commercial GPS/GNSS equipment does not meet the Cat XII(d) criteria and is therefore not subject to ITAR"

https://www.space.commerce.gov/itar-controls-on-gps-gnss-rec....

Any such restrictions are trivially removed in an OSS project.

I find the project it links to (and admits to be inspired by) even more impressive: https://lea.hamradio.si/~s53mv/navsats/theory.html

It's wild reading old issues of VHF Communications and finding advertizements for buying the PCB's for this project. So I,guess people really did try to reproduce it as well.

Frequently posted in GPS comments--but for a good reason: https://ciechanow.ski/gps/

Alternate and maybe more interactive explanation: https://ciechanow.ski/gps/

Here is another good open source implementation: https://m.youtube.com/watch?v=dVD1Yws__v0

I came across a researcher working on collecting GPS data on aquatic creatures that only rarely (and for a short time) come to the surface. By recording raw data and post-processing, the power consumption and minimum duration of exposure to satellite signal are both drastically reduced (duration is under a second).

> The figure below shows how the user-source geometry affects the amount of uncertainty in the user position.

Now I'm wishing there was a setting in mapping applications on my phone that changed that the shape used for position uncertainty, from a circle to these arc-intersection shapes.

I heard that GPS is one of the few applications in daily life that needs to consider relativistic effects. So, the generated data must have already excluded these relativistic effects, right?

> So, the generated data must ..

What generated data are you talking about and who was it generated by?

If you mean the output of commercial GPS units, then yes, all manner of error inducing effects have been compensated for in post aquisition processing that generates output.

This article is about raw GPS data .. which is a collection of raw data streamed from multiple satellites that then requires processing to generate an output, and quite often additional inputs from ground stations | naval corrections to improve accuracy.

There are many different GPS instrument providers who all do broadly similar things .. the devil is in the details.

Several peer comments linked to https://ciechanow.ski/gps/ it's a good read.

from that link

> Moreover, the clocks on satellites don’t have to be explicitly slowed down to fix the cumulative relativistic speed-up of time. As part of their broadcasted message a satellite emits three coefficients that allow the receiver to correct for any offset or speed change of that satellite’s clock.

My understanding is that GPS satellites clocks are tuned to tick slow exactly to account for relativity.

For example this (https://www.nist.gov/publications/global-positioning-system-...) paper explicitly states:

> First, each GPS space vehicle (SV) clock is offset from its nominal rate by about -4.45x10^-10 (= -38 microseconds per day) to allow for the relativistic offsets between the differences between the SV and the ground. Of this -38 microseconds per day, about -45 are due to the gravitational potential difference between the SV at its mean distance and the earth's surface, and +7 to the mean SV speed, which is about 3.87 km/sec. To this mean correction, each receiver must add a term due to the eccentricity of the GPS orbit.

The "relativistic effects" is part of how GPS works.

Time ticks at different rates depending on the strength of the gravity "force", or rather the rate at which objects fall into the space-time distortion caused by mass of the earth. Time also ticks slower for objects moving at higher speeds than the observer (satellites move pretty fast). Since GPS depends on time being in sync between the observer and satellites, the time tick is offset to account for the effects of special and general relativity.

The error budget in the pseudorange to the satellites has various factors due to relativity, but they are just lumped into the errors in the least squares problem that you solve to get the position estimate (as per the article). So relativity is important, but you don't need to know much about it to solve for your position. Various flavours of long baseline/network RTK will need more sophisticated modelling though.

Next step PPP, and/or RTK. GNSS provides delightful rabbithole of possibilities.

Exercise for flat-earthers: how does the GPS mapping on your phone work, without satellites orbiting a spherical Earth? Show your work.

Your phone could do arbitrary 'magic' (ie technology) to get good positioning.

You would first need to make some kind of pretty complicated argument why your phone couldn't do this without satellites.

Somewhat easier for you, and harder for flat-earthers to push aside: the ISS is just about visible to the naked eye and definitely to someone with a backyard telescope. Similar for Starlink satellites.

If you believe hard enough that the government is trying to screw you, you could think that our taught satellite physics is a parallel construction https://en.m.wikipedia.org/wiki/Parallel_construction and the real thing actually conforms to flat earth... with enough epicycles.

In my experience, flat earthers are not capable of the kind of rigorous enquiry that would allow them to even attempt to answer this.

Flat earth isn't a position arrived at by reason, it's one that is invariably reached by either confusion, or as a necessary consequence of some unshakable core belief (typically either an extremely literal reading of the bible, or a paranoid "everything official is a lie" delusion).

Reply on news.ycombinator.com