Your behavior appears to be a little unusual. Please verify that you are not a bot.


Innovation: GPS by the Numbers

April 1, 2010  - By

A Sideways Look at How the Global Positioning System Works

In his 200th Innovation column, Contributing Editor Richard Langley takes a look at GPS by the numbers, getting a sense of how GPS works by examining the key numbers that govern its remarkable capabilities, from zero to pi and beyond.

INNOVATION INSIGHTS by Richard Langley

INNOVATION INSIGHTS by Richard Langley

WELCOME TO INNOVATION COLUMN NUMBER 200. I have managed this column continuously since the first issue of GPS World magazine, which appeared back in 1990. From the outset, we established that the column should deal with issues that have broad application and interest and are presented in terms that are accessible to as wide a range of readers as possible. Since 1990, we have covered a wide range of topics, some of them at the leading edge of GPS development and some of them reviewing the basics of GPS operation in tutorial fashion. The column has appeared 199 times and now we come to number 200.

So clearly 200 is an important number for me and, I hope, for you. But the number 200 is interesting for other reasons, too. It is the smallest base 10 unprimeable number — you can’t turn it into a prime number by changing just one of its digits to any other digit. It’s how many dollars you get when you pass Go in Monopoly. And in 2012, it will be how many years have elapsed since The War of 1812 — the last time Canada and the United States had a serious quarrel (other than in hockey). But more to the point of this column, it is the designation of the basic reference document that describes how GPS works: IS-GPS-200. Formerly known as an Interface Control Document or ICD, it has gone through several revisions since its first public release in July 1991. It is full of numbers. Numbers that tell us how the GPS signals are generated and how a receiver is to interpret the signals to provide a position fix.

If you are a regular reader of the Innovation column, then likely you have an inquisitive bent. You like to know how things work — GPS in particular. And you don’t have to be convinced about the importance of numbers and their role in understanding the world around us. As Sir William Thomson, a.k.a. Lord Kelvin, said in one of his lectures,

“I often say that when you can measure what you are speaking about, and express it in numbers, you know something about it; but when you cannot measure it, when you cannot express it in numbers, your knowledge is of a meagre and unsatisfactory kind.”

So in this column, the 200th, we’re going to look at GPS by the numbers, getting a sense of how GPS works by examining some of the key numbers that govern its remarkable capabilities, from the smallest to the largest. I’ll draw heavily on material from the past 199 columns.

Let’s get started.


“Innovation” features discussions about advances in GPS technology, its applications, and the fundamentals of GPS positioning. The column is coordinated by Richard Langley, Department of Geodesy and Geomatics Engineering, University of New Brunswick.


Numbers. We use them for counting and measuring, for labeling and ordering, and for codes and calculations. The number of numbers is infinite. However, there are some special numbers that characterize how GPS works. Some of these are peculiar to GPS; others are more common, finding utility in other global navigation satellite systems or even in our everyday lives. In this article, we’ll take a look at some of these special numbers and their importance to GPS.

We’ll begin with the smallest non-negative number and work our way up to one of the largest GPS-relevant numbers, concluding with an imaginary but very important number.

0

Zero. The smallest cardinal number and the smallest non-negative integer. While zero is a pure real number (a number on an infinitely long number line), it is also a purely imaginary number (see the last entry in this article) because it lies on both the real and imaginary axes on the complex plane. It is used to indicate a null amount. The English mathematician, Alfred North Whitehead, wrote in his 1911 book An Introduction to Mathematics, “The point about zero is that we do not need to use it in the operations of daily life. No one goes out to buy zero fish. It is in a way the most civilized of all the cardinals, and its use is only forced on us by the needs of cultivated modes of thought.” Perhaps it was not needed for daily operations in 1911 but it is indispensible in our modern world. For zero is also one of the two binary digits (the other is one, of course) used in the binary or base-2 number system that is fundamental to how computers, digital electronics, and communications systems operate. For example, we represent the GPS pseudorandom noise (PRN) ranging codes and the navigation message as sequences of zeros and ones and the zeros are just as important as the ones.

