The Navstar Global Positioning System:
Computing a Location using Numerical Methods
Robert Hunkins
CENG 5131 Engineering Applications
Fall 2005 Research Project
Dr. D. Leleux
Abstract
The Navstar Global Positioning System (GPS) is a space based radionavigation system consisting of a constellation of Earth orbiting satellites, ground stations that control the satellites, and users equipped with receivers. This paper provides an overview of the GPS segments and discusses the basic mathematics used in the operation of the Navstar GPS.
Introduction
“Where am I?”. “Which way do I go?”. “When will I get there?”. These are questions that have been asked by humans since the beginning. In response, scientists and engineers have created tools to help answer these questions. Some of these tools are the map, the compass, the sextant, the chronometer, the radio, and the computer. Each of these inventions has revolutionized navigation. Most recently, the crowning achievement in navigation has been the development of the Global Positioning System (GPS). For the user of a small electronic device, the GPS provides the location, velocity, and the to a level of precision accuracy previously unseen.
GPS Overview
The Navstar Global Positioning System was developed and is operated by the United States Department of Defense. While originally intended as a system for use in military operations, civilians also use the GPS in many different applications at no cost other than that of a receiver.
The GPS consists of three major pieces or segments. These are: the Space Segment, Control Segment and the User Segment.[1]
Space Segment
The Space Segment consists of at least 21 operational Navstar Satellites. These satellites are positioned in 10,900 nautical mile high circular orbits, inclined at 55 degrees to the equator, in six separate orbital planes. The satellites orbit the Earth in a 12-hour period[2].(Refer to Figure 1). The large number of satellites is required to provide continuous global coverage.
Precise timing is extremely important for correct navigation. To accomplish this, each satellite is equipped with four atomic clocks (two Rubidium, two Cesium). On board computers compute the position and velocity of the satellite.
The satellites transmit precisely timed binary pulse signals to the Earth for reception by the user segment. The position, velocity, and time data is encoded in the binary signal and provides the exact location of the satellite in space and time for processing by the user segment.
Figure 1 -Navstar Satellite constellation[3]
Control Segment
Because the satellites tend to drift in space, and small deviations in the timing of the atomic clocks can significantly affect navigation solutions, it is necessary to update the satellite computers occasionally so that the transmitted positions of the satellites are correct and the satellite clocks are synchronized. The Control Segment is therefore necessary to maintain accuracy. The Control Segment consists of a group of monitor stations and control centers located around the Earth. The control segment tracks the satellites from Earth and uplinks timing and position corrections. The control segment also sends commands to the satellites to alter orbits and maintain operational status. The Primary Control Center is located at Falcon Air Force Base in Colorado.
User segment
The User Segment consists of many receivers, produced under contract for the military and government use, or commercially for civilian use. Receivers produced for the Military and Government have additional capabilities not available in commercial units as will be discussed later. A typical handheld commercial GPS receiver is shown in Figure 2.
Receivers may be stand-alone units, or they may be embedded in a vehicle, to provide navigational capabilities to the pilot. The design of the receiver can vary with the intended application. Such applications are for land, sea, and air navigation, surveying, recreation, search and rescue, and vehicle tracking.
Figure 2 - A Hand Held GPS Receiver
GPS Operation
Satellite Signal Transmission
The satellites transmit signals on two frequencies, known as Link 1 (L1) at 1575.42 MHz and Link 2 (L2) at 1227.6 MHz. The signal transmitted on L1 is the 1.023MHz Course/Acquisition code (C/A-code). The C/A signal consists of a 1023 bit signal that repeats approximately 1 time every thousandth of a second[4]. The other signal is the 10.23 MHz Precision code, (P-code), which is transmitted on both L1 and L2. The bit patterns are Phase Shift Key(PSK) encoded on the carrier wave.
Satellite Navigation Services
The C/A signal constitutes the Standard Positioning Service (SPS). The P(Y) code is the Precise Positioning Service(PPS). The P code is usually encrypted so that only authorized users, such as the U.S. military, NATO, and other national government agencies holding with agreements with the United States may use it. When encrypted, the P code is called the Y-code. The P(Y) code repetition interval is approximately 6x1012 bits, and takes approximately seven days to repeat[5]. The C/A code is unencrypted and so may be used by all receivers.
Superimposed on both the C/A and P(Y) codes is a 50 Hz navigation message that provides the satellite position, signal transmission time, the constellation almanac, and atmospheric correction factors[6]. The receiver uses this data to determine position, velocity and time. PPS receivers first decode the data on the C/A code, and from a handover word on that signal, can then lock onto the P(Y) code and make use of the PPS. PPS receivers must have a decryption key loaded in the receiver to use PPS. If the key is invalid, the receiver will operate using SPS.
o Position and Velocity Determination
The C/A and P(Y) signals from each satellite is generated using a unique Pseudo Random Number (PRN) code, allowing the receiver to distinguish between the satellites transmitting on the same frequency. The receiver generates a PRN code identical to that of a satellite and then synchronizes its PRN code to one that it has received. The receiver is then said to have code lock on that satellite and can decode the data being received in that signal. The receiver determines from the signal the time taken by the signal to reach the receiver using the equation:
Equation 1
Rn is the ‘Pseudorange’ to satellite n, c is the speed of light (3x108m/s) and tr-tt is the time difference between transmission and reception of the signal. The time of transmission is part of the data set encoded in the signal from the satellite.
Rn is called a Pseudorange or “false range“ because the distance measured is only an estimate, as will be explained shortly. Also encoded in the data is the position of the satellite. (Xn,Yn,Zn).
The receiver also obtains similar data from at least three other satellites in view.
From these pseudoranges, time and position data, the following system of four equations and four unknowns can be solved. Note the four equations are those of four spheres. The solution to this system of equations is a point that is the receiver position (Ux,Uy,Uz) in space:
Note the fourth unknown, CB. This is the clock bias of the receiver. This is the uncertainty in the pseudorange to the satellite due to timing differences between the satellites and the receiver. If the receiver clock were perfectly synchronized with the satellite clocks (CB=0), the receiver would only need signals from three satellites to determine the position. However, this would require that a very accurate atomic clock be built into the receiver. A more robust and far more inexpensive solution is to process a fourth satellite signal and synchronize the receiver clock with the satellite clocks using the clock bias value. The receiver clocks can be built using inexpensive and relatively sturdy crystal oscillators. Because CB is a distance, CB is divided by c, the speed of light to obtain the clock error, and applied to the receiver time for correction.
While the system of equations can be solved analytically[8], A receiver will solve these equations numerically. Receivers will process signals from more than the minimum number of satellites necessary to produce an over determined solution, and it will use repeated measurements to obtain an optimized solution.[9]
Receiver velocity is also determined from the signals
received from the satellites. The satellites are in constant motion, making it
possible to measure a Doppler shift in the signal. Measuring the Doppler shift
from these four satellites will allow the receiver to determine its motion
relative to the satellites
, as well as the receiver clock frequency bias 
. A system of equations similar to Equation 2 can be solved to determine these parameters.
One way to numerically solve the GPS equations is to use Newton’s method:
Equation 3
where un is an initial guess for the user
position. f(u) is the system of navigation equations given above.
To find the inverse of f’(u), a Jacobian matrix can be used: [10]
Equation 4
By evaluating the Jacobian at the guess taken, a new estimate of the user position and time correction can be generated. The position, velocity, and time of the receiver can then be determined by iteration.
Another method to compute the navigation solution is to use a Least-Squares method. To do this, it is necessary to linearize the navigation equations by subtracting them from one another. This is accomplished as shown below, using pseudoranges from five satellites. This concept can be extended to more satellites however; most modern GPS receivers do not process more than a maximum of 12 satellite signals at a time.
Equations 5
Re arranging the equations in the matrix form Au=b gives:
Equations 6
Solving for the u vector is done by rearranging the equation as follows:
Equation 7
Many GPS systems are used in dynamic situations, where the parameters being used for computation are quickly changing. This would produce a noisy navigation solution. To compensate for this, the navigation solution is processed by a Kalman filter. Kalman filtering is a mathematical technique for combining and smoothing a sequence of navigation solutions and to obtain the best real-time estimate of the current position. Depending on the application, the Kalman filter may only process the three position variables, and the clock bias, or it may process the velocities, and clock bias change as well. For very dynamic applications, the filter may be input with the accelerations of the receiver.[11] Other factors must also be taken into account to realize a high level of accuracy. For example, tropospheric and ionospheric effects change the rate of propagation of the signals, Relativistic effects also contribute to some error in the signals, and satellite clock offsets must be considered when determining a navigation solution. In PPS receivers, differences between the L1 and L2 signals can be used to reduce these errors. In SPS receivers, corrections are provided in the satellite data to estimate these effects.
The angles between the satellites also can produce error. If most of the satellites used in the navigation solution lie in the same orbital plane, or are widely spaced apart, the precision of the navigation solution is reduced. Algorithms in the receivers are used to select the best-positioned satellites for the navigation solution.
Conclusion
The GPS has revolutionized navigation. What was once a tedious mathematical exercise is now as simple as using a radio receiver. The overall concept is amazingly simple, yet the required technology has only become available and affordable in the last decade. Applications of this system will no doubt continue to be incorporated into new and exciting inventions.