Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have a question on the GPS positioning algorithm. In all books I've read for 3D positioning we need four satellites, and I don't understand why.

We need to calculate three variables: x, y, z. We know when satellite send the signal to earth and when we receive it we can measure the time the signal travel to earth by checking the shift in PRN generator. For what purpose do we need four satellite?

share|improve this question

8 Answers 8

up vote 34 down vote accepted

Just a graphic to add to M'vy's answer.

From Geocommons:

enter image description here

This is a high-tech version of triangulation, called trilateration. The first satellite locates you somewhere on a sphere (top left of Figure). The second satellite narrows your location to a circle created by the intersection of the two satellite spheres (top right). The third satellite reduces the choice to two possible points (bottom left). Finally, the forth satellite helps calculate a timing and location correction and selects one of the remaining two points as your position (bottom right).

Update

As R.K. points out, this is not a form of triangulation. Even when GPS is leveraging more than 4 satellites, it is still doing trilateration, as opposed to multilateration, which GPS does not use.

Multilateration should not be confused with trilateration, which uses distances or absolute measurements of time-of-flight from three or more sites, or with triangulation, which uses the measurement of absolute angles. Both of these systems are also commonly used with radio navigation systems; trilateration is the basis of GPS.

share|improve this answer
    
+1 Nice graphic. I have an issue with the quoted text though. Trilateration is not a high-tech version of triangulation. It's a totally different beast. –  R.K. Nov 14 '12 at 14:23
    
cool graphic @kirk –  Ragi Yaser Burhum Nov 14 '12 at 20:21
1  
technically you can leave out the 4th if you assume you at the point which is closer to 6,371 km away from the center of the earth (only works for ground bound devices) –  ratchet freak Nov 19 '13 at 15:42
3  
I think this answer is technically incorrect. For GPS to work, your receiver generates the same codes the satellites generate, and it compares the one generated with the one received in order to compute the time difference, and hence distance from the satellite. For this to work you need to know TIME. (An aside, GPS time is very, very precise.) The minimum number of satellites required to work out your position is 4, because you're solving for X, Y, Z and TIME. YOu do get an ambiguous position, either on the Earth's surface or up in space, you can trivially dismiss one of these. –  alexgleith Apr 2 at 0:57
    

Oh Dear, oh Dear, Oh Dear - we are all in a muddle aren't we? Some of the answers are close, but not entirely clear.

While I was part of a 3 man team which spent 2 years in the early 90's developing the first non-military differential GPS stations in the South West of England, we came across some extra-ordinary questions. 3 or 4 being one of them.

To explain this, it is best to start with a terrestrial radio navigation system. Take one signal from a fixed known point (Station#1) on the beach and beam it at a ship at sea. The ship knows for how long the beam has been traveling and the exact location of Station#1 - it knows this because the time the beam left the fixed point is imprinted on the transmitted signal - e.g (started at 'A'seconds and was received at 'B'seconds) - therefore, given the speed of light (C) of radio waves the ship must be (B-A) X C from the Station#1 - this answer is Range1.

Take another known point Station2 from which started a signal at the same time 'A'seconds - but Station2 is on a different known point which gives Range2. From Range2 you know that your ship lies along Range1.

Do the same with a 3rd Station and you get an intersection of all 3 Ranges. But they do not intersect perfectly ... ever !!!!

This is due to atmospherics, interference, propagation delays which affect all radio waves. The intersections of the 3 ranges give you a triangle of error (hence triangulation) on a 2 dimensional plane (X and Y - LAT AND LON or Northing and Easting). Now, in order to get your elevation (H) you require a fourth Range (you guessed it - Range4) which will give you a 3Dimensional location - X Y and Z - LAT LON and Height.

Now take all of your Stations and stick them in Space - hey presto !!!!!! GPS !!!!!! And your ship is positioned somewhere inside a 4 sided 3D triangle of error which is slightly curved on all sides :-)

share|improve this answer

All this talk of "intersecting spheres" cannot possibly be true. Here's why.

  1. When you receive the signal from one satellite you know where it is because that information was transmitted in the message and also precisely at what time it was sent. In the GPS system all the atomic clocks are kept in sync via control signals from the ground to an accuracy of plus of minus 3 nanoseconds. But you can't compute YOUR distance to the satellite, and hence the sphere, because your local time is not the same. If local time is out of sync with satellite time by just 1 millisecond, because light travels at 299,792,458 metres per second, this translates to a distance error of about 300 kilometres!
  2. With two satellites you can compute the RELATIVE distance from the two satellites by computing the differences between the transmission times of the two messages, and local time. So you can plot your position along a hyperboloid in three dimensions. The surface of the hyperboloid describes all the positions in space where the two time differences make sense and where you could be.
  3. With three satellites you can compute TWO hyperboloids. Their intersection is a hyperbola. You can be anywhere along it.
  4. With four satellites you can compute the intersection of THREE hyperboloids, and derive your position in space, discounting the effects of atmospheric delay.

