11 ms·

Show HN: Building a GPS receiver

552 points by codyd51 2y ago

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 https://news.ycombinator.com/item?id=37736318

deleted 2y ago
[deleted]
blobcode 2y ago
A good, decently detailed look at signal processing required. I also like https://ciechanow.ski/gps/ https://ciechanow.ski/gps/, which has some fantastic visuals to go along with this explanation.
- klabb3 2y 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.
noman-land 2y ago
Really amazing piece of work. I look forward to digging into it. Thanks for sharing.
AdamJacobMuller 2y 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.
- rollulus 2y 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 2y 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 2y ago
    Slightly updated version: http://www.aholme.co.uk/GPS/Main.htm http://www.aholme.co.uk/GPS/Main.htm
noman-land 2y 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 2y 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 2y 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.
darkhorn 2y 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?
- codyd51 2y ago
  GPS jamming or spoofing on a wide scale is definitely a viable attack! As another commenter noted well, making everyone appear at exactly the same location would be nigh-impossible, though. GPS 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.
  - pictureofabear 2y ago
    Just to be a little clearer, jamming and spoofing are the not the same thing. Jamming obfuscates a signal, usually through noise. Spoofing impersonates the signal.
  - error503 2y ago
    > making everyone appear at exactly the same location would be nigh-impossible, though. 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.
CamperBob2 2y 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 2y ago
  I think you need python3.11 for that syntax.
teknopaul 2y ago
[flagged]
- mewpmewp2 2y ago
  I didn't understand how a car engine works at 12. Now try imagine GPS...
  - userbinator 2y ago
    I helped rebuild a car engine at 12... yet GPS didn't even exist.
js2 2y 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 https://youtu.be/Z5N4CqJLAhQ?si=lvaQZv-WG3ab_gEI
pictureofabear 2y ago
Now do it for the encrypted signal (the P(Y)-code)!
sizzzzlerz 2y 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!
- AlexanderTheGr8 2y 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?
- codyd51 2y 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!
tylerchr 2y 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 2y 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 https://en.wikipedia.org/wiki/Hedy_Lamarr
  - pomian 2y ago
    a great book to read, much better than you would expect, about Hedy Lamarr, is Richard Rhodes book: "Hedy's Folly."
- codyd51 2y ago
  Thank you very much!
throw0101c 2y 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=PLGvhNIiu1ubyEOJga50LJMzVXtbUq6CPo https://www.youtube.com/playlist?list=PLGvhNIiu1ubyEOJga50LJ...
- quibono 2y ago
  Thank you for this, this looks great!
- codyd51 2y ago
  Thank you for linking this, this course is phenomenal! Several of the videos were immensely helpful in my GPS journey.
amluto 2y 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_overview-1670395.pdf 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-electronic-warfare-sigint/advantages-of-direct-rf-sampling-architectures.html 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-instruments-and-processing.html?productId=230187 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 2y 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
  - amluto 2y 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.
OmarShehata 2y 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!)
- jeffbee 2y ago
  A person would have to have a quite flawed mental model of what GPS is to form the belief that it would stop working without data service, wouldn't they?
  - outworlder 2y ago
    Most people have quite flawed mental models of how things work.
  - deleted 2y ago
    [deleted]
  - nix0n 2y ago
    There's a difference between GPS vs A-GPS (Assisted GPS)[0][1]. 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 https://en.wikipedia.org/wiki/Assisted_GNSS [1]https://news.ycombinator.com/item?id=40042686 https://news.ycombinator.com/item?id=40042686
magnat 2y 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-receivers-updated/ https://www.space.commerce.gov/itar-controls-on-gps-gnss-rec...
- nomel 2y ago
  > takedown of passive radar GNU Radio module made by Kraken RF team. https://hackaday.com/2022/11/19/open-source-passive-radar-taken-down-for-regulatory-reasons/ https://hackaday.com/2022/11/19/open-source-passive-radar-ta...
  - opello 2y 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-software-for-rtl-sdrs/ 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.
    - londons_explore 2y ago
      The lawyer likely advised not talking about it more publicly. Almost any lawyer won't present the world as black and white, but rather in quantities of risk - and even saying "we've taken the project down and it wont be coming back" is a risk if that attracts attention to your past distribution of the software and causes others to mirror it from archives.
      - 2y ago