The C/A- and P(Y)-codes (see entries 1023 and 235,469,592,765,000), along with the navigation message, are modulated onto the signal carriers using binary phase-shift keying or BPSK. BPSK is a digital modulation scheme that conveys a signal by changing, or modulating, the phase of the carrier wave between two values separated by 180°. The spectrum of a BPSK-modulated signal is a sinc function, with most of the power concentrated around the carrier frequency. An alternative modulation technique is binary offset carrier (BOC) modulation. BOC modulation uses a square-wave subcarrier to offset the spectral power from the carrier frequency and thus allows a BOC-modulated signal to share the same bandwidth as a BPSK signal. The new GPS M-code on L1 and L2 uses a BOC(10.23,5.115) — abbreviated as BOC(10,5) — modulation, which specifies a subcarrier frequency of 1021.023 MHz and a spreading-code chipping rate of 5.115 megachips per second. The spreading code is a pseudorandom bit stream from a signal protection algorithm, having no apparent structure or period. The future L1C signal, the new civil signal to be implemented on L1 by Japan’s Quasi-Zenith Satellite System and the GPS III satellites, will also use BOC modulation. And Europe’s Galileo system, now in development, will also use this modulation technique, which has already been tested in space by the forerunner GIOVE test satellites.

0.00000000000001

(Or 1 x 10-14 in scientific notation). The approximate frequency stability of the rubidium atomic frequency standards in the GPS Block IIR satellites. These devices are used to control the frequency and timing of all aspects of the navigation signals, including the generation of the carrier frequencies and the pseudorandom noise modulation codes. Given their role in controlling the timing of the signals, they are also referred to as clocks.

Each Block IIR satellite contains three rubidium clocks, only one of which is active at any time. The others are spares and the GPS Control Segment carries out a “clock swap” when the performance of an active clock begins to deteriorate, cycling through the remaining units. Many of the Block IIR satellites are still on their first clock.

The Block IIF satellites will also contain three clocks, however, only two will be rubidium clocks. The third clock will be a cesium clock. This mixture of clock types is patterned after the arrangement used on the Bloc
k II and IIA satellites, which used two rubidium clocks and two cesiums.

0.77922077922…

The rational number 60/77. A rational number is any number that can be expressed as a fraction or quotient a/b of two integers, with the denominator b not equal to zero. The decimal expansion of a rational number always either terminates after a finite number of digits or begins to repeat the same sequence of digits over and over again. The digits 077922 of this particular rational number repeat ad infinitum. And why should we be interested in this particular number? It is the ratio of the L2 and L1 carrier frequencies. This number and its inverse ( — the dot above the 3 indicates it repeats indefinitely) are used in various combinations of GPS measurements. For example, if we let η = 60/77, then the ionosphere-free pseudorange combination is

Eq-1
where P1 is a pseudorange measurement on L1 and P2 is the corresponding pseudorange measurement on L2.

1

The loneliest number according to the American rock band Three Dog Night and the Google calculator (try typing “loneliest number” into the Google search engine). It was also the space vehicle number (SVN) of the first Block I GPS satellite, which was launched on February 22, 1978. The satellite did not stay lonely for long. By the end of the year, three more Block I satellites were launched. In total, 10 Block I satellites were successfully orbited between 1978 and 1985 to demonstrate the feasibility of GPS. SVN1 continued in operation until July 17, 1985.

The first satellite of the Block II operational constellation was launched in February 1989. The four-year hiatus in launches was due, in part, to the Space Shuttle Challenger disaster as it had been planned to launch the operational satellites using the Shuttle. Following the accident, it was decided to continue with expendable rockets for GPS launches but to switch to the newly designed Delta II rocket.

The pace of Block II launches was rapid, with five launches of the original Block II design in 1989 and four in 1990. A modified version of the Block II satellite — the IIA — was developed, and between 1990 and 1997 19 Block IIAs were launched. The Block II and IIA satellites established the operational GPS constellation. Full operational capability was declared on April 27, 1995.

A new variant of the Block II satellite was developed for replenishing the constellation as the earlier satellites were retired. Following an initial launch failure, 12 of the Block IIR satellites were launched between 1997 and 2004.

Under the GPS modernization program, the remaining eight Block IIR satellites were modernized with a new navigation payload that included the L2C and M-code signals as well as a new antenna panel (also included on the last four of the classic Block IIRs). The IIR-M satellites were launched between 2005 and 2009, bringing the total number of GPS satellites ever placed in orbit to 58.

One is also the PRN number of SVN49, the Block IIR-M satellite that was modified to transmit the first L5 GPS signals (see 1176.45).

2.4

