[AdamJacobMuller]

Cool article.

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.

[londons_explore]

> GPS was launched in 1978,

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.

[codyd51]

Hi! Yes, "from scratch" is definitely always a bit of a funny term. I also implemented the receiver in Python, which is quite far from "scratch" =). What I mean by it in this context is that I'm taking a piece of hardware that knows nothing about GPS, and just has the ability to sample the EM field, and building up a receiver from there.

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.

[tialaramex]

The fast TTFF on a typical modern device e.g. your phone is because the device has the Internet, and so it can obtain all the information it needs from the Internet up front, it isn't magically brute forcing everything needed, that's not practical at all.

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".

[codyd51]

Yes, I forgot to mention downloading the orbital parameters over the network! Thanks for mentioning this as well.

In this case, I was meaning to refer to brute-forcing the Doppler-shifts and PRN phases of each satellite, not the orbital parameters themselves. The project in the OP is able to get a position fix in less than a minute because, if the subframe timings are convenient, you can retrieve the necessary ephemeris parameters from the subframes in that span (and down to as little as 18 seconds in ideal conditions, if my back-of-the-napkin is right).

[makomk]

Yeah, the key reason this enables so much faster time to first fix is that the precise ephemeris parameters are transmitted much more often than the full almanac, but only from the satellite they apply to whereas each satellite broadcasts the entire almanac covering the whole constellation. If I'm understanding the info out there correctly, every transmission of the ephemeris data comes with only 1/25th of the almanac.

Most decent modern-ish receivers tend to have pretty speedy aquisition time without any assistance data. For example, the reasonably ancient GPS running watch I use can usually get a GPS lock in a couple of minutes from cold with no internet access (in a wrist-sized device running on battery!), and even the two decade old SiRFstarIII chipset is specced to have a sub-minute cold start time without assistance and much shorter with - though I think that chipset was pretty advanced for the time.

[michaelt]

You don't need to brute force the almanac - why would you?

But it's very much feasible to 'brute force' your initial signal lock by searching for all gold codes at a range of frequency offsets.

And it doesn't take 12.5 minutes to get the ephemerides - the almanac is sent in paginated form which is why it takes so long, the ephemerides are sent more often - they repeat every 30 seconds, and they're enough for a navigation fix.

Although 30 seconds isn't amazing, so cell phones do use their data connection to shortcut that wait.

[tialaramex]

> You don't need to brute force the almanac - why would you?

I have no idea, but the claim was that you get faster fix with brute force when I know that's not why it's fast in practice.

> But it's very much feasible to 'brute force' your initial signal lock by searching for all gold codes at a range of frequency offsets.

I hadn't even imagined this constituting "brute force". Is my phone using "brute force" to find the WiFi router? At some point it's not really "Brute force" it's "There are a handful of options, try all of them" and GPS seems past that point especially on modern hardware.

This actually reminded me of a (possibly no longer extant) design choice in Encrypted Client Hello - we don't necessarily know if the encryption was done with key F we gave out yesterday afternoon or key G which we just began using an hour ago, do we need a way to signal that in the connection? No, just try all valid keys. If you can't afford to try more than two keys, make sure you only roll them slowly so you won't need to.

[michaelt]

> I hadn't even imagined this constituting "brute force". Is my phone using "brute force" to find the WiFi router?

Early receivers were a lot less advanced than modern receivers - one of the key functions of the almanac is to help receivers figure out what satellites they can expect to see - thus greatly reducing the range of gold codes and time offsets they have to check.

Unlike wifi, GPS signals are below the noise floor until the gold code is applied to despread the signal, and the gold code has to be synchronized with the received signal to detect it.

The gold codes are pseudorandom and designed to stop signals interfering with one another. Unless you know which gold code you're looking for, and find its time offset (accurate to about 2 chips in 1023) you can't tell it apart from noise.

You also don't quite know the frequency you're looking for - partly due to the imprecision of the receiver clock, partly because GPS satellites move very fast and so can have a lot of Doppler shift (depending on where they are in the sky relative to the receiver of course)

Back when receivers had more limited physical hardware, searching through ~30 different satellites, multiplied by ~500 different gold code offsets, multiplied by a few different Doppler shifts could be a slow process. Especially if you'd found a handful of satellites, so some of your receiver channels were tied up with tracking leaving you with fewer for searching!

So ignoring the almanac and brute forcing every satellite, gold code offset and doppler shift is one of the many ways performance has increased since this stuff was developed in the late 1970s.

