6 ms·

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

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.

rollulus 3y ago
Re: from scratch, this one won’t disappoint you: https://web.archive.org/web/20130111175418/http://www.holmea.demon.co.uk/GPS/Main.htm https://web.archive.org/web/20130111175418/http://www.holmea...
- AdamJacobMuller 3y ago
  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 3y ago
  Slightly updated version: http://www.aholme.co.uk/GPS/Main.htm http://www.aholme.co.uk/GPS/Main.htm
codyd51 3y ago
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.
- Cyph0n 3y ago
  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.
- tialaramex 3y ago
  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".
  - aaronax 3y ago
    Related: Satellite-based augmentation system (SBAS), of which Wide Area Augmentation System (WAAS) is the USA implementation. https://en.wikipedia.org/wiki/GNSS_augmentation https://en.wikipedia.org/wiki/GNSS_augmentation
michaelt 3y ago
> 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 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 3y ago
  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.
shrx 3y ago
“If you wish to make an apple pie from scratch, you must first invent the universe.” ― Carl Sagan, Cosmos
progbits 3y ago
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.
deleted 3y ago
[deleted]
epcoa 3y ago
> 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 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 3y ago
  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 3y ago
    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-system-travelpilot-ids-1989-60605.html https://www.bosch-presse.de/pressportal/de/en/navigation-sys...
londons_explore 3y ago
> 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.
myself248 3y ago
> 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 3y ago
  > 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 3y ago
    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 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.)

rollulus 3y ago

Re: from scratch, this one won’t disappoint you: https://web.archive.org/web/20130111175418/http://www.holmea.demon.co.uk/GPS/Main.htm https://web.archive.org/web/20130111175418/http://www.holmea...

AdamJacobMuller 3y ago
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 3y ago
Slightly updated version: http://www.aholme.co.uk/GPS/Main.htm http://www.aholme.co.uk/GPS/Main.htm

codyd51 3y ago

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.

Cyph0n 3y ago
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.
tialaramex 3y ago
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".
- aaronax 3y ago
  Related: Satellite-based augmentation system (SBAS), of which Wide Area Augmentation System (WAAS) is the USA implementation. https://en.wikipedia.org/wiki/GNSS_augmentation https://en.wikipedia.org/wiki/GNSS_augmentation

michaelt 3y ago

> 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 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 3y ago
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.

shrx 3y ago

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

progbits 3y ago

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.

deleted 3y ago

[deleted]

epcoa 3y ago

> 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 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 3y ago
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 3y ago
  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-system-travelpilot-ids-1989-60605.html https://www.bosch-presse.de/pressportal/de/en/navigation-sys...

londons_explore 3y ago

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

myself248 3y ago

> 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 3y ago
> 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 3y ago
  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 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.)