The approximate delay, in meters, experienced by a GPS signal propagating vertically (from the zenith) through the neutral atmosphere to a receiver at mean sea level. Although the electrically neutral, or unionized, atmosphere extends from ground level up to 50 kilometers and more, the bulk of it is in the lowest most part we call the troposphere. Consequently, the neutral atmosphere delay is often termed the tropospheric delay. The delay varies with actual atmospheric conditions and the elevation angle at which a GPS signal arrives at the receiver’s antenna. If unaccounted for, tropospheric delay would result in position errors of several meters in the horizontal plane and two to three times these values in the vertical. Predictive or “blind” tropospheric models based on climatology attempt to significantly reduce the effect of the troposphere on GPS position fixes.

One such model is UNB3m, developed at the University of New Brunswick. Using a look-up table of surface meteorological parameter values from standard atmospheric models, it can compute the tropospheric delay for a given day of year, latitude, and station height. For example, the UNB3m zenith delay for a sea-level site at a latitude of 60° on day-of-year 201 is 2.435 meters. UNB3m is able to predict zenith delays with an average root-mean-square error of 4.9 centimeters. Better and more consistent performance has been obtained with a wide-area model developed specifically for North America, UNBw.na.

A version of an earlier UNB model became the basis of the RTCA Minimum Operational Performance Standards (MOPS) troposphere model that is included in the firmware of most GPS receivers.

3.1415926…. π

Every nerd’s favorite number. It is the ratio of a circle’s circumference to its diameter in conventional or Euclidean space. We use it, for example, to convert angles measured in radians to degrees (π radians 4 180 degrees). π is an irrational number, which means that its value cannot be expressed exactly as a fraction m/n, where m and n are integers. Consequently, its decimal representation never ends or repeats. But we sometimes use an easily remembered fraction, such as 22/7, to get an approximate value. In this case, 3.14. But, if we compute more digits with this fraction, we get 3.1428571…, clearly an incorrect result. A better way to remember π to eight digits is to count the number of letters in each word of the mnemonic “May I have a large container of coffee?”

In computations related to GPS, how many digits of π should be used? It depends. If you are developing your own algorithms and software for modeling GPS observations or determining precise orbits for the satellites, you’ll likely need π to 16 digits for double-precision floating-point calculations. But it would be a mistake to use π to this precision in computing the position of a satellite from the broadcast ephemeris. The GPS interface specification document, IS-GPS-200, specifies a 14-digit value for π (3.1415926535898) in the satellite coordinate computation. Use fewer or more digits, and the resulting satellite coordinates will not be as accurate.

4

This is the minimum number of satellites that a receiver needs to track and generate a pseudorange measurement to produce a three-dimensional “instantaneous” position fix. The receiver solves a system of four nonlinear equations to obtain the three receiver coordinates and the offset of the receiver’s clock from GPS (System) Time. It is possible to use fewer than four satellites for positioning or navigation, but then additional information must come from elsewhere. For example, if we are navigating and we know our height accurately or can safely assume a value, say, so many meters above the sea surface, then only three pseudoranges would be needed to determine the horizontal coordinates. If the number of satellites drops to two, then another assumption must be made to continue navigation (for example, holding the receiver clock offset constant or assuming a constant driving direction). If the clock offset is held constant, then position accuracy deteriorates quickly since the actual receiver clock offset will diverge from the assumed value. On the other hand, if the direction of travel is held constant, the GPS receiver can at least compute the position along the assumed trajectory. In reality, the vehicle will likely not travel along a perfectly straight path and navigation fails after the first turn.

For single-satellite navigation, three assumptions must be made concerning height, trajectory, and clock offset, but the navigation results are, at best, educated guesses.

If a receiver can acquire and track more than four satellites, it typically uses an optimizing Kalman filter procedure to obtain its position.

10.23

The frequency of a GPS satellite atomic frequency standard in megahertz and the fundamental frequency for signal generation in the satellite. The carrier frequencies and the code chipping rates are harmonically related to this frequency. The P-code chipping rate is identical to the fundamental frequency, while the C/A-code rate is 1/10 of it.

12.5

The length of the full navigation message in minutes. To convert the measured signal delays or pseudoranges between the receiver and the satellites, the receiver must know where the satellites are. To do this in real time requires that the satellites broadcast this information. Accordingly, there is a message superimposed on both the L1 and L2 carriers along with the PRN codes. Each satellite broadcasts its own message, which consists of orbital information (the ephemeris) to be used in the position computation, the offset of its clock from GPS Time, and information on the health of the satellite and the expected accuracy of the range measurements.