To consider atmospheric delay you need to compare the delays of two signals sent at different frequencies from the same satellite or compare the readings of the same signal seen from two different locations ("differential GPS"). Modern GPS systems correlate the two encrypted military signals at frequencies L1 and L2 to obtain this information.

share|improve this answer
    
I'm having trouble understanding your statement: All this talk of "intersecting spheres" cannot possibly be true Which Part of the statement do you an issue with? The sphere part? or something else? –  Devdatta Tengshe Apr 2 at 3:39

>>3 satellites would be enough


Global positioning system(s) assume an 'earth centered, earth fixed, x-y-z 3D cartesian coordinate system'. Any location in this 3D space requires no more than 3 components to be completely identified. So, even though 3 spheres we obtain by 3 distance measurements intersect at two different points, one of those points is rendered useless by [ earth centered + earth fixed ] characteristic of the coordinate system GPS assumes; we are interested in locations below the earth's atmosphere. 3 satellites could be used to determine 3 position dimensions with a 'perfect' receiver clock (with an expensive atomic/optical clock).

!YES!, you !could have gotten! a 3D position fix with 3 satellites IFF the GPS receiver you are using was equipped with an atomic clock. (The ELIMINATION of the second point, on the bottom left figure of the illustration above, is done "intuitively" as it corresponds to someplace in DEEP SPACE. BECAUSE, there is a reason why GPS satellites are at their specific constellation (~their setup in the sky): !more than! 24 GPS satellites, on 6 orbital planes that are ~20,000 kms above you, and 4 satellites on each plane, 60 degrees between these planes, and 55 degrees inclination with respect to equatorial plane, GIVES YOU 5-8 satellites that you can "connect to" from (almost) any place on earth, and 3 SATELLITES TO GIVE A 3D POSITIONAL FIX ON EARTH. If we are talking about locating things "inside AND outside" of earth, WELL THEN YES, you need at least 1 more satellite to eliminate one of two possible intersection points in the last step. This wasn't the question, was it?

In practice, placing expensive clocks in GPS receivers is rarely possible/feasible and 3 space vehicles (SVs, i.e. satellites) can be, instead, used to compute a 2D, horizontal fix (in latitude and longitude) when a certain height (e.g. z-dimension) measurement is ASSUMED; so you get rid of 1 dimensional measurement out of 4 that were originally required. Assumed height can be either the sea level or the altitude of a (normally) altimeter equipped aircraft.

It is the height dimension that is chosen to be discarded, because it is the (relatively) least important one among others. Among the 4 required dimensional mesaurements (x,y,z,time), time always needs to be resolved BECAUSE satellite signals (electromagnetic waves) travel at the speed of light and reach receiver in ~0.07 atomic seconds; and thus, a slight inaccuracy in the GPS receiver's relatively cheap internal clock would give a "very wrong" locational fix because of the extra distance the signal is assumed to travel at the extreme speed of light. And, well, the other two dimensions will place the GPS receiver on some (longitude,latitude) pair on the surface of the planet.

More than 4 satellites provide better accuracy by introducing additional 'time difference pairs'. 4 dimensional requirements remain, yet number of independent equations increase and exceed 4. This will result in an over determined system of equations with multiple solutions. Over determined systems are !approximated! with numeric methods, e.g. least squares. In this case, the least squares method will give the position (of GPS receiver) that best fits all of the time measurements (with extra dimensions) by minimizing the sum of the squares of errors.


(1) Global Positioning System Overview, Peter H. Dana, Department of Geography, University of Texas at Austin, 1994.
http://www.colorado.edu/geography/gcraft/notes/gps/gps_f.html
(The Master GPS Control facility is located in Colorado, Schriever Air Force Base)

(2) Position Determination with GPS,Dr. Anja Koehne, Michael Wößner,Öko-Institut (Institute for Applied Ecology),Freiburg im Breisgau, Germany
http://www.kowoma.de/en/gps/positioning.htm

(3) An Underdetermined Linear System for GPS, Dan Kalman
http://mathdl.maa.org/images/upload_library/22/Polya/Kalman.pdf

(4) For the colorful illustrations
http://www.colorado.edu/geography/gcraft/notes/gps/gif/figure09.gif
http://www.colorado.edu/geography/gcraft/notes/gps/gif/ecefxyz.gif
http://www.colorado.edu/geography/gcraft/notes/gps/gif/gpsxyz.gif
http://www.colorado.edu/geography/gcraft/notes/gps/gif/navigate.gif



>> INaccuracy


" Four sphere surfaces typically do NOT intersect. Because of this we can say with confidence that when we solve the navigation equations to find an intersection, this solution gives us the position of the receiver along with accurate time thereby eliminating the need for a very large, expensive, and power hungry clock. "
http://en.wikipedia.org/wiki/Global_Positioning_System#Basic_concept_of_GPS

It says "typically" BECAUSE the measurements are INaccurate; otherwise they would intersect at exactly one point. From 4 satellites, you get 4 INaccurate distance measurements. INaccuracy in all these 4 measurements are SAME (=in the same amount) BECAUSE satellites use atomic clocks which keeps them perfectly syncronised among themselves (and accurate with respect to GPS time scale), additionally, the INaccurate clock in the measurements remain the same too, because we are talking about one particular GPS receiver. Since accurate and INaccurate clocks, and thus the INaccuracy, is constant in our measurements, there can be only one correction value that reduces the volume of intersection of 4 spheres to a single point of intersection. That value represents the time INaccuracy.


(5) The UTC clock is currently (2012-11-14) 16 seconds behind the GPS clock.
http://www.leapsecond.com/java/gpsclock.htm

(6) How a GPS Receiver Locks, Thomas A. Clark, NASA's Goddard Space Flight Center
http://gpsinformation.net/main/gpslock.htm

(7) How Accurate is a Radio Controlled Clock?, Michael A Lombardi, NIST-Time and Frequency Division, Maryland
http://tf.nist.gov/general/pdf/2429.pdf

share|improve this answer
    
Thank you for these clarifications. Welcome to our site! (BTW, one least squares method is described and illustrated in a reply at gis.stackexchange.com/a/40678. Although the context is 2D positioning, the solution applies to any number of dimensions.) –  whuber Nov 14 '12 at 13:17
    
Wow. The readability of this answer would be much improved if the crazy formatting and capitalisation was removed. I'm a bit scared to attempt it myself though.. –  naught101 Dec 9 '12 at 5:31

You actually need to determine four coordinates from the satellites, x, y, z, and t, the time.

You cannot use the clock inside the device, because it is much too inaccurate. It is generated by a quartz crystal, while for the desired precision of a few meters you'd need an atomic clock, like those used in the satellites.

share|improve this answer
    
You need four satellites to determine the 3D position, in the same way that you need at least three points to determine a third point on a plane, given only distances. Once you have the position, you only need one satellite to determine the time. –  naught101 Dec 9 '12 at 5:29

The major reasons why you need a fourth satellite is for timing corrections. If you know the exact position and speed of the satellites, trilateration will give you indeed 2 points, but one will usually be impossible or with an impossible speed. But a gps receiver uses the time it takes to receive a sattelite signal to determine the distance to that satellite. Even minor errors in the time of your gps receiver will cause huge errors and therefore a large uncertainty band when you have only three satellites.

share|improve this answer

You need four satellites because each data from one satellite put you in a sphere around the satellite. By computing the intersections you can narrow the possibilities to a single point.

Two satellites intersection places you on a circle. (all points possible)

Three satellites intersection places you on two possible points.

The last satellite give you the exact location.

You can avoid using four satellite if you already know the altitude, for example when you drive, you can use the ground level as the last intersection. But you can't possibly do this in a plane, since you are not bound to the ground.

share|improve this answer
    
ground level also varies in height, in the extreme cases by about as much as a plane, so how is altitude of ground level known? –  jk. Jul 31 '11 at 11:09
    
@jk if you have a driving map on your GPS device, it knows the ground level located near the two solutions you have. One should definitely be better than the other. –  M'vy Jul 31 '11 at 13:13

The fourth satellite is there just to increase accuracy to a point where it would be useable. Although, with 3D Trilateration this is not necessary to calculate a location. GPS although requires this because of the accuracy issue.

Resources:
3-D Trilateration
Trilateration
GPS

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.