> Naturally, large range uncertainty increases the ambiguity of position, but the relative position of the satellites also matters. If they aren’t well spread, the exactness of calculated location also suffers.
(see the excellent example in OP)
Fun tidbit, the resulting error is known for the system in closed form as Geometric Dilution of Precision, and is a 3x3 (edit: or 4+x4+ if you are estimating bias or quantities like time, thx brandmeyer) matrix that depends on all the locations of the visible sats, and your position relative to them.
GDOP is a general relationship for any estimator based only on the equations used to derive something from sensor remote sensor measurements. It's possible to derive GDOP for any sensing system using the Fisher Information Matrix (which is the inverse of GDOP). Some minor caveats apply, but in general this is a useful trick.
Another fun thing: FIM can be derived a number of ways, and appears if you simply ask (mathematically) "What is the most likely position of the gps sensor given sat locations" as the hessian matrix of the system that you use while answering that question using e.g., convex minimization.
All of sensing & estimation is just mostly convex optimization.
The natural expression of the DOP matrix is 4x4, since the receiver is computing a solution in 4D space-time. Its pretty common for the dominant eigenvector to be along the time-vertical axis for a terrestrial receiver.
Geometric quality is easy to consider in terms of using trig and measured angles to solve for an (roughly) equilateral triangle vs a triangle with a very small measured internal angle.
Also, it's easier to understand variables vs uknowns of GPS if you consider that direct measurement is of velocity and/or acceleration, and position is the resultant derivative, after taking into account the probabilities of various solutions.
(Velocity and acceleration can be measured directly without making as many assumptions about various starting conditions.)
For these kinds of problems, literature has multiple derivations of FIM for the purposes of tracking & estimation (and path planning for sensing -- my former specialty). Shameless plug: https://josh.vanderhook.info/media/pdf/thesis.pdf chapter 3.
Most of that was distilled from literature or basic math (and probably contains errors -- thanks grad school).
B. Grocholsky, “Information-theoretic control of multiple sensor platforms,” Ph.D.
dissertation, University of Sydney. School of Aerospace, Mechanical and Mecha-
tronic Engineering, 2006
Look there in equation 6: That's the FIM being left multiplied when solving these types of problems. (under standard gauss-newton step, which is also common)
GDOP is sometimes taken to mean the largest eigenvalue or trace of the covariance matrix. It's a metric for the badness of the estimate.
Often, GDOP is broken into components HDOP, VDOP, etc for the values corresponding to some earth-fixed coordinate frame. That starts to look more like statistics about the covariance matrix.
This is very nice. Very clear, and the 3D interactives are excellent at guiding the explanation.
One thing that I thought was a little confusing was right at the beginning, when we were estimating the position of the figurine and there was an area of uncertainty shown by the yellow circle.
It isn't clear how you're estimating position, and why we have an area of uncertainty. At first I figured it was going to explain it using triangulation (measurement of angles) but there's no reason triangulation wouldn't be exactly as accurate as the tape measure method on a 2D surface, so wouldn't explain the area of uncertainty.
The description merely says:
> Just by using these three reference points we can relate the figurine’s position in the environment to an approximate placement on the map as show with the yellow shape on the right.
I worry that having this ambiguity so early on might put some people off from reading the rest, because they figure they don't understand that and so won't understand the rest of it.
More generally, the assumptions about what things were uncertain and what could be taken as exact were poorly motivated. The author should wither justify them with real-world constraints ("satellites can host atomic clocks but destroyers can't" -- not obvious!) or explicitly announce the assumptions as unjustified, but he shouldn't make it seem like the assumptions could have been reasoned to by the reader.
I also was disappointed the author used circles/spheres and guesses for the timing offset rather than the much more edifying choice of hyperbolas. Just as you can think of a sphere as points reachable by the end of a rope of fixed length tied to a post, you can think about a hyperbola as the points reachable by tying separate ropes to two posts and spooling out equal amounts of rope.
I think it's as though you were the yellow figure standing in the landscape, and you were trying to position yourself on the map by going "Okay, the red landmark is quite close to me to the east, the blue landmark is a bit farther away to the north-west, and the green landmark is way over to the south-west. Now, where am I on the map?"
Was taught in college that if we get stuck, just move on forwards, things ahead can clear that up. And it works in this case for me. That part really doesn't matter much. At the end of the day, our brain is not a linear programming interpreter.
I stopped reading there because frankly, if there’s such a flaw in the article that early, I was worried about the accuracy of the rest of it.
The concept is just not explained at all. I spent too long making sure I didn’t miss some sentence somewhere explaining what was happening in that diagram. It felt like the article was wasting my time, and that maybe the author himself didn’t really understand what was happening.
No. I definitely did read that part of the article. I also went back and read the rest of the article this morning before I posted that comment, and he never goes on to explain that part. He just brushes past it and never clears it up.
It’s not really relevant to how GPS works? It’s just scene setting an intuition for, crudely, how you might estimate your position relative to landmarks.
If your take is then ‘well, he didn’t rigorously define how he derived the error bounds on crude position estimation, therefore all this stuff building into the level of precision GPS is capable of rests on a flimsy foundation of lies’, perhaps you are not the target audience for this kind of didactic presentation.
> well, he didn’t rigorously define how he derived the error bounds on crude position estimation
or more correctly, he used an example and a diagram without every explaining how we should think about it. I think running into a nonsensical, unexplained diagram is a good heuristic for whether or not an article is worth reading — even if, in this case, it turns out the rest of the article is well-written.
I had the same question. I moved on in the article, and its great, but this still puzzled me. If the author cleared this up, this article would be an absolute masterclass.
Yeah, I suppose it’s like “you are a human standing on a flat plain looking at these 3 landmark towers. Where on the map are you?
Intuitively you would be able to eyeball the angles between the landmarks, and eyeball the relative distances. I don’t think I’d draw a circle though. I’d probably have way less confidence for the landmark farther away and balloon out my estimate.
Think about it as if you are standing somewhere in relation to the monuments and are trying to figure out where you are on the map. You don't have precise measurements of distances or angles, you only have the estimated distance / angle you are from each of them that you get by looking at them. And without precise measurements there is uncertainty in where you are located.
You probably know exactly where you are on the map if you are within a meter of a monument. As you move farther away from the monuments your estimation of the distance from each one becomes less precise. At least when I am estimating a distance things end up rough really quickly. At 10m I might be off by 1m. By 50m I am off by 10m, and so on. Now translate that into an exact position on the map. It not possible, there is always some level of uncertainty.
I didn't realize it at first, but all of the examples are interactive. You can move the figure around, I found that pretty helpful and fun as well. In the very first example: place the figure somewhere, and then try and point to where it is on the map. I found myself circling areas naturally, even though the scale is relatively small. Especially when viewing it from an angle. The second example is quite exaggerated as far as the circles go but it is representative of the idea.
It's so depressing that – at some point in the future – I'm going to want a really clear and precise explanation of how GPS works and the likelihood that an internet search directs me to this excellent, clean, and ad-free blog is essentially nil.
My own recommendation is NIST Technical Note 1385 "Global Positioning System Receivers and Relativity" by Ashby and Weiss[0], and the GPS ICD for the L1 and L2C signals IS-GPS-200[1].
They are aimed at the practitioner who actually needs to solve problems. TFA is entertaining and pretty, but insufficient to actually get work done.
You may be on to something here. With GPT-3 you could improve the quality of the responses by starting with a prompt like, "You're a well-educated and very helpful individual".
Maybe internet searches can be improved by changing the search from "how gps works" to "excellent, clear, and precise explanation of gps"?
Searching for "TechA vs TechB" was also a great trick. Until the SEO people noticed. They also have access to GPT-3 now to generate their auxiliary "content".
I think we need web search to move towards something more reputation-based. (Based on sites like HN, Reddit, StackOverflow, etc. that don't allow to easily fake high reputation. Or some kind of trust network starting from all your social accounts' subscriptions/follows and spreading your trust far outwards.)
IMO the best place to find in-depth documentation of existing technologies is the patent office. A while ago I programmed a way to locate the source of gunfire with microphones and drew a lot of inspiration from GPS patents because I couldn't find anything in-depth on the subject on Google (finding the time and position of the source of a shockwave is basically just inverse GPS multilateration)
I work on the Android location team at Google, and I sent this article out to my team. GPS/GNSS is critical for accurate location/context, and there's still plenty of innovations happening in this field.
One of our directors is Frank Van Diggelen - none other than the professor who taught the Stanford GPS MOOC referenced by the article :) I'm sure he is going to appreciate seeing the course called out there!
It depends on the GNSS chipset in the phone, but usually it'll be all the GNSS satellites visible in the sky, from all major constellations. The current Android platform supports GPS, SBAS, GLONASS, QZSS, BEIDOU, GALILEO, and IRNSS[0].
Each satellite adds another constraint, which helps, and with more satellites to choose from, you can drop the weakest or worst measurements.
> The current Android platform supports GPS, SBAS, GLONASS, QZSS, BEIDOU, GALILEO, and IRNSS[0].
But it depends (and varies wildly) on the hardware of said Android. I buy 3 to 5 cheap (sub 100 euro/US$) Androids per year and it always surprises me which device supports which GNSS is supported and how accurate or not they are.
PS I use them to Wigle (https://wigle.net) mainly, and the WiFi reception is exactly as diverse as the GNSS.
There are certain streets in downtown SF where Android (and iOS) location always suddenly jumps to a block away. Navigation apps then direct drivers to make incorrect turns or even dangerous turns like turning the wrong way onto a one-way street.
It seems to me that your software could prevent this error.
Yup! This issue, which is commonly described as the "wrong-side-of-the-street" or "wrong-city-block" error, is one of the biggest ones, and is where a lot of the innovation I mentioned is happening today.
This occurs because in "urban canyons", meaning streets with tall high-rises or sky scrapers, there is little or no line of sight to GNSS satellites (GNSS being the generic term for all satellite positioning systems, not just the American GPS). Consequently, what your phone picks up are signals reflected off of buildings, which exaggerates the distance between you and the satellites, and causes the positioning solution to be pushed away- onto the other side of the street or another city block.
One way Google/Android is tackling this is by using Google's trove of 3D building data, the same that is rendered in Google Earth when you use it in 3D. Your phone uses the building data to correct for reflections. Read on here (and note the authour!): https://android-developers.googleblog.com/2020/12/improving-...
And, the device can use various filters and smoothers to minimize sudden jumps, and normally does, but there are edge-cases (for example, an app may be requesting pure "unfiltered" GNSS location returned directly from the GNSS chipset, hence the jumps). But rest assured, we are working on this issue.
Anyway, thanks for the feedback. We're always doing our best to improve location accuracy and reliability for billions of users in all scenarios and environments, and it's no trivial feat!
I wonder how the inventors of GPS would have responded if back in the early nineties you had suggested to just add a map of all the worlds high buildings to the GPS receiver.
Fun fact: when I was looking into patenting this concept in c. 2007, the prior art search revealed that it had already been patented by someone in Japan in c. 1997.
Amazing to think that ideas people had back when Selective Availability was on for the foreseeable future are just now becoming available to consumers. Congrats on getting it done!
Yes, I was working for a company making standalone car navigation devices (remember those?), amongst other GPS-related things - I also worked on a lot of OEM GPS receivers. There was even a guy (not me!) who had written the firmware for a GPS receiver basically from scratch, so I got a look at everything from the very low level up to the navigation UI.
At this point the iPhone hadn’t come out yet, but building data was just starting to show up the maps we used for navigation.
Trying to predict reflections by processing building geometry sounds very complicated and error-prone.
Wouldn't it be easier to query Google Maps & Waze telemetry for impossible position jumps? Then you could make geofences where Google Play Services ignores position jumps and falls back to Wifi-based location and integrating the accelerometer.
We consider and integrate all kinds of solutions, accounting for building geometry is just one of them, and we do thorough validation to ensure it's actually helping. There's always various tradeoffs being made.
Ideally, clients will be using our Fused Location Provider API [0] which fuses any (or all) of GNSS, WiFi, accel, gyro, mag... with smoothing + filtering to provide the best location possible at any time while automatically managing power compromises; in effect, using WiFi + accel, as you described, along with more signals and filtering. However, some clients still choose to use pure GPS/GNSS, for various reasons.
Part of providing the best location experience possible (while simultaneously minimizing power drain...) is providing high accuracy at every percentile. Some techniques that may improve the average or median percentile error may cause higher errors at the 90% percentile. For example, let's say we check for "impossible" GNSS position jumps, and just ignore those. What if 10% of the time, the position it's jumping to is actually closer to the true position - since suddenly we might have better line of sight - and previously we were stuck at a worse estimate? What might help in one situation might hurt more in another. It's hard to build robust systems to handle every possible scenario and condition (on all sorts of different kinds of hardware from tons of vendors, since anyone can launch an Android device). It's even harder because, as you can image, smartphone grade sensors are magnitudes worse than those you find in survey or military grade hardware.
Also, WiFi-based localization can only be as good as the estimate of WiFi access point location, which isn't always great (and it's usually worse so since WiFi signal strength localization isn't that great), so GNSS is generally higher accuracy under good conditions (and hence rectifying GNSS error wherever we can is one of our goals), and the error of accel/gyro based dead-reckoning grows quadratically/cubically (due to double integration errors), so it doesn't get you very far.
I experienced this as a pedestrian in downtown Chicago (on iOS in my case). It made me curious about what was going on — were the buildings reflecting the signal or obscuring it somehow? It's a fascinating phenomenon.
Here are some fun GPS projects I've found in the past, maybe others can add to this list.
GPS/Galileo/Beidou/Glonass status and error monitoring, open-source community-ran project: https://galmon.eu/
DIY GPS receiver using minimal signal frontend, FPGA Forth CPU for real-time processing and RPi running position solvers: http://www.aholme.co.uk/GPS/Main.htm
How are these interactive visualizations made? As a senior machine learning engineer (with only rudimentary JS skills) it would be fantastically fun to make something like these.
The author wrote his own WebGL library. If you don't have much knowledge about 3D, then https://threejs.org/ is a fantastic library to learn. It abstracts away much of the tedious part.
Not sure what's the best starting point to learn, but there's lots of videos on YT to help you get started.
Of all the reasons, I was stunned with how much detail went into the work at seeing the little globe/Earth in the satellite orbits section -- the Earth has the weather patterns and clouds running in animation as you spin the globe around!
not what he/she uses, but if you are interested in these kind of things, check out https://cables.gl/ .
it provides you with an in-browser, graphical, node based interface where you can just connect boxes together and it will output js-code ready to implement in your website.
There's a lot of really great info in here. One random things I learned from this:
> As that angle increases, the signal from a satellite travels more sideways and its larger portion gets affected by the atmosphere. To account for this, GPS receivers ignore ranges measured from satellites at very low elevation angles. ... atmospheric effects are primary source of GPS inaccuracies.
(I know GPS has inaccuracies, but I didn't really know what caused them, but if I had to guess, the atmosphere wouldn't have been on my list of guesses for the top causes)
Something not mentioned: the "new" L5 signal at 1176Mhz, combined with the existing L1 signal at 1575Mhz, allows the receiver to estimate the atmospheric effects and reduce the uncertainty, allowing for a much better position fix. Think centimeters instead of meters.
One more thing I've wondered: the system depends on the sattelites knowing and broadcasting their exact position, but how do you determine this position? From ground stations, sure, but how exactly? What's the margin of error on that?
And to add to this, how do you bootstrap this?
Galileo had an outage from 2019-07-11 to 2019-07-18 [0]. I've not read much about the details what caused the outage, or why it took an entire week to get back up & running.
The knowledge of a satellite's orbit is taken by using the prior parameters of the orbit, predicting where the satellite will be, and pointing a combination of telescopes (for precise angular measurements) and radars (for precise distance measurements) at this location, and measuring the error between where the satellite is and where it is expected to be. A set of these observations are then used to update the "known" orbit.
This known orbit is then provided back to the satellite so that it can be broadcast. If this system of updates stopped working, the quality of GPS position estimates would degrade pretty quickly (think weeks, not years).
This also means that if a GPS satellite were to need to maneuver for some reason -- either periodically boosting back into its assigned orbit or for debris avoidance -- the normal system of updates will catch this and users will never have to know or care that the satellite moved.
That was a very interesting read, thanks for the link!
From the article:
The outage in the ephemeris provisioning happened because simultaneously:
* The backup system was not available
* New equipment was being deployed and mishandled during an upgrade exercise
* There was an anomaly in the Galileo system reference time system
* Which was then also in a non-normal configuration
So they had to do a cold boot, which is by design slow because it focuses on high accuracy/certainty. Disappointing to read that the collaboration between the involved companies is downright bad in case of emergencies such as this. And the communication is also terrible, there's no public/official report of what exactly went wrong, why it took so long to recover, and what lessons were learned.
It sounds to me that GPS being under military control is an advantage over Galileo.
This is also true for celestial navigation with a sextant and the light refracting in the atmosphere: the "Altitude Correction Tables" give the combined correction for refraction, semidiameter, and parallax under standard atmosphere conditions.
Ionospheric distortions are the largest source of errors in single-frequency solutions! And it's why the WAAS birds transmit a correction model, which all modern (post-2004 or so) receivers can apply.
Multi-frequency receivers can derive the corrections directly because the distortions affect the different frequencies in predictable ways, and they can work back to "ionosphere-free" pseudoranges, and base the rest of the solution on those.
To your quoted comment, nicer receivers also tend to have a configurable "horizon mask" aka "elevation mask", so you can tune this rejection behavior. I could swear I've heard of some that let you configure the mask height _per azimuth_ but I can't find an explicit reference right now.
Elevation masking is tricky because if you crank it up too high, you force yourself into poor-DOP geometries. But if you relax it too low, not only do you get heaping piles of ionospheric distortion, you also invite ground-clutter multipath. I think it's primarily used by stationary timing receivers, because they know their position is fixed, they're less susceptible to GDOP.
Author doesn't mention refraction from varying atmospheric density introducing a non-straight path. Maybe that is negligible for air? It's extremely important for sonar ranging. Lots of things affect water density.
For as long as this blog is, one thing that's missing is a discussion of multipath errors. Multipath errors are when the GPS signal reflects off of buildings or mountains, giving the illusion that the satellite is further away than it is. This is why it can sometimes be hard to get a precise location in cities.
Not only that. You can use a ground-based fixed station to listen to GPS signals and work out how much they have been affected by the atmosphere. This then gets fed back into the weather prediction models used by many weather forecasting services.
There’s an interesting chicken-and-egg problem there. You don’t know what angle the signal is coming from (unless you have some kind of sophisticated multi receiver setup) - so first you need to estimate your position, then figure out whether the satellite is low in the sky, then you can determine whether to trust the timing of the signal from that satellite.
It comes down to the fact that the ingredients we buy from the stores near us tend to come in nice round numbers in our local measuring system, and recipes tend to be tailored to that. For example, "1 cup of shredded cheese and 1lb sausage" may translate precisely to "236.9 mL shredded cheese and 0.45kg sausage", but your nearby store selling metric ingredients may have shredded cheese in a 300mL bag and sausage in 0.5kg packages. So you either measure very precisely and waste food (which makes the recipe a pain to get right), or try to use the local equivalent (and the recipe might not end up tasting the same as a result.) So there ends up being some "art" to doing a proper translation.
For baking, precision is important, but subsequently most recipes are precisely specified, so the conversion should be followed pretty exactly. For most non-baking recipes, precisions is much less important, so a 'recipe translator' could either perform some rounding (maybe there should be a 'level of precision' metadata element for recipes), or, I could just do the rounding in my head and use my critical thinking facilities rather than following the recipe blindly.
One of the things I love about GPS is: Since you know your exact position, you can pick a good GPS satellite (one of the satellite's you're using to calculate your position), look at the timestamp from that satellite, and use it as a highly-accurate time source!
Purpose-built GPS time servers (like those from Meinberg) give you an option to enter the length of the coax cable connecting the receiver and the antenna, so that it can correct for the extra time it takes for the signal to travel over the cable (for example, see https://www.meinbergglobal.com/download/docs/manuals/english... page 19).
My car does this. Unfortunately, it's a Honda/Acura, and there's a downstream bug in the way the receiver sends the info to the clock display that this year, almost all older Hondas/Acura's are reporting the wrong time:
> Honda’s head unit receives a GPS signal for date and time including a number representing a week, coded in binary. These digits count from 0-1024 and rollover to 0 after the completion of week 1024. Honda’s head unit supplier did not code their head units to account for the rollover and, on January 1, 2022, reverted to a date and time 1024 weeks in the past [1024/52 = 19.7, so 20 years in the past or 2002]
So despite all the almost-magic level of engineering that has gone into the GPS system that has stayed consistent for 40-some-odd years, a classic integer overflow has ruined it all because some subcomponent test engineer didn't think to check the inputs against the expected lifetime duration of the car's equipment.
Another fun issue with these is DST databases. The satellites will tell you the time, but it's up to you know how your location translates into a DST zone. And if you have long-running offline equipment (say, a car), and the DST dates change, well, your smarts are only as smart as the update procedure.
It's been said that week number rollover occupies a "sweet spot of awfulness" where it happens infrequently enough that it doesn't get much testing, but often enough to impact equipment deployed in the real world.
The designers of GPS either should've made it use like 64 weeks so WNRO would happen constantly and we'd have to get good at handling it, or 32768 weeks so we could ignore it for the entire life of the system and any successors.
> It's been said that week number rollover occupies a "sweet spot of awfulness"
It's even worse than that: The traditional way of handling week number rollover is a rollover count in nonvolatile memory, incremented every time a rollover is seen (for a standalone receiver there's no other source for how many rollovers there have been)
So a griefer with a software-defined radio can radio out repeated week number rollovers and GPS receivers will increment their rollover counters. In 99% of cases there's no way to decrease them, and now your GPS receiver is convinced it's year 2100.
Perhaps traditional in devices without a UI. My car's stereo (which is where the GPS/nav functions also live) has an epoch dropdown in the settings menu.
Your car does it somewhat different then those Meinbergs. Yes you can get datetime from GPS, but what you really want is a clock signal that triggers 1 PPS.
It's a bit more complex than this, the entire GPS fix is 4D since position depends on time and vice versa. The time reported by a GPS receiver, once fix is attained, is not just the time from one of the satellites but the time resulting from the 4D fix in space and time. This eliminates (to within a certain precision) the latency.
A lot of discrete GPS receivers have some nonvolatile storage where they "cache" fixes to reduce fix time. This has the amusing result that when you buy a GPS receiver and monitor its output immediately you usually find out the time and location where QA was performed, as the first fixes emitted without the quality flag.
Or a test location emitted by QA's satellite simulator.
I have a small list of funny locations I like to pipe into gps-sdr-sim, including Null Island, the north pole, 500 feet above the Kremlin, the middle of Lake Erie, and a quiet beach in the Bahamas.
Not that I expect anyone to look at the first few sentences of output after I hand them hardware, but if they _do_...
I have a hand-held GPS receiver that was last used in Chicago in November. I just turned it on again in another part of the world but inside a reinforced concrete building, where is gets no satellite signals. It still thinks it's at the Chicago airport.
Yup, that's covered by the functions on Pages 20 and 21, which let you either completely wipe all stored state, or update it to account for being moved a long distance (while still retaining satellite data).
Dumb question, but how does this deal with security? Can't anyone broadcast valid but malicious data on 1575.42 MHz? (e.g. to crash planes/missiles etc)
Yes, and there are moves in the next generation to add cryptographic signatures to the satellite streams. Someone could still jam it, but they couldn't spoof it.
One security measure effective against a simple class of GPS spoofing is to check against the satellites' epheremi.
For example, if your RX tells you that bird #7 is part of your location fix, but it knows from prior valid ephemeris data that that bird is currently below your horizon, the bogosity indicator will flash red. Ditto with certain pull-off spoofing methods.
it's already illegal to cause a plane to crash, regardless of the mechanism used, and the legality of the mechanism generally has no bearing on its effectiveness...!
but, gps (or other gndss) spoofing or jamming is effective, and i think that commercially available jammers simply broadcast reasonably broad spectrum noise around that frequency, which can overwhelm nearby recievers; although the article describes how noise rejection is performed, it has its limits. spoofing is more difficult, but still possible, including simple re-broadcast attacks using data received at another location, however i believe these things are non-trivial for military receivers due to countermeasures like beam steering?
If all of the teaching materials would be so good... I've encountered first GPS devices back 1997.i remember when my coulegues were explaining them to me. At that time you wouldn't get precise measurements right away. You had to wait for correction factors or something like that. The GPS signal was scrambled at that time.
In order to determine where you are you need to know where all of the satellites are. For a standalone receiver this involves downloading a almanac of the satellites from the signal, but GPS receivers have small antennas and the satellites don't blast out at tremendous power so the available bandwidth is very low. This means the effective bitrate of a GPS signal is only 50 bits per second so it takes twelve and a half minutes to transmit the entire list.
Cell phones get around this by downloading the almanac from the internet. Standalone receivers also keep the almanac in nonvolatile storage, but the almanacs eventually go stale if you leave the receiver off for too long.
surely you need to know where you are not, to know where you are. if the difference between where you are not and where you were, or vice versa, is correct, then you are being targeted by the missile.
That's post-processing, and it's still done. Here's why:
The satellites only know their own position to a certain precision, and there are only so many bits to express it in the data packet. More bits wouldn't make sense because the measurements aren't that good in the first place.
So what you get "live" is naturally limited by both of those things. Single-frequency unassisted solutions are usually good to a few meters, dual-frequency to a meter or so.
But ground stations can determine, after observing the satellites for a long time, where they _were_ to a much higher accuracy. It's a complicated process involving a whole network of ground stations, whose own positions are precisely surveyed, etc.
The product of that network is known as "precise ephemeris", and it's available in an "ultra-rapid" (3-9 hours later), "rapid" (24 hours later), and "final" (13 days later) version. With these data, the initial observation can be post-processed to get very good solutions. Down into the millimeters.
The RTKLIB manual has a lot more detail if you're curious.
Thanks. Yes, I remember that it took about two weeks to get the final results. I always thought that the data on how much "interference" was added was released with some offset.
The article explains the delay. The satellites transmit their ephemeris data and other important data very slowly, 50 bits per second, so you have to listen to the signals for a long time to get all of it. Not explained in the article is that modern GPS receivers in phones download this data separately from the internet, so they can calculate positions instantly without waiting for the data to finish transmitting.
I think you're talking about receiving a full almanac and ephemeris, and the parent is talking about post-processing. See my parallel comment about PP.
Even sidestepping the internet just handing you a full alm+eph dump, modern standalone receivers can perform a cold-start much faster than their predecessors, because they have huge numbers of receiver channels available. The system operators cleverly offset the almanac being transmitted by each satellite, so if you can receive several satellites at once, you can start writing your almanac with several pencils on the page writing different paragraphs, as it were. Finish the page very quickly.
In the early 90s, it was common for a GPS receiver to have just 4 channels. So a blind search through all the satellite PRNs could take quite a while, and since the receiver didn't know where anything was yet, Murphy's law guaranteed that any satellite it did get a lock on would soon disappear over the horizon anyway. It took agonizingly long to get lucky and hit a bird just coming into view, so you could get whole messages from it and start filling in that table.
And of course any obstructions that limited your sky-view just made it worse.
By the late 90s, 12-channel receivers were fairly common, my first was one of these. This greatly increased the odds of getting useful satellites in a reasonable period of time, and on cold-start it would get a fix pretty reliably in 15 minutes, sometimes less.
In all cases, if the user could give the receiver a hint of the current time (within a few minutes) and location (within a few degrees), as soon as it got part of the almanac it could start figuring out which satellites must be behind the Earth right now, versus which ones would likely be overhead, and make much better use of its receiver channels to shorten the TTFF. Additionally, being able to estimate the Doppler shift greatly shortens the lock-on period.
Today's receivers don't even have discrete radio channels in the old sense, they just have a wide RF front end and then slice the data into digital correlator pipelines, achieving hundreds of virtual channels. True "all-in-view" reception is possible even with four full constellations aloft, and it's nearly magical how good they are. Cold-start times under a minute in some cases.
HOWEVER.
A survey receiver, whose data is being post-processed, need not even calculate its own position. (It probably does, since that costs nothing once the data has been received, but it's not strictly necessary.) It just records carrier-phase measurements and pseudoranges, along with clock and doppler info, in (or later converted to) a format called RINEX. The surveyor just keeps it in one place for a while, marks down "3:32pm-3:38pm, marker C", and then moves to the next point. Later back at the office (once the precise ephemeris comes out), the RINEX is crunched with that better data, and solutions are derived which allow the surveyor to say exactly where Marker C actually is.
This is better than doing it in real time, because the ephemerides available in real time just aren't that good. Only by measuring with a network of ground stations, can the better ephemerides be calculated, and then applied to the observations.
There's also RTK and correction networks, which deserve mention:
Real-Time Kinematic is called that because it tells you about distance and motion, the kinematics, _relative to a nearby base station_. If the base doesn't know where it is, the rover doesn't either. So the base is usually surveyed first, using the techniques outlined above, and then that surveyed position is combined with the kinematic differences, to derive the rover's precise position. It requires a data link between the base and rover, though that's gotten dramatically easier in the last few decades...
Correction networks do all of that, over a wide area, providing a "virtual reference station" nearby to wherever you need it to be. The corrections are transmitted typically over a separate data channel (often on leased L-band satellite time), and applied by the receiver. Some are available over the internet as well, if cellular signal is easy to come by wherever you happen to be. I don't know as much about these as I'd like to.
Modern cell phones use A-GPS (Assisted GPS): https://en.wikipedia.org/wiki/Assisted_GNSS I also remember back in the early 2000s we were using a GPS-quipped PDA as a turn-by-turn navigation device, and for the first ten minutes the device simply asked us to wait.
I was totally inmersed in that animation. I only wish it was longer, It must've account for half of my total reading time. The author is genuinely great and every single one of their posts are terrific.
However, I do like the role GPS plays as a plot device in all kind of stories, where it's an active device, with GPS-enabled devices giving away position or there's no GPS in the wilderness, as mobile connections fail. So there are two versions of GPS, the popular plot device and the actual navigation device.
(The more sinister version is that this has actually been planted as a cover-up for more realistic electronic intrusions, as this is also a trope in popular media and news.)
The original study by Woodford and Nakamura (which laid the foundations for what eventually became NAVSTAR/GPS) has a really fascinating slide where they consider the tradeoffs of alternative configurations. What if GPS receivers had transmitters? What if the mathy computation was offloaded to a nearby ground station? What if every GPS receiver had an atomic clock? Or just a cheap quartz clock? How does that impact the quality of the signal and the number of satellites you need to get a fix?
I think we're really fortunate that they made the choices they did. If they hadn't take the route that was the most complicated technically, GPS wouldn't have become as ubiquitous as it is today.
There's good reason for them to have considered these questions too, as a lot of the satellite-based positioning systems prior to GPS, such as the Navy's TRANSIT, involved both a more active receiver and offloading parts of the work to ground stations. This was very practical at the time, as is TRANSIT fixes were so complex that GE had to design a special computer with a cylindrical chassis so that it would fit through the porthole for installation in submarines. This replaced the previous situation of the submarine having to send its TRANSIT observations to a ground station for fix calculation.
You can still do this with GPS if you want. In the surveying community, it's not unusual to collect an extended period of raw GPS observations (e.g. 48 hours) and then submit them to NOAA's offline GPS computation service OPUS which will return a fix by email a while later. This can result in a more accurate fix but perhaps more importantly a more consistent fix, since OPUS will apply the exact same sophisticated solver used for other government geodetics like survey benchmarks. The tradeoff is that OPUS is slow enough that it tends to run on a queue.
In any case modern GPS involves surprisingly active receivers since smartphones commonly use AGPS over IP to accelerate receiving ephemera.
When I fly, I like to cache a map of the region I fly over on my phone, particularly the airport region at the destination. Then, you can hold your phone to the window for a few minutes and get a GPS fix, even if in airplane mode, because as you say GPS is purely passive.
Then you can follow along nicely where you are, at the resolution you want. (Sure, many airlines have moving maps, but they're not as good as Apple maps or Google maps.)
Once I was flying in the middle section of economy, on a flight without in-flight WiFi, and accidentally opened Google Maps on my phone. I was shocked to find it managed to see enough GPS satellites to provide a lock, which matched the map in the seat back in front of me.
Terrorism isn’t the reason you can’t use cell networks during a flight. Early on it was ostensibly interference concerns but those are not a real problem (if they were they wouldn’t let you carry cell phones onto a plane).
At this point it’s an explicit request from the cell phone companies to not have a plane with 200 people ripping through their cell networks with association attempts that are most likely going to fail and then immediately become stale.
There are way more (real-world) versions than two, with quite a few arrangements that can cancel out some of the systematic error, both with and without inputs requiring a data connection, and with some augmented solutions passively broadcast as "one-way" data.
The funny thing is that the James Bond/ Tomorrow Never Dies plot device has turned out to be the most realistic, but doesn't actually require the theft of some encoding device, with various record and delay replay attacks.
Other underused plot device: lots is made out of over reliance on GPS and what would happen in the event of an attack on the system. But most ignores the fact that the US NAVSTAR GPS constellation is multipurpose, and is also a (confirmed) primary component of worldwide nuke detection, with some (afaik unconfirmed) claims of a missile launch detection capability, as well.
Very nice primer. I worked on the GPS program (first at Boeing, then at a small subcontractor when Lockheed won the GPS III work) - though I worked on the software simulator for the satellites (focused on the operational side of the constellation) so didn't get much into the weeds of how the PNT actually works for clients on the ground :)
As someone who learned about GPS and was impressed by its structure, I used to tell my friends around me, whenever I had the opportunity, how great GPS was.
Now I saw this article and I got goosebumps, well done, thank you very much! It's really fantastic. From today it will be enough for me to just share this article with my friends, or I will tell along with this article.
If you want to explore deeper, there's some fun (and well commented) open source GPS processing codes in Octave/Matlab [1], coming from the excellent book [2]. Those are compatible with cheap RTL-SDRs. [3] also looks nice, but as I recall is Linux only.
One of my favorite engineering tech interview questions is asking an engineer how they think GPS works. You won't believe how many people start with: "Well, your cell phone sends a signal to the satellite......."
Amazing that even engineers don't understand that GPS receivers don't talk to the satellites.
This is going to come across as harsh, but if that is your favorite interviewing question, and you are not hiring GPS engineers, then it is a ridiculous question to ask and serves no purpose but to "haze" candidates.
I think it depends on the job. If this was for an embedded/firmware engineering position, I'd expect a level of EE knowledge that would at least make the concept of everyone's phone sending data to a satellite be a non-starter.
I think it's more relevant than asking an embedded engineer which sorting algorithm is the fastest.
I think you're unfairly assuming something about how the question was used.
If the intent was to find out if people __knew__ how GPS worked when they didn't need it for the position, sure.
However I see two other possibilities:
- How does a candidate react when they don't know something? Do they try to bullshit their way through? Do they admit it and ask what you'd like them to do?
- Can a candidate, __with guidance__, come to a basic understanding of how GPS works and come up with a reasonable (note: not necessarily correct) suggestion for how to implement it?
I agree with the meta interview concept, but I don't think that applies here because of the OP's last sentence:
>Amazing that even engineers don't understand that GPS receivers don't talk to the satellites.
They're amazed at the lack of knowledge, not that a candidate wasn't able to talk it out, or that they bs-ed through it. That tells me the question is asked in bad faith.
Again, that's not necessarily how that's intended. The observation on its own is just an observation, it doesn't indicate anything about how interview performance was evaluated.
For example when I interview, I have a question related to chess, which requires a basic understanding of how the pieces move. I was amazed that even engineers don't understand the basic movement rules of chess.
However as far as the interview went, it was a non-issue. It took about 30 seconds to explain, not a single candidate had a problem with it, and it never came up when I was giving my verdict.
As an interviewer, where there's a huge power imbalance, why even stray into the territory where candidate can easily perceive a disadvantage for not having totally unrelated knowledge? A candidate will feel like their lack of chess knowledge, or GPS knowledge, hurt them if they didn't perform well. Why not just ask questions that are relevant to the work they will be doing? Maybe you don't realize just how stressful interviews are to some people, and how much they have to prepare, only to be asked to reverse engineer how GPS works.
It's very clear in the interview that knowledge of chess isn't being tested. The chess-related exchange is literally about 30s and it's clearly part of the segment where the problem is explained, not the part where the candidate needs to demonstrate their abilities.
As for why, by relating the question to something in the real world (like chess or GPS) a few things are accomplished:
- It gives the candidate an ambiguous situation that they have to navigate away from (e.g. by asking clarifying questions).
- It requires the candidate to map a real-world situation to an algorithmic solution, rather than just being told "implement a graph traversal" or "use dynamic programming to solve this".
- It makes the problem more interesting.
I know exactly what it's like to be on the other side because I was there too not so long ago, solving interviews just like this. I found questions like this much nicer than more obscure questions like Gray code.
I think you're just fixated on this idea that the interview is there to test what you know and not knowing something is a fail but that's not really how it works. What a candidate knows is next to nothing to me, what's most important is how they go about solving the problem. Do they ask questions? Do they consider alternative solutions before digging in? Is their code somewhat readable?
Aside from the basics of CS, I really don't care what they know and that's made reasonably clear before the interview (as it was to me when I was interviewed).
I'll firmly disagree. I find logic questions, and how they solve a problem vastly more important than other aspects of the interview.
I'm often looking for someone I can give a problem to and they return with a potential solution. That involves thinking through problems, how they work, how they can't work, etc.
Asking someone how they think GPS works, or asking them a question about how they'd try to track down a defect based on what a customer is reporting to me are very important skill sets to have.
You've received some flack for this, but I'm not sure the context. If most of the questions in this round are of this nature, then maybe it is a "why are manhole covers round" thing.
But as a one-off, and if asked in a forgiving way to explore how they think, then I'd consider this question valid.
Maybe "Have you ever thought about how GPS works?"
if "yes", then let them explain,
if "no", then make it easy for them to start reasoning about the system and then see how they might design it.
Seems to me as fair as asking "have you ever thought about how a double-linked list works?" or "a basic way to ensure database consistency when the DB is replicated at two different physical machines"?
It's not like GPS is something esoteric that they are unlikely to have interacted with, odds are they used it to get to the interview location.
I don't know about you, but this part of the interview is for me just another annoying obstacle on the way to get the job.
The "Have you ever thought about how GPS works?" question gets a scripted "No, but <blah blah blah>" answer. It's fully automatic, because there are now two possibilities:
- I have thought about GPS before. I will now fake my creative process. No hard feelings, but you are just another obstacle for me to get the job, that's it.
- I have never thought about GPS before. We will now try to design "together" a super-complicated system having so many boundaries and hidden constraints, while I will be also panicking on the inside the whole time. No wait, that would be dumb. I know, I will just refuse to discuss it further. Next question.
(Also, TIL that "flack" in addition to its primary meaning is apparently an acceptable spelling of "flak" too.)
I don't understand why you think linked lists and db replication, which I think are both are very appropriate questions for a software engineer (less relevant to FE engs), are as relevant as how GPS works.
Depends on what you’re evaluating the candidate on. If you’re evaluating the candidates ability to reason through a problem, and communicate the reasoning, the. GPS is arguably a better question for a software engineer as they’re unlikely to have studied it. Thus you can watch them work through a problem they haven’t thought about before, but which should probably have the basic tools to solve.
There should be no expectation of them coming up with the “correct” answer. But they should be able come with an answer and explain it clearly, warts, holes and all.
Using something real like GPS also ensures that the candidate understands why the problem is a useful problem to solve, and what the objective of the solution is I.e. a system that lets you locate yourself on earth.
Only reason I can think of is it is a real world example of distributed coherency/information problem and if you squint hard could give insights into things like paxos (and why it does what it does), why certain types of keying/sharding/distributed computing are done the way they are done.
But directly talking about those topics is probably handy.
Bonus/Followup question: Explain why GPS is not working very well to determine height.
Once you understand the signals are timecoded, this boils basically down on your ability to picture the intersection of multiple sphere in 3D space and it will become obvious (amongst other, very technical reasons that should not be an interview question).
The linked article does neatly, but they use 2D projection (so it's circles not spheres). Very simplified you use the broadcasted position + timestamp of multiple GPS satellites to find your location on the earth. So for a single satellite, you can (using time-in-flight of the signal) estimate the distance to that satellite at a point in time when you received its data. Once you know the distance D to that single satellite, you will know that your position (within margin of error) is anywhere on a sphere with the satellite as its center and radius D (of course this is a bit silly as you know you are definitely not farther away from earth surface as the satellite but rather somewhere 6000-6500km away from Earth center). So when using multiple satellites, you get a set of spheres and (simply viewed) would intersect those spheres - you will be somewhere in this intersection. Now if you can safely assume that your are always on the surface of the earth, you would project this (3d volume) intersection to 2d onto the earth surface - this projection is rather "small" hence less error. But if you would project this intersection using any other 2dimensions, the resulting area would be "wider" in terms of height/depth relative to the surface.
You have to picture those spheres given that the satellites are roughly at same orbital height relative to earth center and you always receive signals within your "field of view" on the nightsky - and of course assume the earth is round.
If the satellites are above (the horizon/field of view), and you're intersecting spheres, it seems to me that you would have the best precision in the height direction and worse precision along the sphere. Am I missing something?
The article has a demonstration that directly contradicts your argument. See the illustration that follows the text "To make things easier to see let’s briefly drop down to a two dimensional case and consider a simplified scenario with signals from just three satellites."
Off the top of my head, I can think of a couple of things it tests for:
* Ability to reflect on and critique their own ideas, using technical common-sense. If someone has never had a reason to research or think too hard about how GPS works, then it might be reasonable to initially assume that it sends a signal to a satellite. But hopefully, when prompted to think about it a bit more, they would realize: "Hey, if that's true, then somehow these satellites that were launched in the 80's and 90's were able to scale up their capacity and handle orders of magnitude more demand, now that everyone has a smartphone in their pocket. Maybe that's not how it works?"
* General curiosity and interest in areas outside their field of specialty. This might not be strictly necessary to get a job done, but it probably has some correlation with other measures of technical aptitude that are hard to probe directly.
> General curiosity and interest in areas outside their field of specialty. This might not be strictly necessary to get a job done, but it probably has some correlation with other measures of technical aptitude that are hard to probe directly.
I think this is a bit misguided, since the scope of things outside of a candidate's field of specialty is tremendously large. Picking a random piece of tech within that space and drilling the candidate about it seems rather unfair.
A better way to handle this would be to actually ask the candidate about what else interests them outside of their specialty. But hey, maybe that doesn't stroke the interviewer's ego enough (:
Fair enough. I understand where you're coming from, at the end of the day I guess it depends on the context and the way the question is presented (left-field questions such as this one can be somewhat fun to try to answer and hypothesize about, if the interviewer creates a friendly environment to do so)
I hear ya. I would definitely not disqualify someone for not knowing the answer.
In fact, someone who is able to sort of work through the problem on the spot may even be preferable to someone who just knows the answer because they happened to read Wikipedia the week before.
Because that’s not a problem you can solve with software and algorithms. That a chemical and lithographic problem that requires a knowledge that rarely overlaps with software.
However GPS can be solved with some high school maths, and applying solutions found on the software engineering domain E.g. computing distance from latency, communicating with a remote resource over a comms link, broadcast vs unicast etc
It’s not like the interviewer is going to ask them to design the satellites and rockets themselves.
Because that's a lot more obscure. A better example might be asking something like "what's the difference between cache and RAM" or "what is a CPU register", which I'm starting to think will still catch objections from some people on the grounds of it not being relevant to Javascript.
Asking how GPS works (in general terms) is more like asking how the Internet works. Anyone who has "engineer" attached to their job title should at have a general understanding of this, or at least be able to work through it using common sense on the spot. I know we covered it early on in college (maybe in Physics, I forget).
Again, I'm not talking about low level details here. Something like "your phone measures the time it takes the signals to arrive and calculates a distance" indicates some understanding. From there, most people can figure out how that information could be used to calculate a 3d position.
>Anyone who has "engineer" attached to their job title should at have a general understanding of this
The fact that the interviewer finds so many candidates who don't answer the GPS question to their satisfaction, while companies complain about difficulty finding software engineers, should tell you all that you need to know about the question's relevancy as well as the bizarre assumptions that some interviews hold.
"Assume you are on a relatively typical unix system, you type `ls -l` and press return, walk me through what happens in as much detail as you're comfortable with."
A decent candidate will give me 5-10 minutes of delving into various parts of "unix processes", maybe "dynamic linking", most probably a bit of "file system" by judicious use of "could you explain that in more detail" or "how does X work".
A truly excellent candidate will have me taking notes for 25-30 minutes, while they pre-answer all my followup questions, go through process creation, dynamic linking, file system API, filesystem internals, maybe some disk layout, process termination and signal handling.
Out of maybe 120 candidates I've asked that question, one (maybe two) have answered it so fully on their own that I did not have to ask any followup questions. And pretty much exhausted my question graph, so once done we could pivot to "do you have any questions for me?".
You either find out the candidate knows how GPS works or you find out the candidate's willingness to say "I don't know".
It's valuable to know how someone will handle a question they don't know the answer to -- whether they recognize their own ignorance and whether they are willing to admit to it.
There are plenty of ways to get to the bottom of what a candidate knows without resorting to unreasonable questions. What you're really testing for is a candidate's patience for being toyed with.
I assume the responses are from people who didn't know that and are now offended that they would've flubbed what the interviewer considered common knowledge in their field. I could see someone thinking it's not a relevant question for certain types of positions, but anyone getting defensive about it is a little bit of a red flag. Anyone doing development relying on location services or navigation systems should have a general baseline intuition for how those things work, even if it's only the broadest strokes. If someone feels angry about not knowing this, well congratulations, you now know this and no longer have anything to get defensive about.
I don't quite understand how such questions help in the hiring process? It reminds me of the famous "why are pothole covers round" question, still not sure what it achieves.
Actually this is a very good question for engineers, as the (wrong) idea that a smartphone regularly sends data to a satellite shows fundamental lack of knowledge in some very basic physical understanding. The basic understanding should be: transmitting/sending = emitting energy (costly if a device runs on batteries), receiving/listening for a signal = almost for free nowadays.
I also like the question because even if you have no idea how GPS actually works, you could quickly come up with the rough idea yourself given that you have a bunch of satellites that can emit arbitrary signals. Lots of room to show creative and analytical thinking here.
> Actually this is a very good question for engineers
What kind of engineers are you interviewing?
> I also like the question because even if you have no idea how GPS actually works, you could quickly come up with the rough idea yourself given that you have a bunch of satellites that can emit arbitrary signals.
I find this really doubtful. Someone who doesn’t already understand how GPS works is unlikely to derive it from first principals in a brief interview.
If you make some simplifications and assumptions such as a GPS receiver has a highly-precise & synchronized clock (it doesnt), you can conceive GPS basically as a system where each satellite simply broadcasts its position & own current timestamp and then determining your position of the earth surface becomes basic triangulation calculating the time-in-flight of the received signal from multiple satellites. Of course a lot of simplifications in there (such as constant signal expansion time), but I would say a system that you could design with basic geometry. The required knowledge is basic physics and math that everybody calling themselves engineers should have heard at uni (or even at school).
You’re still going to wind up assuming a lot of baseline common knowledge that, while it might be stuff you find interesting and have come across in pursuit of your personal brand of geekery, are likely not actually necessary for the job.
Just consider that there are people - perfectly intelligent, capable of learning - who don’t actually know what ‘GPS’ stands for. They maybe don’t know that the GPS system is separate from their phone’s cell connection. They may not even know that satellites are involved. They may have not taken enough of an interest in space technology to have internalized how satellite orbits work, to have intuitions for how orbital speeds and altitudes are correlated. Or they may have picked up a common misconception at some point in the past about how cellphones work, thinking cellphones are always talking to satellites. So they might have made some reasonable intuitions about how GPS works that - because they haven’t been exposed to the true answer - cause them to make some erroneous assumptions that seem like dumb mistakes a poor engineer would make.
Not having had the opportunity to come across those things is not the same thing as not being able to incorporate that knowledge into your worldview when you encounter it.
Ok, but feeding the candidate half of the information is pretty different from coming up with the rough design with “no idea” how it works. Yes, if you basically tell them how it should work, then they can probably figure out how to calculate the time difference and do some trig.
I mean if the candidate would insist that the smartphone sends a signal to the satellite, you can go on and ask "what kind of data?" -"Nothing, just a PING to which the satellite answers with a PONG that contains its position". This is not at all how GPS works, but this system would also work (in a sense you could determine your position on earth based on the RTT + transmitted satellite coordinate). It is not that the candidate should come up with a perfectly correct solution (actually this could be bad because he could just blindly repeat what he/she read without understanding it) - its whether he/she can come up with a solution for the problem at all. In the interview you could still go into discussion about that approach then (what about undirected energy dissipation for contacting a thousands-of-km away satellite, and problems with time-multiplexing transmissions now on the satellite that has to answer individual requests vs broadcast etc.).
I have a hard time imagining engineers in any other field (e.g a structural engineer) would be getting asked questions about GPS as a proxy for general engineering knowhow.
Yes, you will be asked to showcase 2-3 side-projects such as houses, bridges and tunnels you built & designed in your backyard and discuss your design decisions on a whiteboard.
What kind of “engineers”? I’m not aware of most engineers going through this sort of interview. Mostly just software engineers who are indeed programmers even if they get uppity about the title
OK, I'll play. Some qualities that are valuable in an engineer are curiosity, creativity, and general knowledge. If your nomenclature has a programmer as a software engineer and a software engineer as an engineer, then these qualities are also valuable in programmers.
If you ask an interviewee how GPS works and he says something about the cell phone sending signals to a satellite, you would want to pursue that further, at least to make sure that he's asserting that with a sufficiently low confidence.
The thread became about whether a good interview question for an engineer was how she thought GPS works. HeyLaughingBoy thinks that the qualities a question like that seeks to explore are irrelevant for a programming job.
I think that it is a good question for any engineer. One explanation for why HeyLaughingBoy might have disagreed was that HeyLaughingBoy was making a distinction between a programmer and an engineer.
I thought that highlighting the distinction between what HeyLaughingBoy wrote (programmer) and the parent (engineer) was a parsimonious way of expressing this.
Considering GPS was originally created for military purposes, I find it fascinating that the largest holes are over the north and south poles. The northern polar region is where the US-launched missiles and bombers would travel. Does the lesser orbital coverage in that area not negatively affect GPS precision?
Bombers use a similar inertial guidance system, but with updates from GPS and star trackers as applicable. The reduced precision from GPS doesn't matter too much, as the inertial guidance systems are pretty good now.
A surprising number of ICBMs have used star trackers as well! It's somewhat surprising that ICBMs used star trackers before inertial guidance was sufficiently precise. The idea of an automated, high-precision star tracker is not so surprising today but back in the '60s it was quite an achievement.
I don't believe ICBM's are using GPS. They're programmed like they always have been and follow a very predictable path and don't change course (unlike hypersonic missiles). It's the "smart weapons" that are usually plane/ship dropped/launched that are gps guided as they are smaller munitions that have a much smaller blast radius and need to be more precise to be effective (as opposed to just carpet bombing the whole area). Those are "close" range weapons. You don't need to be very precise with an ICBM to obliterate the target, as it's usually city-sized. A mile off here or there will still destroy the target. Planes can and do still fly without GPS. There also haven't been too many wars involving the poles as basically no one lives there except science teams and no one wants the "land" as you can't do anything economically practical with it. Most of our ICBM's are still ancient Minuteman III's which were manufactured in the 1960's (my dad launched one in 68 out of Minot AFB, ND) and recently updated in 2015 to extend their useful life.
If you're interested in the implementation details of a home made GPS receiver, check out this fantastic writeup: http://www.aholme.co.uk/GPS/Main.htm.
They are operational and very compatible with GPS.
Modern devices have them all, the iPhone 13 for examples combines satellite data from GPS, BeiDou, GLONASS & Galileo.
In practice, you get a "super-GPS", with way more satellites (120 vs GPS' 35) and great coverage. Potential accuracy can be in the cm's, it is all about software optimization.
GPS is fascinating, especially the development period.
Due to the complexity of the signal processing (relativity means that the clocks onboard run faster than on earth) there was much scepticism. The story I heard was that they only let them launch 1 Block 1 satellite to prove that could work, and then the first block of 10 satellites was used to validate the system before spending enough to get the full 24 satellites needed.
I'd be interested to see an illustration of how selective availability works -- if your goal is to ensure that a position cannot be determined accurately, how do you alter the signals produced by your satellites to correctly introduce only the desired amount of error?
Selective availability worked by introducing pseudorandom variation into satellite clock used to generate C/A signal, which directly mapped into pseudorange errors.
From the toy model it seems like if in addition to distance you could also get your angle to the landmark then you could get your position from a single landmark. Is that something which is practical? Knowing which angle a radio signal came from? It seems like if you had several receivers you could use the timings of when they receive a message to determine the approximate direction of the satellite in the sky. Given receivers have gotten much cheaper over time, is this a viable extra constraint to improve accuracy?
Determining the angle of a microwave signal requires a pretty big receiver dish (or an array of receivers, at least).
The wavelength of the GPS L1 band is 19cm, you'd need (roughly) something of at least 10x that size to get a good sense of where a signal is coming from, so on the order of 2m.
A single good antenna and sensitive amplifier gets you a fix on more satellites, which provides good accuracy with less space and hardware used.
Assisted GPS in phones can augment GPS data with information coming from cell towers nearby. From a quick search, some are omni-directional while others operate in a specific direction. Depending on reported signal strength, you could get some hints on the angle as well.
How feasible is it to speed up the bitrate used by GPS? This really helped explain why it takes so long to get a position based on how slowly these satellites are sending information.
I never understood what motivates these people to spend so much time and effort making such an amazing blog to educate so many people in such a nice way....It's incredible!
Bartosz is a one of a kind explainer of things - no matter what topic he touches, he always manages to outright nail the communication of the core concepts in a manner almost anyone can understand.
Let alone the interactive visualizations.
There should be some sort of Nobel Prize for people that contribute to humanity’s education - and methods therof.
Organization and presenting information in a uniquely useful way can cement your life as having a major impact on the memetic evolution of human colossus, to a much greater degree than making babies ever will in most cases, even if no one ever knows or remembers your name.
There's a certain satisfaction in knowing that you've made an impact on millions of minds and that that impact will ripple into the future for as long as the light of consciousness burns.
Likely out of love to educate. And/or if you are inclined to look for less altruistic reasons, just his blog presence in HN could bring him a lot of visibility. Every of his amazing posts appeared on first page (disclaimer: I have seen and enjoyed a few, I don't know that for certain.)
This is such a good write-up. Slowly builds on top of what I would consider the very basics of location terms while adding complexity in a digestible way. Excellent illustrations, great examples, and overall an informative teaching tone...
It is worth every minute you spend reading it (took me over 60 to get through it and I feel like I did skim a little towards the end)
Lovely visualization! Reminds me of the principles used by Bret Victor to teach things well - allow the learner to play with time and space of the simulation so they can understand the system fully. Thank you for making this
Bartosz is a one of a kind explainer of things - no matter what topic he touches, he always manages to outright nail the communication of the core concepts in a manner almost anyone can understand.
Let alone the interactive visualizations.
There should be some sort of Nobel Prize for people that contribute to humanity’s education - and methods therof.
Yes what an absolute solid educational interactive, from presentation to code to writing and simplicity.
Additionally the code level, If you view the source you can see, nice clean, non-minified code that is clear and has no dependencies other than browser/render standards. The project simply has a base.js and a gps.js, base for common canvas tools and gps for the project/interactives.
Very nicely done and very refreshing to see and experience. We need to get back to this level, it was a simpler higher level with more innovation. Even HN's code is this way, partially why this site is great besides the contributors and curation.
Engineering/creative and good value creation is ultimately taking complexity and making it simple, this is right along those lines in every aspect.
Simple is beautiful and very difficult to achieve in a cluttered/distracting/dependency/minimal context overload world. This interactive nails it. Solid work Bartosz Ciechanowski!
@dang Why was this suddenly pushed to the bottom of the comments? (After being second in rank.) Possibly a bot detection false positive. Hope this is fixed so the author gets the reward he deserves for this amazing work
The really neat stuff is in the details, like when the elastic rope curls. – We have somewhat forgotten how important these details are, even in infographics. Let's call this "interactive texture".
(see the excellent example in OP)
Fun tidbit, the resulting error is known for the system in closed form as Geometric Dilution of Precision, and is a 3x3 (edit: or 4+x4+ if you are estimating bias or quantities like time, thx brandmeyer) matrix that depends on all the locations of the visible sats, and your position relative to them.
GDOP is a general relationship for any estimator based only on the equations used to derive something from sensor remote sensor measurements. It's possible to derive GDOP for any sensing system using the Fisher Information Matrix (which is the inverse of GDOP). Some minor caveats apply, but in general this is a useful trick.
FIM is worth learning if you want to get into sensing & estimation. https://en.wikipedia.org/wiki/Fisher_information
Another fun thing: FIM can be derived a number of ways, and appears if you simply ask (mathematically) "What is the most likely position of the gps sensor given sat locations" as the hessian matrix of the system that you use while answering that question using e.g., convex minimization.
All of sensing & estimation is just mostly convex optimization.