The message also contains almanac data for all of the satellites in the GPS constellation, as well as their health status and other information. The almanac data, a crude description of the satellite orbits, is used by the receiver to determine the location of each satellite. The receiver uses this information to quickly acquire the signals from satellites that are above the horizon but are not yet being tracked. So, once one satellite is tracked and its message decoded, acquisition of the signal from other satellites is quite rapid. A receiver will store a copy of the almanac to speed up initial acquisition of satellites when it is switched on.

The GPS navigation message is sent at a relatively slow rate of 50 bits per second, taking 12.5 minutes for all of the information to be transmitted. To minimize the time it takes for a receiver to obtain an initial position, the ephemeris and satellite clock offset data is repeated every 30 seconds.

24

The number of satellites in the current GPS baseline constellation. The GPS constellation went through a number of design alternatives even after the first satellites were launched with different numbers of orbit planes, satellites per plane, and orbit inclinations. The current design has four satellites, irregularly spaced, in six orbit planes. The orbit planes, labeled A through F, are spaced at 60° intervals around the equator with a nominal inclination to the equator of 55°. However, we have typically had a surfeit of satellites with more than 24 in operation since the mid-1990s. In fact, during 2008, as many as 31 satellites were transmitting healthy signals at the same time. However, although a modern GPS receiver should be able to handle a 32-satellite active constellation, there are limits imposed by the GPS Control Segment and some legacy military equipment that currently imposes a 30-satellite active constellation limit.

Although the number of active satellites is well in excess of 24, the constellation has been operated as a 24-satellite constellation without optimizing the orbit locations of the “bonus” satellites. In fact, several pairs of satellites are bunched together minimizing geometrical performance. This is in the process of being changed. The GPS Wing recently announced the transition to a 24+3 or “Expandable 24” baseline constellation. Taking about 24 months to complete, six on-orbit satellites are being rephased within their respective orbit planes to improve the overall geometry of the active constellation so that the number of GPS satellites in view from anywhere on Earth will increase, enhancing the possibility of getting a position fix in partially obscured environments, and potentially improving the accuracy of fixes.

Of course, 24 is also the number of hours in the day during which GPS is available at any point on the Earth’s surface with good sky visibility. It is also the title of a popular American TV series, whose protagonist, Jack Bauer, frequently makes use of imaginary GPS tracking capabilities.

40.3

The scaling factor, which together with the signal frequency and the total electron content, is used to compute the delay experienced by a GPS signal as it propagates through the ionized part of the Earth’s atmosphere. The total electron content is the integrated electron density along the signal’s path. Basically, it is the total number of electrons in a tube with a cross-sectional area of one square meter centered on the signal path. To a very good approximation, the delay, in meters, is computed as

Eq-2

where TEC is the total electron content in so-called TEC units or TECUs (1016 electrons per square meter) and f is the signal carrier frequency in MHz. The scaling factor is a function of the electron’s charge and mass and a constant of electromagnetism theory called the permittivity of free space also known as the electric constant. The scaling factor is actually 40.308193 but this much precision is not generally needed in GPS calculations.hile the code signals are delayed, making pseudoranges longer than they would be in the absence of the ionosphere, the phases of the signal carriers are advanced, make carrier-phase measurements shorter — but by exactly the same magnitude as the code delays.

TEC is highly variable both temporally and spatially. The dominant variability is diurnal following the variation in incident solar radiation. Maximum ionization occurs at approximately 1400 local time. On the ionosphere’s nighttime side, in the absence of solar radiation, free electrons and ions tend to recombine, thereby reducing the TEC. The protonosphere, or uppermost region of the ionosphere, may contribute up to 50 percent of the electron content during the nighttime hours. Typical nighttime values of vertical TEC for mid-latitude sites are of the order of 10 TECU or less with corresponding daytime values of the order of 100 TECU. However, such typical daytime values can be exceeded by a factor of two or more, especially in near-equatorial regions. TEC also varies seasonally with higher values during equinoxes.

1023

