Global Positioning System - Position Computation Fundamentals

GPS Positioning and Navigation Mathematics Introduction Global Positioning System (GPS) receivers determine their location by measuring signals from multiple satellites orbiting Earth. The fundamental challenge is that we need to find three spatial coordinates—latitude, longitude, and altitude—but we have an additional unknown: the receiver's clock bias. This means we need measurements from at least four satellites simultaneously to solve for all four unknowns. Understanding how GPS converts satellite signals into accurate position fixes requires knowledge of pseudorange measurements, the geometry of sphere intersections, and numerical solution methods. Pseudorandom Codes and Pseudorange Measurements How Pseudorange Works Each GPS satellite continuously transmits a known pseudorandom code—a specific sequence of ones and zeros that repeats in a predictable pattern. Your GPS receiver generates an identical copy of this same code locally. By comparing when the satellite's code arrives with when the receiver's local code starts, the receiver measures the time delay. Multiplying this time delay by the speed of light gives the pseudorange ($pi$): $$pi = c \cdot \Delta t$$ where $c$ is the speed of light and $\Delta t$ is the measured time delay. The Clock Bias Problem Here's the critical issue: the receiver's clock is nowhere near as accurate as the satellite's atomic clocks. This means the receiver's local time can be off by milliseconds or more. This time error directly translates into a distance error in the pseudorange measurement. Mathematically, we express this as: $$pi = di + b$$ where: $pi$ is the measured pseudorange from satellite $i$ $di$ is the true geometric distance from satellite $i$ to the receiver $b$ is the receiver clock bias (distance equivalent): $b = c \cdot \text{(clock error)}$ The key insight is that the same clock bias $b$ appears in every pseudorange measurement, since all measurements come from the same receiver. The Navigation Equation System Setting Up Four Equations, Four Unknowns To find a receiver's position, we need to determine three spatial coordinates ($x$, $y$, $z$) and the clock bias ($b$). That's four unknowns, so we need at least four equations. Each satellite provides one equation. For satellite $i$, the geometric distance is: $$di = \sqrt{(x - xi)^2 + (y - yi)^2 + (z - zi)^2}$$ where $(xi, yi, zi)$ are the satellite's coordinates (which are known). Combining with our pseudorange equation gives: $$pi = \sqrt{(x - xi)^2 + (y - yi)^2 + (z - zi)^2} + b$$ With four satellites, we have four such equations. Although these equations are nonlinear (due to the square root), standard numerical techniques can solve them. More Than Four Satellites: Least-Squares Solutions In practice, GPS receivers can see many more than four satellites. When we have $n > 4$ measurements, the system becomes overdetermined—we have more equations than unknowns. This is actually advantageous. Rather than forcing an exact solution, receivers use least-squares fitting to find the position that minimizes the sum of squared errors: $$\text{minimize} \sum{i=1}^{n} (pi - di - b)^2$$ This approach automatically rejects measurement outliers and reduces the impact of random noise. The result is a more accurate position estimate than any single exact solution could provide. Why Not Just Three Satellites? A natural question: if we only need three spatial coordinates, why not use just three satellites? The answer reveals the elegance of the system. Without the clock bias ($b = 0$), three satellites would suffice—they would define the intersection point of three spheres. However, because the receiver clock is inaccurate, we cannot ignore $b$. The fourth satellite constraint is essential for solving this fourth unknown simultaneously with the position. Geometric Interpretation: Spheres, Hyperboloids, and Trilateration Trilateration with Perfect Clocks Imagine a perfectly synchronized receiver clock ($b = 0$). Each pseudorange measurement would equal the true distance, so we'd have: Satellite 1: Points lie on a sphere of radius $p1$ centered at satellite 1 Satellite 2: Points lie on a sphere of radius $p2$ centered at satellite 2 Satellite 3: Points lie on a sphere of radius $p3$ centered at satellite 3 The receiver's position is at the intersection of these three spheres. Mathematically, two spheres intersect in a circle, and that circle intersects a third sphere at (typically) two points. One point is the receiver's actual location; the other is usually far from Earth's surface and is rejected. The Role of Clock Bias: Hyperboloids Now consider imperfect clocks. Subtracting one pseudorange from another cancels out the common clock bias $b$: $$pi - pj = di - dj$$ This equation describes a hyperboloid of revolution—the set of all points where the distance difference to two focus points (the two satellites) is constant. Each pair of satellites defines a hyperboloid. With four satellites, we can form three independent difference equations, giving us three hyperboloids. The receiver's position lies at their unique intersection point. The Insphere Interpretation There's an elegant geometric way to visualize the role of clock bias. Imagine: Four spheres centered at each satellite, with radii equal to the measured pseudoranges An "insphere" (inscribed sphere) centered at the true receiver position The insphere has radius $r{\text{in}} = c \cdot b$ (the clock bias converted to distance). The receiver position is where this insphere internally touches all four outer spheres. Since each outer sphere has radius $pi$ and is centered at satellite $i$, the distance from the receiver to satellite $i$ equals $pi - r{\text{in}} = di$ (the true distance). Solving the Navigation Equations Nonlinear Problem Formulation The navigation equations are nonlinear due to the square root in the distance formula. Standard approaches exist: Iterative Methods (Gauss–Newton) Start with an initial guess for $(x, y, z, b)$, then: Linearize the equations around the current guess Solve the linearized system Update the guess Repeat until convergence This method generally provides high accuracy and handles overdetermined systems naturally when combined with least-squares. It requires a reasonable initial guess (often based on previous position or approximate satellite geometry). Closed-Form Methods (Bancroft's Algorithm) Bancroft's method reformulates the problem algebraically. The key steps are: Express the equations in a form that involves a $4 \times 4$ matrix Invert this matrix Solve a single quadratic equation The quadratic yields one or two mathematical solutions; the physically realistic one is selected (typically the solution closest to Earth's surface). Bancroft's method is computationally fast because it doesn't require iteration, making it useful when computational resources are limited. Comparison Iterative methods: Generally more accurate, especially in good satellite geometry; require computational resources for multiple iterations Closed-form methods: Faster (one-pass computation); slightly less accurate in poor geometry; more robust since they don't require a good initial guess Handling Overdetermined Systems With more than four satellites, both methods extend naturally: Iterative methods solve via weighted least-squares iteration The Bancroft method can be generalized, though the computational advantage diminishes Geometric Dilution of Precision (GDOP) What GDOP Represents Even with an accurate pseudorange measurement from every satellite, your final position error depends critically on satellite geometry. Geometric Dilution of Precision (GDOP) quantifies this effect. The relationship is: $$\text{Position Error} = \text{GDOP} \times \text{Pseudorange Measurement Error}$$ If GDOP is small, good satellite geometry means measurement errors don't translate much into position errors. If GDOP is large, poor geometry magnifies measurement errors. When GDOP is Good or Bad Good GDOP (low value): Satellites are well-distributed around the sky—some high overhead, some near the horizon, spread across all compass directions Poor GDOP (high value): Satellites are clustered in one part of the sky (e.g., all in the northern sky for a northern hemisphere receiver) Intuitively, clustered satellites provide redundant information; satellites spread around the sky constrain the position from many independent directions. <extrainfo> GDOP Components GDOP combines separate dilution factors: HDOP (Horizontal): affects latitude/longitude error VDOP (Vertical): affects altitude error TDOP (Time): affects clock bias error The relationship is: $\text{GDOP}^2 = \text{HDOP}^2 + \text{VDOP}^2 + \text{TDOP}^2$ </extrainfo> Error Sources and Receiver Tracking Major Sources of Position Error Beyond pseudorange measurement noise, several physical phenomena degrade GPS accuracy: Atmospheric Delays: Signals pass through the ionosphere and troposphere, which slow the electromagnetic wave. This causes the signal to arrive later than it would through a vacuum, inflating the measured pseudorange. Modern receivers use models and dual-frequency measurements to correct this. Multipath Reflections: Signals can bounce off buildings, ground, or other surfaces before reaching the receiver. The reflected signal arrives later than the direct signal, creating a delayed copy that corrupts the pseudorange measurement. Satellite Geometry: As discussed under GDOP, poor satellite positions multiply the impact of any measurement error. Receiver Clock Instability: Even though we solve for clock bias, an unstable clock can cause errors that vary with time. Tracking Algorithms: Combining Multiple Measurements Rather than computing position from a single set of four pseudoranges, practical receivers use tracking algorithms that combine successive measurements over time. These algorithms: Improve accuracy: Multiple measurements are combined statistically to reduce random noise Reject outliers: Bad measurements (e.g., from multipath) are identified and downweighted Estimate velocity: By tracking how the receiver's position changes, the receiver computes velocity and can predict future positions Common approaches include Kalman filtering, which optimally balances the noisy measurements with predicted motion. Modern Enhancements and Integration Assisted GPS (A-GPS) GPS's main limitation is the time-to-first-fix—the time required to acquire satellite signals, download ephemeris data (satellite positions), and compute the first position fix. This can take 30 seconds or more for a cold start. Assisted GPS reduces this time by using auxiliary data from external networks (typically cellular networks): Cellular network provides rough receiver location to narrow search area Ephemeris data is downloaded from network rather than waiting for satellite transmission Receiver searches only the relevant part of the pseudorange/Doppler space Result: Time-to-first-fix drops from tens of seconds to seconds or less. Multi-Sensor Integration Modern receivers often integrate GPS with: Inertial Navigation: Accelerometers and gyroscopes provide continuous position/velocity estimates during GPS outages or when signals are weak Compass: Magnetic heading helps resolve ambiguities in velocity direction Other sensors: Barometer (altitude), odometer (ground vehicles), or cellular positioning These integrated systems provide robust positioning even when GPS signals are partially obstructed. <extrainfo> Doppler Shift Measurements As satellites move relative to the receiver, their transmitted frequency is shifted (Doppler effect). Receivers can directly measure this frequency shift to estimate velocity without needing to track position changes over time. This is particularly useful for: High-speed platforms (aircraft, missiles) Brief GPS encounters with limited measurement time Continuous velocity estimation independent of position solutions </extrainfo> Coordinate Reference Systems GPS positions must be expressed in a well-defined coordinate system. The standard for GPS is WGS 84 (World Geodetic System 1984), which defines: A reference ellipsoid (approximation of Earth's shape) Latitude/longitude coordinates on that ellipsoid Altitude above sea level When your GPS receiver displays "40.7128° N, 74.0060° W" (coordinates of New York City), it's giving latitude and longitude on the WGS 84 reference ellipsoid. Different countries have historically used different reference systems, but WGS 84 is now the global standard. Key Takeaway: GPS positioning is fundamentally a problem of solving four simultaneous nonlinear equations for three spatial coordinates and a clock bias, using measurements from at least four satellites. The elegance of the system lies in how it automatically calibrates the receiver's clock while determining position, and how additional satellites beyond the minimum four improve accuracy through least-squares methods. Modern implementations enhance this basic principle with tracking algorithms, sensor integration, and assisted data, making GPS a reliable navigation tool even in challenging environments.