Show HN: Building a GPS receiver

Show HN: Building a GPS receiver(axleos.com)

552 points by codyd51 2 years ago | 128 comments

Hi everyone!

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!

[1]: https://news.ycombinator.com/item?id=37736318

amluto 2 years ago |

> Just one problem: you won’t find any SDR on the market that will claim to be able to sample a wave oscillating over a billion times a second.

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.

elevation 2 years ago | |

> 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

AnarchismIsCool 2 years ago | | |

It's very hard to prevent the LO from leaking into the ADC input. Putting the filters in the right places would cause a lot of issues for the signal chain so a common workaround is trying to null it with a 180 degree out of phase LO signal.

amluto 2 years ago | | |

I don’t know all the details of this kind of technology, but I would imagine that one direct RF receiver’s sample clock looks effectively identical to any other similar receiver’s sample clock. So if these devices become popular, then a military sample clock is indistinguishable from a civilian sample clock. In contrast, an LO is rather application-specific.

codyd51 2 years ago | |

This is amazing! I had no idea tech like this was available on the market. Thank you for the correction.

kragen 2 years ago | | |

i agree!

AdamJacobMuller 2 years ago |

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.

magnat 2 years ago |

Note that GPS receiver capable (i.e. not artificially limited) of providing navigation data while moving 600 m/s or higher used to be considered munition by ITAR. The amount of legalese at updated ruling [1] is well beyond what I can make sense of, to the point I don't even know if it still applies.

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

nomel 2 years ago | |

> takedown of passive radar GNU Radio module made by Kraken RF team.

https://hackaday.com/2022/11/19/open-source-passive-radar-ta...

opello 2 years ago | | |

I did some brief searching of their Twitter feed and in general but couldn't find any update on this. Does anyone know the current state of passive radar and KrakenSDR?

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

analognoise 2 years ago | | |

IIRC everything they took down was in the Git repo history.

blobcode 2 years ago |

A good, decently detailed look at signal processing required. I also like https://ciechanow.ski/gps/, which has some fantastic visuals to go along with this explanation.

klabb3 2 years ago | |

Wow that blog never ceases to amaze me. I was actually thinking about it when I read this post, that it’s exactly the type of post Bartosz could have made. And he had! Those interactive graphics are unbeatable.

sizzzzlerz 2 years ago |

Brilliant! I have no idea what the technical background of the author is but for anyone to tease apart the vast, complex, details of the GPS universe is a massive feat. Coupled with his ability to craft software to both assist his analysis and to implement the final solution, he has created a magnificent project. I've been studying GPS and worked with it professionally for a number of years and I still don't know everything about it. I'm looking forward to digging into the code. Kudos to the author!

codyd51 2 years ago | |

I am really grateful for this nice comment, thank you! As a self taught programmer with no background in RF or EE, this project was definitely a stretch for me and involved lots of (sometimes frustrating) learning and experimentation. Looking back, I'm really glad for it, as it feels as though I've unlocked RF as a domain that I now understand a lot more tangibly and can use as a sort of tool. It reminds me of the things I love about computers themselves!

AlexanderTheGr8 2 years ago | |

"Interestingly, the only thing stopping civilians from using the P code is the knowledge of the value of its chipping sequence. If the formula to generate the P code was publicly known, there’d be nothing stopping civilian GPS receivers from locking on to it, with the exact same techniques as are used for the C/A code."

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?

tylerchr 2 years ago |

Super impressive. Can’t agree more with the author that GPS is a stunningly clever engineering achievement.

For those interested in the story of the development of GPS, I found “GPS Declassified” by Richard Easton to be an engaging retelling.

d33 2 years ago | |

While reading Amazon reviews, I learned that they missed the contributions by Hedy Lamarr, a very interesting and impressive figure:

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

pomian 2 years ago | | |

a great book to read, much better than you would expect, about Hedy Lamarr, is Richard Rhodes book: "Hedy's Folly."

codyd51 2 years ago | |

Thank you very much!

OmarShehata 2 years ago |

Amazing! I also had exactly the same experience that led me to research this a few years ago, realizing that:

- 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!)

wglb 2 years ago |

> Have you ever noticed that your Maps app still works during a flight?

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.

noman-land 2 years ago |

I really love how this article is paced in real time from the first person as a learning adventure. Even down to the search terms used and the inner monologue. This is my absolute favorite kind of tutorial because you're not just being taught to fish, you're being shown how go about sourcing the parts to built your own fishing machinery.

codyd51 2 years ago | |

Thank you for sharing this! It is sort of a vulnerable thing to write, because it reveals the shapes and bounds of my own ignorance, and the path I took to learning. I am really grateful to hear that you appreciated the approach.

noman-land 2 years ago | | |

No, this is great. This is extremely rare for people to do, even rarer for people to do well. You have a gift! Keep going.

js2 2 years ago |

A documentary which interviews the principals involved in the creation of GPS (The Lonely Halls Meeting) is on YouTube:

https://youtu.be/Z5N4CqJLAhQ?si=lvaQZv-WG3ab_gEI

throw0101c 2 years ago |

Standford has/had a course that is available online on GPS/GNSS and a lot of the nitty-gritty details:

* https://www.youtube.com/playlist?list=PLGvhNIiu1ubyEOJga50LJ...