This is the number of chips in the C/A-code. The C/A-, or coarse/acquisition-, code is one of the two legacy PRN ranging codes that have been transmitted by all GPS satellites. These PRN codes consist of sequences of binary values (zeros and ones) that, at first sight, appear to have been randomly chosen. But a truly random sequence can only arise from unpredictable causes over which, of course, we would have no control, and which we could not duplicate. However, using a mathematical algorithm or special hardware devices called tapped feedback registers, we can generate sequences that do not repeat until after some chosen interval of time. Such sequences are termed pseudorandom. The apparent randomness of these sequences makes them indistinguishable from certain kinds of noise such as the hiss heard when a conventional AM radio is tuned between stations.

The C/A-code is a sequence of 1,023 binary digits, or chips, which is repeated every millisecond. This means that the chips are generated at a rate of 1,023 million per second and that one chip has a duration of about 1 microsecond.

The C/A-code is generated by two 10-cell feedback registers referred to as G1 and G2. A delayed version of the G2 sequence is obtained by binary adding the contents of a pair of tapped G2 cells and binary adding that result to the output of G1. That becomes the C/A-code. The various alternative pairs of G2 taps (delays) are used to generate the complete set of 36 unique PRN C/A-codes. There are actually 37 PRN C/A-codes, but two of them (34 and 37) are identical. The first 32 codes are assigned to satellites. Codes 33 through 37 are reserved for other uses such as for ground transmitters. This family of codes is a subset known as Gold codes, which have the property that any two have a very low cross correlation (are nearly orthogonal). The term for the codes comes from the inventor, Robert Gold, not from their lustrous properties.

The C/A-code is modulated only onto the L1 carrier, unlike the P(Y)-code (see 235,469,592,765,000) which appears on both L1 and L2. However, beginning with the first Block IIR-M or modernized Block IIR satellite, a new civil code, L2C or L2 Civil, has been transmitted on the L2 frequency. The future Block IIF satellites will also transmit L2C.

1023 is also the maximum value of the GPS week. This is the number of full weeks that have elapsed since the GPS Time zero point of midnight UTC beginning January 6, 1980 — but with a special counting procedure. GPS weeks are numbered consecutively with week zero starting on January 6 and ending on January 12, 1980. The GPS week, together with the Z-count (see 403199), specifies an epoch or event related to GPS signals or measurements. The current GPS week is included in subframe one of the navigation message, which — along with other subframes containing satellite clock, ephemeris data, and other user-required information — is transmitted every 30 seconds. Only 10 bits are used to represent the GPS week, and so the largest possible week number is 1023 (210–1). In other words, the GPS week number is modulo 1024 (see the “Modular Arithmetic” sidebar). At the end of week number 1023, the week number rolls over to zero. This first occurred on August 21/22, 1999, and caused difficulties for some GPS receivers as their manufacturers had failed to account for the “end-of-week rollover” in receiver firmware. The next occurrence will be in April 2019. By that time, the new Civil Navigation (CNAV) message will be in use, in which the GPS week number is represented as a 13-bit value, meaning it rolls over after 8192 weeks, or about every 157 years.

Although officially the GPS week number is still modulo 1024, some agencies, such as the International GNSS Service, prefer to use a running count of the GPS week, ignoring the rollover. The number of the week beginning April 4, 2010, is then alternatively given as 1578 or 554. Or, mathematically speaking (see sidebar), 1578 ≡ 554 (mod 1024).

1176.45

The L5 carrier frequency in megahertz. The L5 carrier frequency is obtained by electronically multiplying the satellite 10.23 MHz standard frequency by 115. It is the lowest and the newest of the GPS frequencies and is used for the new civil-only GPS signal.

The addition of the L5, or Link 5, civil signal to the suite of signals transmitted by the satellites is a key feature of GPS modernization. The introduction of such a signal on a different carrier frequency than that used by the legacy L1 GPS signal was proposed in the 1995 reports by the U.S. National Research Council and the National Academy of Public Administration on the future of GPS. The reports argued that an unencrypted signal on a second frequency would offer civil users the benefit of ionospheric delay correction, wide-lane carrier-phase ambiguity resolution, improved interference rejection, and faster accuracy recovery in multipath environments. The frequency is in a protected aeronautical radionavigtion services band and, unlike L2, means that L5 can be used for safety-of-life services. The L5 signal will be standard on all Block IIF and future satellites. An L5 demonstration payload was included on Block IIR-M satellite SVN49 to secure the L5 frequency under the rules of the International Telecommunication Union.

1227.60

