3 ms·

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 Inte

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
codyd51 3y ago
Yes, I forgot to mention downloading the orbital parameters over the network! Thanks for mentioning this as well. In this case, I was meaning to refer to brute-forcing the Doppler-shifts and PRN phases of each satellite, not the orbital parameters themselves. The project in the OP is able to get a position fix in less than a minute because, if the subframe timings are convenient, you can retrieve the necessary ephemeris parameters from the subframes in that span (and down to as little as 18 seconds in ideal conditions, if my back-of-the-napkin is right).
- makomk 3y ago
  Yeah, the key reason this enables so much faster time to first fix is that the precise ephemeris parameters are transmitted much more often than the full almanac, but only from the satellite they apply to whereas each satellite broadcasts the entire almanac covering the whole constellation. If I'm understanding the info out there correctly, every transmission of the ephemeris data comes with only 1/25th of the almanac. Most decent modern-ish receivers tend to have pretty speedy aquisition time without any assistance data. For example, the reasonably ancient GPS running watch I use can usually get a GPS lock in a couple of minutes from cold with no internet access (in a wrist-sized device running on battery!), and even the two decade old SiRFstarIII chipset is specced to have a sub-minute cold start time without assistance and much shorter with - though I think that chipset was pretty advanced for the time.
michaelt 3y ago
You don't need to brute force the almanac - why would you? But it's very much feasible to 'brute force' your initial signal lock by searching for all gold codes at a range of frequency offsets. And it doesn't take 12.5 minutes to get the ephemerides - the almanac is sent in paginated form which is why it takes so long, the ephemerides are sent more often - they repeat every 30 seconds, and they're enough for a navigation fix. Although 30 seconds isn't amazing, so cell phones do use their data connection to shortcut that wait.
- tialaramex 3y ago
  > 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.
  - error503 3y ago
    > I hadn't even imagined this constituting "brute force". Is my phone using "brute force" to find the WiFi router? At some point it's not really "Brute force" it's "There are a handful of options, try all of them" and GPS seems past that point especially on modern hardware. Your phone only needs to listen to the WiFi router on one channel at a time in operation, and the signal parameters are well enough defined that they can be scanned quickly. A GPS receiver requires at least 4 parallel channels to achieve a position solution, and there are up to 32 possible codes the satellites could be at. Scanning 6 channels across 32 codes, and then also sweeping phase and doppler shift to lock them , just to 'discover' if there is a valid signal there takes time, and this is what older receivers had to do. Modern receivers tend to just 'brute force' this by having an entire receive pipeline dedicated to every possible PRN all the time, and possibly even correlate multiple doppler shifts simultaneously as well, so they effectively have 32 (or more) receive channels, despite only ever expecting a maximum of 12 birds being visible. The extra channels are necessary more or less exclusively to reduce acquisition time, so I think it's fair to call them 'brute force'.

aaronax 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

codyd51 3y ago

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

makomk 3y ago
Yeah, the key reason this enables so much faster time to first fix is that the precise ephemeris parameters are transmitted much more often than the full almanac, but only from the satellite they apply to whereas each satellite broadcasts the entire almanac covering the whole constellation. If I'm understanding the info out there correctly, every transmission of the ephemeris data comes with only 1/25th of the almanac. Most decent modern-ish receivers tend to have pretty speedy aquisition time without any assistance data. For example, the reasonably ancient GPS running watch I use can usually get a GPS lock in a couple of minutes from cold with no internet access (in a wrist-sized device running on battery!), and even the two decade old SiRFstarIII chipset is specced to have a sub-minute cold start time without assistance and much shorter with - though I think that chipset was pretty advanced for the time.

michaelt 3y ago

You don't need to brute force the almanac - why would you? But it's very much feasible to 'brute force' your initial signal lock by searching for all gold codes at a range of frequency offsets. And it doesn't take 12.5 minutes to get the ephemerides - the almanac is sent in paginated form which is why it takes so long, the ephemerides are sent more often - they repeat every 30 seconds, and they're enough for a navigation fix. Although 30 seconds isn't amazing, so cell phones do use their data connection to shortcut that wait.

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