ck2 2y 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 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 2y 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.gpsstatus2&hl=en_CA&gl=US https://play.google.com/store/apps/details?id=com.eclipsim.g... .
NovemberWhiskey 2y 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 2y 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!
michaelt 2y 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 2y 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.
robtest123 2y ago
[flagged]
ruuda 2y 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 2y 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 2y 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.
wglb 2y 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.
emehrkay 2y 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 2y ago
  What data do you mean...?
seba_dos1 2y 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 2y 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 2y 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.
    - tgsovlerkhgsel 2y ago
      Unfortunately, most countries don't have, or don't enforce, penalties for companies claiming rights they don't have. So that's the first part: Companies claim, often using vague or misleading wording, to have more rights than they can legally claim. And what they can claim varies but can go quite far. For example, even employee-friendly California with a law specifically to limit far reaching clauses (https://law.justia.com/codes/california/2011/lab/division-3/2870-2872/2870 https://law.justia.com/codes/california/2011/lab/division-3/...) allows terms in employment agreement that assign to the employer the ownership of "invention[s] that the employee developed entirely on his or her own time without using the employers equipment, supplies, facilities, or trade secret information" as long as they "Relate ... to the employers business, or actual or demonstrably anticipated research or development of the employer". For a megacorp, that can be basically everything. The second part is that in some countries you can be fired for any reason, or no reason, except for specific protected reasons. "We didn't like your blog post and are worried that you might accidentally reveal company secrets in one of them in the future, so we're letting you go" would be legal in many places. "All social media or personal web site content has to be reviewed to make sure you're not leaking company secrets" is also a demand some companies make. Likewise "we want you to give 100% at work and your side project clearly shows you're spending too much time elsewhere so we don't believe you're working to your full potential", even though stupid, would be a perfectly legal justification to fire someone in many countries. Or just the manager silently thinking that and silently retaliating through e.g. denying promotions.
AlexanderTheGr8 2y 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?
- tgsovlerkhgsel 2y ago
  I would assume that the chipping sequence is derived from a frequently-rotated cryptographic key.
  - codyd51 2y 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.
- minetest2048 2y 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
jeffypoo 2y 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 2y 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.
tgsovlerkhgsel 2y 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 2y ago
  That's so great to hear, thank you for the nice feedback!
kaitocross 2y ago
Does it only support the US-made GPS (NAVSTAR GPS) or other GNSS systems like Galileo as well?
- codyd51 2y ago
  This project only supports the 'legacy' C/A variant of the NAVSTAR constellation's signals.
wkat4242 2y 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.
two_handfuls 2y ago
Beautifully written, and educational. Plus very impressive technically! I wish I could upvote this more than once. Thank you!
- codyd51 2y ago
  What a wonderful thing to say about a stranger's article! Thank you very much for posting this.
hcfman 2y ago
Really nice writeup!
ChuckMcM 2y ago
Just want to say Cody this is a super write up!
bArray 2y 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!

552 points by codyd51 2y ago

deleted 2y ago

[deleted]

blobcode 2y ago

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

klabb3 2y 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.

noman-land 2y ago

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

AdamJacobMuller 2y 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.

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

noman-land 2y 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 2y 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 2y 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.

darkhorn 2y 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?

codyd51 2y ago
GPS jamming or spoofing on a wide scale is definitely a viable attack! As another commenter noted well, making everyone appear at exactly the same location would be nigh-impossible, though. GPS 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.
- pictureofabear 2y ago
  Just to be a little clearer, jamming and spoofing are the not the same thing. Jamming obfuscates a signal, usually through noise. Spoofing impersonates the signal.
- error503 2y ago
  > making everyone appear at exactly the same location would be nigh-impossible, though. 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.

CamperBob2 2y 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 2y ago
I think you need python3.11 for that syntax.

teknopaul 2y ago

[flagged]

mewpmewp2 2y ago
I didn't understand how a car engine works at 12. Now try imagine GPS...
- userbinator 2y ago
  I helped rebuild a car engine at 12... yet GPS didn't even exist.

js2 2y 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 https://youtu.be/Z5N4CqJLAhQ?si=lvaQZv-WG3ab_gEI

pictureofabear 2y ago

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

sizzzzlerz 2y 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!

AlexanderTheGr8 2y 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?
codyd51 2y 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!

tylerchr 2y 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 2y 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 https://en.wikipedia.org/wiki/Hedy_Lamarr
- pomian 2y ago
  a great book to read, much better than you would expect, about Hedy Lamarr, is Richard Rhodes book: "Hedy's Folly."
codyd51 2y ago
Thank you very much!

throw0101c 2y 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=PLGvhNIiu1ubyEOJga50LJMzVXtbUq6CPo https://www.youtube.com/playlist?list=PLGvhNIiu1ubyEOJga50LJ...

quibono 2y ago
Thank you for this, this looks great!
codyd51 2y ago
Thank you for linking this, this course is phenomenal! Several of the videos were immensely helpful in my GPS journey.

amluto 2y 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_overview-1670395.pdf 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-electronic-warfare-sigint/advantages-of-direct-rf-sampling-architectures.html 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-instruments-and-processing.html?productId=230187 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 2y 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
- amluto 2y 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.

OmarShehata 2y 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!)