The L2 carrier frequency in megahertz. The L2, or Link 2, carrier is modulated with the P(Y)-code. Additionally, starting with the Block IIR-M satellites, a new civil ranging code, L2C, is being transmitted on L2 along with the new military M-code. These new signals are also part of the GPS modernization effort. The L2 carrier frequency is obtained by electronically multiplying the satellite 10.23 MHz standard frequency by 120.

1381.05

The L3 carrier frequency in megahertz. This frequency is used in conjunction with the GPS satellites’ secondary purpose, which is to detect nuclear detonations. The L3 carrier frequency is obtained by electronically multiplying the satellite 10.23 MHz standard frequency by 135.

1575.42

The L1 carrier frequency in megahertz. The L1, or Link 1, carrier is modulated with the C/A-code and the P(Y)-code. Starting with the Block IIR-M satellites, the new military M-code is also transmitted on L1. The L1 carrier frequency is obtained by electronically multiplying the satellite 10.23 MHz standard frequency by 154. If you’ve been counting, you’ll have noticed that we didn’t list an L4 frequency. L4 has never been implemented but it has been studied. For example, a frequency of 1841.40 MHz (10.23×180) was once considered for ionospheric correction.

403199

The maximum value of the GPS time of week count. The GPS satellites count and communicate GPS Time in a unique manner that is ultimately related to how they generate the PRN ranging codes. As described below, the P-code is generated by combining two shorter PRN codes, X1 and X2, which are clocked in phase at a chipping rate equal to the satellite’s 10.23-MHz oscillator frequency. X1 has a repetition interval, or period, of 1.5 seconds — a fundamental GPS timing unit. The start of each 1.5-second interval identifies an epoch. The number of X1 epochs since the beginning of the week is called the time of week (TOW) count, which runs from zero to 403,199 at the end of week. The TOW count returns to zero coincident with the resetting of the PRN codes.

The TOW count can be represented as a 19-bit binary number, a truncated version (the 17 most significant bits) of which is part of the handover word (HOW) that a satellite transmits every six seconds. The HOW appears as the second word in each data subframe of the navigation message. These 17 bits correspond to the TOW count at the X1 epoch that occurs at the start of the immediately following subframe, and so effectively preannounces the arrival of a time marker, just like telephone “speaking clocks” and shortwave radio time and frequency stations.

The TOW count by itself cannot be used to unambiguously establish the date of an event. It can only time an event at modulo 604,800 seconds [(403199+1)x1.5] because it is reset every week. This time ambiguity is reduced by noting the number of full weeks that have elapsed since January 6, 1980 modulo 1024 — the GPS week number (see 1023). The TOW count and the GPS week number combine to form the 29-bit Z count. The 19 least-significant bits are the TOW count and the 10 most-significant bits are the GPS week number.

299,792,458

The speed of light in meters per second. This is the speed with which all electromagnetic radiation propagates in a vacuum. Until 1983, the speed of light was measured experimentally using adopted standards for the length of the second and the length of the meter. However, compared to the second, the definition of the meter had a large uncertainty. So in 1983, the 17th General Assembly of Weights and Measures defined the meter as the distance travelled by light in a vacuum during 1/299,792,458 of a second, fixing the speed of light at 299,792,458 meters per second — exactly. This constant is used by a GPS receiver, for example, to convert the measured signal propagation time in seconds to a pseudorange in meters.

235,469,592,765,000

(Or 2.35469592765000 x 1014 in scientific notation). This is the number of chips in the P-code if it were allowed to continue without being reset. The P-, or precision code, is one of the two legacy PRN ranging codes that have been transmitted by all GPS satellites. The other is the C/A-code, already discussed.

The P-code is actually the product of two PRN codes, each of which is generated with a pair of feedback registers. The X1 code has a length of 15,345,000 chips while the X2 code has a length of 15,345,037 or 37 chips longer. So the complete P-code has a length equal to the product of the lengths of the X1 and X2 codes, or 235,469,592,765,000. The codes are clocked at a rate of 10.23 MHz so that each chip has a length of about 0.097752 microseconds. This means the pattern of chips in the full P-code would not repeat for almost 266 days. Each satellite is assigned a unique one-week segment of the P-code, which is reset at Saturday/Sunday midnight each week. The individual P-codes have low cross-correlations with each other. In other words, no significant segments of the P-code of one satellite matches that of another.