codyd51 2 years ago | |

Thank you for linking this, this course is phenomenal! Several of the videos were immensely helpful in my GPS journey.

quibono 2 years ago | |

Thank you for this, this looks great!

michaelt 2 years ago |

Great project, thanks for posting it!

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?

codyd51 2 years ago | |

Thank you very much for your thoughtful offer! I won't be able to readily work on side projects after starting my new role next week, and am content to consider this project complete for the time being. However, what you've proposed does sound interesting and fun. I'm going to go ahead and shoot an email to the address listed in your profile.

seba_dos1 2 years ago |

> I’ll be starting a new job next week which isn’t as amenable to publishing side projects

What does a job have to do with publishing hobby projects?

tgsovlerkhgsel 2 years ago | |

Some jobs insist on owning everything you do even in your free time, and will fire you for having personal projects.

(Other jobs may just take up a lot of energy and/or time.)

seba_dos1 2 years ago | | |

> owning everything you do even in your free time

Where and how is that legal? You're supposed to be an employee, not a slave.

ck2 2 years ago |

If you really want to see all the gps-like services out there and have android, you must play with the open-source GPStest

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)

nayuki 2 years ago | |

Awesome app you mentioned. So far, I was only using the lesser app of "GPS Status" for Android: https://play.google.com/store/apps/details?id=com.eclipsim.g... .

ChuckMcM 2 years ago |

Just want to say Cody this is a super write up!

NovemberWhiskey 2 years ago |

It's not entirely clear to me from the write-up, but it seems some of the problems that the author had with the "tracker" come from attempting to do carrier phase synchronization (with the Costas loop) before any kind of clock recovery.

codyd51 2 years ago | |

Whoa, thank you! I don't know much about RF and learned ad-hoc for this project, and it seems perfectly plausible to me that someone knowledgeable would be able to look at this and identify a root cause - I certainly didn't do anything special for clock recovery, and based on the name I would have blindly assumed that synchronising the carrier wave _would_ be tantamount to recovering the satellite clock. I haven't researched clock recovery yet, and will do so. Once again, thank you!

tgsovlerkhgsel 2 years ago |

Wow, thank you! While I had a glimpse at various parts of the madness earlier, this is the first article that actually brought it to a level where I could convince my brain to understand it end-to-end.

codyd51 2 years ago | |

That's so great to hear, thank you for the nice feedback!

ruuda 2 years ago |

> Have you ever noticed that your Maps app still works during a flight?

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.

error503 2 years ago | |

You're more or less inside a Faraday cage. I find you'll generally get a strong lock just holding your phone near the window, though TTFF can be relatively slow compared to normal due to the lack of AGPS.

wglb 2 years ago | |

I've had good luck getting fixed, particularly in window seats holding the phone generally close to the window. It takes longer than on the ground outside.

AlexanderTheGr8 2 years ago |

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?

minetest2048 2 years ago | |

Kind of. The P code itself is publicly available in publicly available specification IS-GPS-200. They are xor-ed by W code, which like the sibling comment says, is cryptographically generated, which runs at a lower rate. This results in P(Y) code signal, which is then transmitted over the satellites.

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

tgsovlerkhgsel 2 years ago | |

I would assume that the chipping sequence is derived from a frequently-rotated cryptographic key.

codyd51 2 years ago | | |

I believe you are correct. My understanding is that the root P key is rotated daily, and needs to be manually uploaded to any military hardware that needs to use it.

wkat4242 2 years ago |

I find it amazing that they managed to design and build all this in the 1970s when computers were only in their infancy and SDR was complete science-fiction.

jeffypoo 2 years ago |

This was a delightful read. Reminded me of my time working on low power FHSS radio gear. We truly take modern wireless technologies for granted!

codyd51 2 years ago | |

Thank you very much! I agree, they are incredible! I really had no idea until making this project, and it makes things like cellular phones so astoundingly impressive.

two_handfuls 2 years ago |

Beautifully written, and educational. Plus very impressive technically! I wish I could upvote this more than once. Thank you!

codyd51 2 years ago | |

What a wonderful thing to say about a stranger's article! Thank you very much for posting this.

bArray 2 years ago |

Would like to add that I have purchased myself the SDR so that I can replicate the experiment/work done here - it seems super cool!

CamperBob2 2 years ago |

Anyone manage to get this working with pip in Windows? After installing the dependencies:

    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 syntax

icegreentea2 2 years ago | |

I think you need python3.11 for that syntax.

darkhorn 2 years ago |

Is it possible to trick phones with a jammer in a large area to make it look like all phones are in a specific point on Earth. Only with a jammer?

emehrkay 2 years ago |

Does anyone know how the data a stored, where at, what tech etc? I can only assume that the retention policies are in decades

martinky24 2 years ago | |

What data do you mean...?

kaitocross 2 years ago |

Does it only support the US-made GPS (NAVSTAR GPS) or other GNSS systems like Galileo as well?

codyd51 2 years ago | |

This project only supports the 'legacy' C/A variant of the NAVSTAR constellation's signals.

noman-land 2 years ago |

Really amazing piece of work. I look forward to digging into it. Thanks for sharing.

hcfman 2 years ago |

Really nice writeup!

pictureofabear 2 years ago |

Now do it for the encrypted signal (the P(Y)-code)!