jeffbee 2y ago
A person would have to have a quite flawed mental model of what GPS is to form the belief that it would stop working without data service, wouldn't they?
- outworlder 2y ago
  Most people have quite flawed mental models of how things work.
- deleted 2y ago
  [deleted]
- nix0n 2y ago
  There's a difference between GPS vs A-GPS (Assisted GPS)[0][1]. 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 https://en.wikipedia.org/wiki/Assisted_GNSS [1]https://news.ycombinator.com/item?id=40042686 https://news.ycombinator.com/item?id=40042686

magnat 2y 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-receivers-updated/ https://www.space.commerce.gov/itar-controls-on-gps-gnss-rec...

nomel 2y ago
> takedown of passive radar GNU Radio module made by Kraken RF team. https://hackaday.com/2022/11/19/open-source-passive-radar-taken-down-for-regulatory-reasons/ https://hackaday.com/2022/11/19/open-source-passive-radar-ta...
- opello 2y 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-software-for-rtl-sdrs/ 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.
  - londons_explore 2y ago
    The lawyer likely advised not talking about it more publicly. Almost any lawyer won't present the world as black and white, but rather in quantities of risk - and even saying "we've taken the project down and it wont be coming back" is a risk if that attracts attention to your past distribution of the software and causes others to mirror it from archives.
    - 2y ago

ck2 2y 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 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 2y 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.gpsstatus2&hl=en_CA&gl=US https://play.google.com/store/apps/details?id=com.eclipsim.g... .

NovemberWhiskey 2y 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 2y 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!

michaelt 2y 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 2y 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.

robtest123 2y ago

[flagged]

ruuda 2y 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 2y 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 2y 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.

wglb 2y 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.

emehrkay 2y 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 2y ago
What data do you mean...?

seba_dos1 2y 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 2y 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 2y 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.
  - tgsovlerkhgsel 2y ago
    Unfortunately, most countries don't have, or don't enforce, penalties for companies claiming rights they don't have. So that's the first part: Companies claim, often using vague or misleading wording, to have more rights than they can legally claim. And what they can claim varies but can go quite far. For example, even employee-friendly California with a law specifically to limit far reaching clauses (https://law.justia.com/codes/california/2011/lab/division-3/2870-2872/2870 https://law.justia.com/codes/california/2011/lab/division-3/...) allows terms in employment agreement that assign to the employer the ownership of "invention[s] that the employee developed entirely on his or her own time without using the employers equipment, supplies, facilities, or trade secret information" as long as they "Relate ... to the employers business, or actual or demonstrably anticipated research or development of the employer". For a megacorp, that can be basically everything. The second part is that in some countries you can be fired for any reason, or no reason, except for specific protected reasons. "We didn't like your blog post and are worried that you might accidentally reveal company secrets in one of them in the future, so we're letting you go" would be legal in many places. "All social media or personal web site content has to be reviewed to make sure you're not leaking company secrets" is also a demand some companies make. Likewise "we want you to give 100% at work and your side project clearly shows you're spending too much time elsewhere so we don't believe you're working to your full potential", even though stupid, would be a perfectly legal justification to fire someone in many countries. Or just the manager silently thinking that and silently retaliating through e.g. denying promotions.

AlexanderTheGr8 2y 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?

tgsovlerkhgsel 2y ago
I would assume that the chipping sequence is derived from a frequently-rotated cryptographic key.
- codyd51 2y 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.
minetest2048 2y 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

jeffypoo 2y 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 2y 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.

tgsovlerkhgsel 2y 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 2y ago
That's so great to hear, thank you for the nice feedback!

kaitocross 2y ago

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

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

wkat4242 2y 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.

two_handfuls 2y ago

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

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

hcfman 2y ago

Really nice writeup!

ChuckMcM 2y ago

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

bArray 2y 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!