Before transmission, a P-code chip sequence is encrypted to form a new sequence called the Y-code. The combined sequence is usually referred to as P(Y). Although civil GPS receivers cannot use conventional correlation procedures to acquire and track the P(Y) code, they can use knowledge of the underlying P-code sequence and C/A-code tracking on L1 to produce pseudorange and carrier-phase measurements on both the L1 and L2 frequencies.

√-1

The square root of -1. This is the unit of imaginary numbers. The concept of imaginary numbers, actually known to the ancient Greeks, was introduced in the effort to solve algebraic equations. Not all equations can be solved using real numbers. In particular, x2=-1 has no real-valued solution. But we can say some solution exists and represent it by the symbol i. (Mathematicians and physicists use this symbol whereas electrical engineers prefer j, since i usually describes a varying electrical current.) Then i has the property — by definition — that its square is -1. Of course, that equation would also permit the solution -i. An imaginary number — sometimes called pure imaginary — is any number of the form bi, where b is a non-zero, real number. A real number, a, and an imaginary number, bi, can be combined into a complex number, a+bi, or a+ib, the more usual notation. Using complex numbers and a set of rules governing their manipulations, any algebraic equation can be solved.

It is useful to consider the real and imaginary parts of a complex number to be orthogonal so that we can represent a complex number geometrically on a plane — the complex plane — where the real component is plotted on the x-axis and the imaginary component on the y-axis. We can then represent a 2-dimensional vector as a complex number, with one component considered real and the other imaginary. The magnitude or modulus of the vector, r, is the positive square root of the sum of the squares of the real and imaginary components with the vector making an angle, Φ , with respect to the positive real axis.

It can be easily shown that

Eq-3

This is Euler’s famous formula, which provides an enlightening connection between plane geometry and algebra.
And, we may also write any complex number in the form

Eq-4 or even more compactly as  Eq-5

If the vector rotates counterclockwise with angular speed ω, its projection onto the real axis generates a sine wave. The modulus of this vector is the amplitude of the oscillations, while its argument is the total phase,

Eq-6

where t is time. The phase constant θ represents the angle that the vector forms with the real axis at t=0. This representation of a sine wave as a phase vector, or phasor, finds great utility in signal theory including descriptions of the propagation of radio waves such as those emitted by GPS satellites.


Modular Arithmetic

GPS Time, like all time systems, is based on modular arithmetic. This arithmetic is a little different from conventional arithmetic in that numbers, typically restricted to integers, have a finite maximum value. Adding one to that number doesn’t get you a larger number — it gets you a smaller one, a much smaller one: zero.

Modular arithmetic is known to us all as clock arithmetic. Take the 24-hour time system as an example. If it’s currently 1800, then 8 hours later we say it’s 0200, not 2600. Similarly, if it’s currently 0400, then 6 hours earlier it was not -0200 but 2200. The idea here is that if two numbers differ by 24 or a multiple of 24, then they are “equal.” We could simply write 26 = 2 but this could be confusing. So we write 26 ≡ 2 (mod 24), and -2 ≡ 22 (mod 24), or in words, 26 is congruent (or somehow “equal”) to 2 (modulo 24) and -2 is congruent to 22 (modulo 24). In arithmetic modulo 24, any number larger than 24 is congruent to some number less than 24 because we can always subtract a multiple of 24 from the larger number to get the smaller one. Similarly, any negative number is congruent to some positive number less than 24, and 24 is congruent to 0. This means that in arithmetic modulo 24, we need deal only with integers from 0 to 23.

We can choose any positive integer for the modulus and carry out arithmetic operations accordingly. Using a modulus of 4, for example, we would have 2+2=0 in our loose notation — a disturbing result if interpreted as conventional arithmetic. But when written 2+2 ≡ 0 (mod 4), the meaning is clear.

As another example of modular arithmetic, consider this question: If today is Monday, what day of the week is it 185 days from now? The modulus here of course is 7, the number of days in the week. So, mathematically stated: 1+185 ≡ ? (mod 7). The answer: 4 or Thursday. The answer is obtained by dividing the sum on the left side of the congruency by 7, using “long division,” and noting the remainder. Or, alternatively, the sum is divided by 7, and the decimal part of the result is then multiplied by 7.

An interesting quirk of modular arithmetic is that a number and the sum of its digits are congruent, modulo 9. This property is the basis for a formerly well-known procedure (before the days of calculators and computers) for checking the correctness of hand multiplication — the rule for casting out nines, which states that the product of two numbers and the product of the sums of their digits must have the same remainder on division by 9.

