Comment by tialaramex | Hacker News Reader

Comment by tialaramex | Hacker News Reader

Parent Full thread

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Reply on news.ycombinator.com