Shortly after publishing my iOS 4 jailbreak last October[1], I got to work on my next hobby project: a from-scratch homebrew GPS receiver, which can solve the user’s location solely from billions of radio antenna samples.
I took a commodity SDR (alongside the Python standard library and numpy) and built a signal processing pipeline that can detect and track GPS satellites over many minutes, drop and pick up satellites as they come in and out of view, and precisely determine the user’s position and clock inaccuracy.
All told, gypsum can go from a cold start to a fix on the user’s position, and the precise time, in less than a minute of listening to the antenna. I went on a journey of learning how to detect and track satellite signals that are literally too quiet to hear, and I hope that some of the magic comes through in the posts!
After implementing this myself and walking the long road of getting it working, I’m left completely stunned by the brilliance of GPS, across so many axes. I hope you enjoy the read!
On a more personal note, I’ll be starting a new job next week which isn’t as amenable to publishing side projects, and therefore this will be my last publicly-published project for some time. I’ve had great experiences making and sharing projects on here, and I’m really grateful for the positive feedback that’s been shared!
This was true, but not any more. You can get truly impressive “direct RF sampling” or “direct RF conversion” receivers that are more than fast enough for GPS. For example:
Xilinx RFSoc: https://www.mouser.com/datasheet/2/903/ds889_zynq_usp_rfsoc_...
A nice National Instruments article: https://www.ni.com/en/solutions/aerospace-defense/radar-elec...
And their referenced off-the-shelf hardware: https://www.ni.com/en-us/shop/category/flexrio-custom-instru...
One might be forgiven for being a bit puzzled as to why NI thinks that direct RF conversion is cost-effective but nonetheless sells the device for $30k :) That being said, if I were prototyping a system that wanted phase-coherent wideband reception around 3 GHz and I had a proper lab and budget, I’d buy a few of these. If I were to go to production, I’d either wait for costs of a homemade board to come down a bit or see whether a traditional heterodyne receiver could do the trick.
Hmm. For military applications, if I were concerned about really advanced RF-seeking weapons pointed at me, a direct conversion receiver is probably great — there won’t be any leakage of the LO that an enemy device could try to detect.
Why would an LO be more of an issue than your sample clock?
edit: missing word
Whenever I see "from scratch," I'm always curious to see how from scratch the author actually means so I'll admit I was a bit disappointed to see that the hardware was just RTL-SDR. Still, the protocol decoding was very interesting and the result is great.
> GPS was launched in 1978, which was 45 years ago at time of writing. Five billion people are currently under 40 years old, so well over half the world’s population has never existed in an environment but this.
A note based on this. While GPS was around since 1978 the signal was intentionally degraded with a process known as "selective availability" until 2000. This largely rendered GPS unusable for many many purposes, definitely useless for road navigation, it had some limited utility in areas like backcountry navigation and was definitely useful for marine navigation.
> gypsum can go from a cold start to a fix on the user’s position, and the precise time, in less than a minute of listening to the antenna
This is very impressive and outclasses what I see even commercial receivers doing today, do you have any idea how? I remember on road trips in the early 2000s I would have to sit on the side of the road and wait for the GPS receiver to get a fix (a 15-20 minute process, when it worked) before we could leave. Or, more likely, my mother would just start driving with paper maps.
I would like to point out the insanely good design of the GPS radio layer (the L1+L2 signals).
Even 46 years on, the radio layer is fully forwards and backwards compatible, and a bunch of important metrics like time to first fix and user equivalent range errors have both improved by factors of 10-1000, with no incompatible change needed to the protocol.
The total RF transmit power to provide service to the whole earth is less than the electricity consumption of a typical US house (far less than 5G or TV or AM/FM radio), and well below the noise floor. That's possible due to clever use of stacked gold codes.
The design has allowed frequency-sharing with competing systems (eg. Galileo) - you don't see mobile phone networks doing that!
The actual signal sent has allowed things like carrier phase decoding, due to the locking of the phase between the modulated data and the carrier, which in turn gives far better pseudoranges and accuracy.
Overall, the designers either had incredible forethought, or incredible luck, or some combination of the two.
Re. slow TTFF, or time-to-first-(position)-fix on older hardware, this essentially stems from advancements in processing power.
Traditionally, GPS receivers would need to download the ‘almanac’ of all the satellites, which takes a minimum of 12.5 minutes (under certain conditions) due to the GPS data transmission format and speed. With modern processing power, though, receivers (including gypsum) can just ‘brute force’ the search space to find the in-view satellites, instead of using the hints downloaded over the air. This is the technique described at the end of Part 1.
The 12.5 minutes includes a rough multi-week almanac which you could perhaps brute force given available compute and receive capability (original GPS receivers have a single channel receiver and minute compute capability) but they more importantly include the ephemerides, precise data about exactly where the birds are and the atmospheric conditions, replaced hourly by a ground station. You can't "brute force" these - they're parameters measured by someone with objective truth like "I, a massive NASA satellite ground terminal in Florida, am definitely not moving, therefore this GPS bird #14 is 0.08 metres away from where it should be, I will adjust the data for the next hour accordingly".
Ah, the almanac part I completely forgot about, that makes a lot of sense, I read that part but forgot how it USED to be done when we couldn't just throw cycles at it.
I would disagree strongly with this. I took a roadtrip in 1999 using a Delorme Earthmate Hyperformance GPS receiver, the RS-232 version, plugged into a Toughbook running Delorme Street Atlas USA, I believe it was version 6.0.
It provided perfectly usable directions all the way across the country. It didn't do lane guidance (which I don't find terribly helpful anyway), but some time in advance of every turn, it would announce the turn, including the street name.
That version even had voice recognition, so you could say things like "are we there yet?" and it would announce the ETA to both the next stop and the final destination, along with current location. Lots of fun!
30 meters (typical worst-case CEP under SA) is plenty accurate for road navigation in all but the densest areas, and even then, just glance at the map. Once you're out on the open road, it's brilliant. Rock out to some mp3's until the voice pipes up with the next maneuver.
I have one of these, but don’t really know how useful it is or what I can do with it, but like all of my random antique hardware, I don’t really have any good reason to part with it either.
Do you have any ideas for what to do with it?
For that matter, what is a good GPS unit in modern times?
Somewhat surprisingly, if you went back 15-20 years, a lot of what the author is doing in software here would have been done in hardware.
GPS receivers used to market themselves by the number of tracking channels they had, as cheaper receivers might only have the hardware needed to track 6-8 satellites while a more expensive receiver might track 12.
So this software-defined receiver actually implements quite a bit of what would otherwise be hardware. And of course it can track every satellite in view.
The software-defined approach has some powerful benefits - for example, initial satellite acquisition involves calculating cross-correlation between the received signal and various gold codes. Being able to do this in the fourier domain lets you acquire signals pretty fast!
If you want a hardcore DIY GPS receiver, going right down to the transistor level, you'd probably enjoy reading https://lea.hamradio.si/~s53mv/navsats/theory.html - an 1990s era DIY GPS receiver, complete with hand-drawn schematics, hand-drawn PCBs, even a hand-made antenna.
https://en.wikipedia.org/wiki/Automotive_navigation_system. Moreover, while often not ideal in dense urban environments(modern receivers often struggle here anyways), by the late 90s differential GPS augmentation was available in cars as well, which was available in dense coastal population areas like NYC. Old auto nav systems were clunky and with overall shitty map data but they weren't "definitely useless" due to SA.
EDIT: I'll concede they were pretty bad, but SA was only one factor. With today's computing power and higher quality maps you could more easily adapt to the SA position error if it were an issue as well.
Automotive GPS systems existed pre-2000. So did dead-reckoning systems. Did people use them at the time? Some did. It was an amazing technology compared to the alternative, which was manually navigating a paper map.
But you'd often get errors large enough (50m avg) that it wouldn't accurately identify your location on roads close enough to provide accurate instructions. If you gave any of that tech to someone today to use, they'd think it was broken.
Ever since I've seen the project by Andrew Holme (mentioned in sibling comments) years ago it has been on my wish list to replicate, but analog/RF signals are dark magic to me.
Now I feel like I can skip the hard RF frontend bit and play with the software by using the SDR I already have.
That's cool, I can understand just enough about what's going on there to know I have absolutely no idea what's going on for 90% of that article. Excellent to learn from.
― Carl Sagan, Cosmos
While we're at SDRs, ITAR is also responsible for takedown of passive radar GNU Radio module made by Kraken RF team.
[1] https://www.space.commerce.gov/itar-controls-on-gps-gnss-rec...
https://hackaday.com/2022/11/19/open-source-passive-radar-ta...
[1] https://www.rtl-sdr.com/sdrdue-updated-passive-radar-softwar...
Comment thread from 2023-02-10:
> We are attempting to clarify if it is legal for us (KrakenRF, a US company that provides a physical SDR product) to also provide our own open source software that is made by us. As that could be seen as providing a full PR system.
Is the latest I found from them.
I didn't finish reading the whole thing but was curious. Is there any way of brute forcing it or some other trick to get the chipping sequence to get the P code for more precise GPS?
For those interested in the story of the development of GPS, I found “GPS Declassified” by Richard Easton to be an engaging retelling.
- GPS works even in airplane mode (while on a literal airplane) - It works without cell service, or wifi, or anything - The United States of America controls the GPS constellation, and they can (and have!) turned off GPS off certain regions at will when necessary (which has prompted other countries to launch their own GNSS constellations) - GPS satellites don't send down a location, they only send down time
I think it's a really fun exercise to do this with data you receive on your phone. Your phone has a direct link to satellite.
(side note: I recently learned the basic principles of star navigation, and while it is a completely different mechanism, it also relies very much on keeping accurate time, which I thought was a fun symmetry!)
Maybe this is a conception that some people have when their first experiences of using GPS was on a smartphone?
But my first couple GPS receivers were standalone devices without any sort of data connection, so it seems obvious to me that GPS doesn't require data.
My only exposure to GPS without data came from outdoor sports where GPS watches and PLBs are common, as are offline mapping applications. I don't think it's obvious to most casual users of GPS technology today that it is entirely independent from data connectivity.
They do send a location - to be more exact, they send rough locations of all satellites in the constellation (almanac) and precise location of themselves (ephemeris). Devices like mobile phones, however, usually get that data from other sources because it's much faster than listening to data over GPS.
All those things are neat, but mostly what I've learned is that quite a lot of people, otherwise apparently reasonably smart and competent and toting a whole stack of prestigious degrees, have ghastly flaws in their mental model of what GPS is.
Since A-GPS uses the cell tower to get the list of satellites in view, the GPS on some cellphones will keep working when cell service is lost but won't start working if cell service is unavailable.
I think this means my Samsung doesn't actually have GPS, since fallback to unassisted GPS has never worked for me (yes, I've tried waiting far longer than 15 minutes).
Maybe you can excuse a mental model that doesn't make the GPS vs A-GPS distinction, since A-GPS is often sold as GPS.
[0]https://en.wikipedia.org/wiki/Assisted_GNSS [1]https://news.ycombinator.com/item?id=40042686
(and contrary to popular belief, I think the average person is interested in understanding this, they're more motivated to understand things that actually matter to them, that are in their hands every day. A lot just have an emotional aversion to math due to bad school experiences, but they are genuinely curious)
Functionally on most devices losing network coverage renders GPS useless. I keep telling people to download OsmAnd if they want to be able to view maps on a plane or get home from their hike outside cell range. Google maps will try to cache maps to some degree nowadays but it tends to be very flakey and it seems to be very easy to accidentally get it to drop its cache when you're outside cell coverage.
Heh, but they aren't the only global positioning system out there (nor the most accurate). EU, China, India, and Russia all have their own.
The GPS almanac data they transmit is effectively location. It's not literally location, but the P code isn't literally time either.
> and they can (and have!) turned off GPS off certain regions at will when necessary
As I understand it, those capabilities are no longer present in newer (possibly all active?) GPS satellites.
Yes, and I use that to take pictures of features below my as we fly from one place to the other.
If you have a iPhone, when you land, those pictures will be associated with the place you were when the photo was shot. This enables you to locate those curious features you happen to see.
* https://www.youtube.com/playlist?list=PLGvhNIiu1ubyEOJga50LJ...
It just so happens I've got an RTL-SDR, a GPS receiver that outputs raw pseudoranges, and a signal splitter that lets me put the signal from one antenna into two receivers.
So if you like I can get the pseudoranges out of a commercial GPS receiver, and the raw signal from an RTL-SDR at the same time, which might help you pinpoint your last bit of location inaccuracy.
Would you be interested in that? Or do you consider this project complete?
What does a job have to do with publishing hobby projects?
(Other jobs may just take up a lot of energy and/or time.)
Where and how is that legal? You're supposed to be an employee, not a slave.
https://github.com/barbeau/gpstest
I've been fascinated for years how badly GPS does altitude (mean-sea-level)
in the USA they had to build an augmentation system for airplanes for altitude (WAAS)
I noticed the opposite, it always fails to locate any satellites, even when GPS is still turned on in aeroplane mode. I'm not sure why.
I didn't finish reading the whole thing but was curious. Is there any way of brute forcing it or some other trick to get the chipping sequence to get the P code for more precise GPS?
If you know whats the P code roughly is, which you can know from L1CA code and handover words, you can try using both possible W code value (its 0 or 1) and that W code practically dissappear, until the W code move to its next iteration and you need to guess again. This strategy is called semi-codeless tracking.
People did this so they can access the signals at L2 frequency (1227.6 MHz), which because its at a different frequency than L1 (1575.42 MHz), they got slowed down by different amount through the ionosphere. So by comparing the signals together, you can remove the ionospheric effects and get more accurate position.
These days you don't need all of this, GPS now have public signals at L2 and now smartphones have these fancy dual-frequency receivers
C:\dev\gps\gypsum-release>gypsum-cli.py
Traceback (most recent call last):
File "C:\dev\gps\gypsum-release\gypsum-cli.py", line 9, in <module>
from gypsum.receiver import GpsReceiver
File "C:\dev\gps\gypsum-release\gypsum\receiver.py", line 20, in <module>
from gypsum.navigation_message_decoder import EmitSubframeEvent
File "C:\dev\gps\gypsum-release\gypsum\navigation_message_decoder.py", line 8, in <module>
from gypsum.navigation_message_parser import (
File "C:\dev\gps\gypsum-release\gypsum\navigation_message_parser.py", line 62
*bits
^
SyntaxError: invalid syntaxGPS receivers will look for the 'strongest' PRN signal in the noise, so broadcasting louder than the (incredibly weak!) C/A signal is a valid way to jam or spoof GPS. It is, however, generally illegal for civilians.
GPS receivers operating with good practice do tend to try to mitigate this sort of attack, by (for example) ignoring signals with a too-high power level. It's a bit of a cat and mouse game, and there are academic papers exploring each side.
Lastly, GPS receivers also need to deal with interference from GPS itself! If GPS signals bounce off surfaces before reaching the receiver, the receiver might see two sets of GPS signals: one that arrived directly, and one that was scattered off a surface and arrives a bit later. This is called ‘multipath interference’, and part of what goes into making GPS receivers work well is mitigating multipath interference.
I don't think this is actually the case. In a spoofing scenario, all of the rogue signals would typically be generated by a single terrestrial station. The time of flight of all of the generated signals will be the same, so all that matters is the position solution reflected in the transmitted signals, as the fundamental principle of GPS based on TOF is no longer in play. So I'd think that in a typical spoofing scenario, all receivers thinking they're in more or less an identical location is what you'd expect.
It might be possible in a borderline case for the receiver to receive some spoofed signals and some real signals simultaneously, in which case you'd expect weird results, but I think you'd definitely see a correlation around the position being broadcast by the spoofer.
This may be theoretically possible but is, in reality, practically impossible.
Embedded within the GPS signal is the ephemeris data which, among other things, includes each satellite's location in space.
Receivers calculate position by calculating the difference between the time a signal was received and the time stamp encoded in the signal itself.
By analyzing the signals from a minimum of four satellites (one for each dimension in time and space), a receiver calculates where it is.
To spoof all phones on Earth, you would need to trick each receiver individually. Since receivers are passive, they don't identify themselves, and there would be no way to target each individual receiver, making them think they're somewhere they're not.
1. Jamming is obfuscating a signal, usually by creating a lot of noise that makes the real signal hard to find. Spoofing is impersonating a signal.
You can blast out fake data, but depending on what you mean by "large area" and a "point", I don't think what youre suggesting is possible. To trick GPS receivers you end up broadcasting fake signals from multiple GPS satellites, so receivers in different areas will be processing it differently and come up with different coordinates.
Also see this one: https://www.lloydslist.com/LL1148748/War-zone-GPS-jamming-se...
Even if a couple of these signals are degraded, wrong, or missing, most phones will come up with a relatively accurate location using the remaining data.
Not necessarily jamming.