Many computer languages have a built-in modular arithmetic function or operator. Typically called MOD, it returns the remainder from an integer division operation. In BASIC, for example, if we enter 5 MOD 2, we get 1 because 5 divided by 2 is 2 with a remainder of 1. The same computation is coded 5 2 MOD in Forth, 5 % 2 in Python, and MOD (5,2) in FORTRAN.

The following line of FORTRAN code by Henry Fliegel of The Aerospace Corporation inherently uses modular arithmetic by way of integer division to determine the Julian day (JD) number from the year, month, and day of an AD Gregorian calendar date, incorporating all leap year rules:

JD=367*Y-7*(Y+(M+9)/12)/4-3*((Y+(M-9)/7)/100+1)/4+275*M/9+D+1721029

And just how can the GPS end-of-week rollover be described using modular arithmetic? Very simply: 1023+1 ≡ 0 (mod 1024).


FURTHER READING

• GPS Interface Control Documents

Navstar GPS Space Segment / Navigation User Interfaces, Interface Specification, IS-GPS-200 Revision D (IRN-200D-001), prepared by ARINC Engineering Services LLC, El Segundo, California, March 2006.

Navstar GPS Space Segment / User Segment L5 Interfaces, Interface Specification,
IS-GPS-705 Revision IRN-705-003, prepared by ARINC Engineering Services LLC, El Segundo, California, 22 September 2005.

Navstar GPS Space Segment / User Segment L1C Interfaces, Interface Specification,
IS-GPS-800,
prepared by Science Applications International Corporation, El Segundo, California, 4 September 2008.

• Imaginary Numbers

An Imaginary Tale: The Story of √-1 by Paul J. Nahin, Princeton University Press, Princeton, New Jersey, paperback edition, 2007.

• Innovation Column 1

“GPS: A Multipurpose System” by D. Wells and A. Kleusberg in GPS World, Vol. 1, No. 1, January/February 1990, pp. 60–63. (Scanned versions of the first 15 Innovation columns are available.)

• Innovation Column 100

“Smaller and Smaller: The Evolution of the GPS Receiver” by R.B. Langley in GPS World, Vol. 11, No. 4, April 2000, pp. 54–58.

• Some Other Numerically Relevant Innovation Columns

“Why is the GPS Signal so Complex?” by R.B. Langley in GPS World, Vol. 1, No. 3, May/June 1990, pp. 56–59.

“The Orbits of GPS Satellites” by R.B. Langley, in GPS World, Vol. 2, No. 3, March 1991, pp. 50–53.

“Time, Clocks, and GPS” by R.B. Langley in GPS World, Vol. 2, No. 10, November/December 1991, pp. 38–42.

“Detecting Nuclear Detonations with GPS” by P. Highie and N. K. Blocker in GPS World, Vol. 5, No. 2, February 1994, pp. 48–50.

“The Promise of a Third Frequency” by R.R. Hatch in GPS World, Vol. 7, No. 5, May 1996, pp. 55–58.

“The GPS End-of-Week Rollover” by R.B. Langley in GPS World, Vol. 9, No. 11, November 1998, pp. 40–47.

“Tropospheric Delay: Prediction for the WAAS User” by P. Collins and R.B. Langley in GPS World, Vol. 10, No. 7, July 1999, pp. 52–58.

“GPS, the Ionosphere, and the Solar Maximum” by R.B. Langley in GPS World, Vol. 11, No. 7, July 2000, pp. 44–49.

“The New L5 Civil GPS Signal” by A.J. Van Dierendonck and C. Hegarty in GPS World, Vol. 11, No. 9, September 2000, pp. 64–71.

“Time for a Better Receiver: Chip-Scale Atomic Frequency References” by J. Kitching in GPS World, Vol. 18, No. 11, November 2007, pp. 52–57.

The GPS L2C Signal: A Preliminary Analysis of Data Quality” by R.F. Leandro, R.B. Langley, L. Sükeová, T. Thirumurthi, and M.C. Santos in GPS World, Vol. 19, No. 10, October 2008, pp. 42–47.

GPS L5 First Light: A Preliminary Analysis of SVN49’s Demonstration Signal” by M. Meurer, S. Erker, S. Thölert, O. Montenbruck, A. Hauschild, and R.B. Langley in GPS World, Vol. 20, No. 6, June 2009, pp. 49–58.

This is posted in Innovation, OEM