10/26/2014 -- How does a GPS device know your location?

posted Nov 16, 2014, 6:28 PM by Patrick Poole   [ updated Nov 16, 2014, 7:43 PM ]
Nearly everyone with a phone these days has a Global Positioning System (or GPS) device right in their pocket--something that can tell them their location within about 50 feet. Most people know that these devices operate in conjunction with satellites in orbit, but the details that go into this calculation reveal some of the intricacies of geometry.

It's tough to think about 3D images in your head, so I've changed the format of this post a bit--I'll be predominantly using images to illustrate how each subsequent satellite signal narrows down your location.

GPS satellites orbit the Earth and constantly emit signals that can be picked up by your device
GPS signals

Let's start by thinking about the problem: the Earth roughly a sphere, which is a three dimensional (3D) object. If it were a perfect sphere and we lived on the surface then our problem would be a bit simpler, because the surface of a sphere is a simpler 3D object (it's really just a 2D sheet wrapped around onto itself). We have plenty of different elevations on the real Earth, though, and what's more we'd like to use our GPS devices on airplanes. In that case we care about our elevation, which brings us back to determining our location anywhere in 3D space.

GPS satellites are always emitting signals, as depicted in the cartoon above. These satellites are constantly broadcasting two pieces of information: their location in the sky relative to the Earth, and the time that they emitted the signal. These signals can be picked up by GPS receivers on Earth. At any given time your receiver is likely watching 9 or more GPS satellite signals, so it has a list of signal locations and times those signals were sent.

Your GPS receiver can tell how far away it is from a satellite using the sent time signal and the speed of light

The signals being sent are electromagnetic waves (just like radio waves, or microwaves, or light, but with a different wavelength), so they always travel at the speed of light.So when your device receives a signal it can subtract the time the signal arrived from the time the signal was sent (which was transmitted as part of the signal) and, using the fact that it knows how fast the signal moved, determine exactly how far the signal must have traveled.

One satellite signal pinpoints your location to the surface of a sphere around that satellite

Here comes an important part: your GPS device now knows how far away it is from this one satellite, but it doesn't know in which direction. In other words, there is a sphere of possible locations centered on the satellite with a radius of this distance calculated by your device. Now most of this sphere is off in space, and if you were looking at an image like the one below you could instantly tell that, but the important thing is that the GPS receiver doesn't know this. It doesn’t need to, as I'll explain below, because it has other GPS satellite signals to rule out these incorrect locations. In this way the GPS receiver software can be very simple, and thus make quicker calculations and updates. Note that even this one signal is not bad--you've narrowed down your location from anywhere at all in three dimensions to somewhere on the surface of a sphere.

Circles and spheres

The signal from two satellites determines your location down to a circle

If two satellites in two different places each sent signals then they have different location spheres, and together they know the signal must have originated from somewhere that those two spheres touch. So as soon as your receiver detects two satellite signals, it’s ruled out a large set of possible locations that are off in space. Below on the left I've drawn two satellites orbiting the Earth with orange location spheres, and on the right there is a cartoon showing how two overlapping spheres touch to form a circle--in mathematics we'd say that the intersection of two spheres is a circle. This extra satellite has narrowed down your possible location by one dimension: from the 2D surface of a sphere to some position on a circle, which is a 2D object.

2 sphere intersection

Note that it’s possible for the two spheres to touch at exactly one point, which would then give you the correct answer from only two satellite signals, but that requires you to be exactly in between the two satellites. This likely won’t ever happen, and if it did it would only be for a moment—remember the satellites are orbiting the Earth this entire time, in a number of different directions. Note also that it’s possible for two spheres to intersect at every point, but only if they have exactly the same center—this could only happen if two satellites crashed into one another, and in that case they probably wouldn’t be sending anymore signals.
Three satellites pins you down to two points

Now add in a third satellite, like in the figure below. This time we’re interested in the intersection of this new sphere with the circle of possible solutions from the intersection of the first two satellite signals. If the sphere just touches the edge of the circle, there’s only one solution and we’re done, but again this is unlikely. Most of the time there will be two possible point solutions (the red x's below) because the sphere touches this circle at two points. One of them is probably obviously wrong--in space or underground--but again the GPS receiver doesn’t know that.

3 spheres now

It’s possible for there to be four intersections if the sphere is smaller than the circle, but that would mean the satellite was sending its signal from somewhere on the ground very close to you, which probably isn’t the case--unless maybe it crashed into another satellite during the last step and you’re on the recovery team.

Finally, a fourth satellite determines your location exactly

A fourth satellite will be able to determine which of the two possible points is correct, because its signal will only touch one of them, as you can see in the figure below. At this point your GPS device knows your location!

4 spheres!

Bonus mathematics—Dimensionality

The idea of how many dimensions an object occupies (or, how many numbers it takes to describe it's location) is an important one in both mathematics and physics. As we were adding more satellites for our receiver to detect we were decreasing the possible locations by cutting down dimensions, like when the second satellite took the possibilities from a spherical surface (2D sheet wrapped around on itself into 3D) to a circle (1D line wrapped around on itself into 2D). When we narrowed our search down to two points, how many dimensions do you think one of those points had? Hint: a 3D object can be described by it's length, width, and height, for example--which of these does a point have? Look at the images here for the answer.

Advanced physics—GPS and Einstein's theory of relativity

Many people have heard of Albert Einstein's theories, and think of them as complex and hard to grasp. This isn't really the case, and I have a planned post describing these fascinating ideas in relatable terms, but here I just want to mention their interesting consequence for GPS systems.

Einstein’s theory of General Relativity says clocks that experience different amounts of gravity will experience time slightly differently. There is just a tiny bit less gravitational field up where the GPS satellites orbit, and so these satellites will disagree slightly with ground-based clocks on how fast time is passing. They account for this by sending a slightly modified signal for their timestamp. Einstein's other theory, Special Relativity, matters as well: this one says clocks moving faster experience time differently than slow moving clocks. This is certainly the case for GPS satellites in orbit--they are moving around 14,000 kilometers/second faster than Earth-based receivers!

The combination of these two effects causes GPS satellite clocks lose about 35 milliseconds each day compared to Earth-based clocks. That’s a small amount, but the speed of light is 300,000,000 meters/second, or about a foot per nanosecond—so being off by 1 millisecond = 1,000,000 ns can ruin your measurement by 1000 feet. In other words, only a few minutes of non-relativity-corrected satellite signals would render GPS useless!