Building a GPS Receiver, Part 4: Measuring Twice

We’re plotting the satellite’s orbit according to the data the satellite is sending, but the resulting orbit is clearly nonsense.

My first instinct was to track down where I was parsing the data format incorrectly. To my dismay, these bits are what the satellites are beaming down, and I was pretty sure I was parsing the data fields correctly.

Next line of attack: I knew that the satellites also transmitted parity bits for error detection. I had been ignoring these parity bits up to now. Perhaps it’s a good time to check against them?

Parity bits

As it turns out, the parity aren’t just an out-of-band error detection mechanism. Instead, they’re an integral part of the message itself. To decode the bits coming from the satellite, you need to run the data bits and parity bits you’ve received through a small state machine.

The actual formula for decoding the bits is a tad arcane, and the state machine advances temporally as bits are received from the satellites^✱.

All done, look at those gorgeous orbits!

Computing satellite positions

OK, we’ve got each satellite’s orbital parameters at some reference time, which is a few hours in the past or future relative to the current time^✱. How do we turn that into the satellite’s current position?

The GPS specification gives us a lucky break, and actually provides the exact equations needed to compute the current satellite position. Just one problem: they look terrifying.

A large part of the effort here was just working up the courage to trust the spec and implement the equations as written.

Once I had the satellite positions at the precise moments the satellite signals were transmitted^✱, finding the position of the user was just^✱ a matter of solving which positions could have resulted in the observed time delays^✱ for the known satellite positions.

Just one problem. My receiver said I was way past the moon’s orbit, and (I could be mistaken here) that’s not where I am.

This took a while to track down, and I’m sort of shocked that the root cause isn’t called out more explicitly in the GPS specification.

Take a look at the these equations provided by the spec. These are used to compute a satellite’s Keplerian orbital elements:

Some values mentioned in these equations come directly from the satellite’s navigation message, where they’re defined like so:

This satellite data format also includes the following unit definitions:

There’s a horribly insidious gotcha between these three diagrams, separated by dozens of pages of dense spec. Have you spotted it? Yeah, me neither.

Many values given in the satellite data are expressed in semicircles. By the time they’re used in the equations, the values have implicitly been converted to radians. It’s up to the receiver software to convert the units. The only way to catch this is to stare at the relationships between these equations as you cry yourself to sleep^✱.

Hey ho, there’s a lot of complexity. Who can fault poor pedagogy in a military specification? But the military didn’t stop there. It’s one thing to publish a specification with unintentional footguns. It’s entirely another to intentionally hobble the accuracy that civilians can achieve while using GPS.

Selective Availability

For a large part of the GPS history, the United States military intentionally reduced the accuracy of navigation data delivered by the C/A code (i.e. civilian-usable GPS). To my understanding, this was accomplished via two mechanisms – both of which involve intentionally degrading the navigation message.

1. Fuzz the clock correction in the navigation message.
   • One important field of the navigation message is the bit where the satellite says “here’s what time it is”. This field is expressed in seconds. Since these satellites carry extremely precise, and fairly aged, space-bound atomic clocks, this timestamp needs to be corrected by a factor far less than a full second. Another field in the navigation message gives this correction, and it’s this field that was intentionally deviated from its true value.
2. Reduce the accuracy of the satellite ephemeris data.
   • Even simple negligence in updating the accurate positions of the satellites in their orbits can have wide-ranging effects for the accuracy of GPS. By neglecting to regularly update, or by slightly nudging, the orbital parameters that the satellites report, the U.S. military could precisely control a factor of imprecision for each satellite’s derivable position.

The military gave itself the ability to fuzz both “Here I am” and “here’s what time it is”. These two techniques boil down to the same goal: if the user has less accurate info on where the satellite is and what the precise time is, they will be mathematically unable to solve for their exact position^✱.

Selective Availability was originally thought to be a good idea because it meant that the U.S. military could have control over who could precisely determine their geolocation. Eventually, though, it was decided to turn Selective Availability off for good.

What about the security benefits Selective Availability provided, though? Not to worry, says military:

The United States has no intent to ever use SA again. To ensure that potential adversaries do not use GPS, the military is dedicated to the development and deployment of regional denial capabilities in lieu of global degradation.

Out of all the phrases that have ever been meant to be reassuring, that must be one of the most terrifying. My “I have developed advanced capabilities that allow me to selectively drown out GPS in a given terrestrial region” T-shirt is raising a lot of questions that are answered by my shirt.

Honing in

Back on track: we’re computing the satellite’s current positions, and using this to solve the geometric solution for our position and local clock bias.

All of a sudden, we’re in… Antarctica?

Hmm. It can certainly get chilly in the UK, but I think that’s a touch dramatic.

Here begins a long quest of tracking down errors within my GPS receiver’s software stack. As a reminder, the GPS position solution is completely and solely determined by the relative time it takes for each satellite’s signal to arrive at the receiver. Different combinations of time delays yield different geometric solutions for the receiver’s position.

If my receiver is spitting out inaccurate position readings, it’ll be because I’m making some error when handling the timing material.

It might seem easy to say “this signal arrived from that satellite at this time”. It’s actually quite tough.

GPS, fundamentally, assumes that the receiver has some cheap and inaccurate clock, and doesn’t depend on it at all for timings. The current time, and the relative timings between the signals from each satellite, are derived entirely from the signals sent by the satellites^✱.

However, the receiver doesn’t magically have access to these timings! We’ve built up layers of strata between the raw radio signals that arrive from the satellites, to the decoded time data that they contain. We pass through the signal tracker, pseudosymbol aggregation and queuing, bit phase selection, and subframe phase selection, and if any of these stages don’t perfectly encapsulate the precise time that their associated signals were received, our positioning solution will be wildly incorrect.

Thanks to days of careful tweaking, we slowly make our way up to the southern tip of Africa…

Take a detour through the Americas…

Fish for salmon in the North Sea…

Before finally settling down back home at my true location^✱!

Wrap up

I started this project with absolutely no background in digital signal processing, radio technology, or GPS.

I am left stunned by the genius of the people who created this system, and the genius of those whose work they built upon. GPS demonstrates incredible foresight and ingenuity on part of its architects. We truly live on the shoulders of giants.

Just to list a few of the deep fields and ideas that GPS directly leverages:

• Rocket science and orbital mechanics
• Signal carrier recovery and the Costas loop
• Relativity and time dilation
• Geodesy
• Heterodyne RF receivers
• Atomic timekeeping
• Error detecting codes
• Network synchronisation
• Pseudo-random noise sequences
• Spread-spectrum radio transmission
• Code-division multiple access systems
• High auto-correlation, low cross-correlation sequences
• Military security on publicly broadcasted signals
• Operating a satellite fleet
• Atmospheric science

The system designers anticipated wild, and legitimate, problems, and built the solutions into the GPS specification and data format preemptively.

Writing a homegrown GPS receiver was quite difficult, but worth it. Thanks to months of dedicated work, I can now say with confidence that I am somewhere in England^✱!

gypsum’s code is here. Here’s a demo showing the web-based satellite tracking dashboard in action.