[myself248]

Small note -- the codes are named after Robert Gold, so being a proper noun, they should be capitalized, just like Gray, Hadamard, or Golay codes.

[error503]

> I hadn't even imagined this constituting "brute force". Is my phone using "brute force" to find the WiFi router? At some point it's not really "Brute force" it's "There are a handful of options, try all of them" and GPS seems past that point especially on modern hardware.

Your phone only needs to listen to the WiFi router on one channel at a time in operation, and the signal parameters are well enough defined that they can be scanned quickly. A GPS receiver requires at least 4 parallel channels to achieve a position solution, and there are up to 32 possible codes the satellites could be at. Scanning 6 channels across 32 codes, and then also sweeping phase and doppler shift to lock them , just to 'discover' if there is a valid signal there takes time, and this is what older receivers had to do. Modern receivers tend to just 'brute force' this by having an entire receive pipeline dedicated to every possible PRN all the time, and possibly even correlate multiple doppler shifts simultaneously as well, so they effectively have 32 (or more) receive channels, despite only ever expecting a maximum of 12 birds being visible. The extra channels are necessary more or less exclusively to reduce acquisition time, so I think it's fair to call them 'brute force'.

[aaronax]

Related: Satellite-based augmentation system (SBAS), of which Wide Area Augmentation System (WAAS) is the USA implementation.

https://en.wikipedia.org/wiki/GNSS_augmentation

[Cyph0n]

As an EE grad, I would still consider what you did to be “from scratch”. Yes, the RF side is complex, but for the purposes of GPS, it is also generic enough to abstract out. Nice work.

[AdamJacobMuller]

Please don't take the "from scratch" bit as criticism. It was just amusing trivia :)

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.

[myself248]

> definitely useless for road navigation

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.

[aspenmayer]

> Delorme Earthmate Hyperformance GPS receiver, the RS-232 version

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?

[myself248]

It's a SiRFstar chipset and speaks the SiRF binary protocol, not standard NMEA0183, so it was difficult to use it for anything else back in the day. Apparently there's a simple command to put it into NMEA mode, but I think that's not preserved across power cycles or something? It was a long time ago... I'm tempted to snag one off eBay and go on a roadtrip down memory lane.

These days, it depends on what you're doing with it, but it's hard to go wrong with this thing that claims to have a U-Blox 8-series chipset:

https://www.aliexpress.com/item/32816656706.html

Uniquely among such cheap receivers, that unit can even be configured to report raw data, and is thus the darling of the Galmon project for low-cost observers starting up. Also fun if you want to play with (single-band) RTK, etc.

(Dual-band has gotten "affordable", by which I mean "under a kilodollar", which is tremendous given where it was just a few years ago, but you'd probably know if you had a use for dual-band.)

[michaelt]

> I'll admit I was a bit disappointed to see that the hardware was just RTL-SDR.

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.

[makomk]

I think even these days, a lot of what the author is doing here is still generally done in hardware for power efficiency reasons - it's just that nowadays, the hardware looks a lot like the software-defined architecture used here with a conversion to digital at the frontend followed by hardware accelerators for doing cross-correlation in the fourier domain. Actually, this kind of approach of implementing the architecture an SDR-based receiver would use as specialised hardware seems to be pretty common in general nowadays.

[epcoa]

> 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

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.

[kube-system]

The truth here depends on the definition of "useless".

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.

[sllabres]

As example the TravelPilot IDS/1989 first prototype from 1983 (see [1] if you want a picture) IIRC the system used a compass, a shunt for the heating wire from the rear window (it would alter the compass because of its magnetic field) and two wheel sensors measuring the rotation of the wheels.

[1] https://www.bosch-presse.de/pressportal/de/en/navigation-sys...

[progbits]

I'm actually glad it uses RTL-SDR, I wasn't aware it was good enough to get interesting results.

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.

[rollulus]

Re: from scratch, this one won’t disappoint you: https://web.archive.org/web/20130111175418/http://www.holmea...

[AdamJacobMuller]

He didn't make his own FPGA with sand from a beach? Weak. (Sarcasm, for those whose detectors are broken)

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.

[magnat]

Slightly updated version: http://www.aholme.co.uk/GPS/Main.htm

[shrx]

“If you wish to make an apple pie from scratch, you must first invent the universe.”

― Carl Sagan, Cosmos