Seven technologies that put GPS in mobile phones around the world — the how and why of location’s entry into modern consumer mobile communications. By Frank van Diggelen, Broadcom Corporation Exactly a decade has passed since the first major milestone of the GPS-mobile phone success story, the E-911 legislation enacted in 1999. Ensuing developments in that history include: Snaptrack bought by Qualcomm in 2000 for $1 billion, and many other A-GPS startups are spawned. Commercial GPS receiver sensitivity increases roughly 30 times, to 2150 dBm (1998), then another 10 times, to 2160 dBm in 2006, and perhaps another three times to date, for a total of almost 1,000 times extra sensitivity. We thought the main benefit of this would be indoor GPS, but perhaps even more importantly it has meant very, very cheap antennas in mobile phones. Meanwhile: Host-based GPS became the norm, radically simplifying the GPS chip, so that, with the cheap antenna, the total bill of materials (BOM) cost for adding GPS to a phone is now just a few dollars! Thus we see GPS penetration increasing in all mobile phones and, in particular, going towards 100 percent in smartphones. This article covers the technology revolution behind GPS in mobile phones; but first, let’s take a brief look at the market growth. This montage gives a snapshot of 28 of the 228 distinct Global System for Mobile Communications (GSM) smartphone models (as of this writing) that carry GPS.   Back in 1999, there were no smartphones with GPS; five years later still fewer than 10 different models; and in the last few years that number has grown above 200. This is that rare thing, often predicted and promised, seldom seen: the hockey stick! The catalyst was E-911 — abetted by seven different technology enablers, as well as the dominant spin-off technology (long-term orbits) that has taken this revolution beyond the cell phone. In 1999, the Federal Communications Commission (FCC) adopted the E-911 rules that were also legislated by the U.S. Congress. Remember, however, that E-911 wasn’t all about GPS at first. It was initially assumed that most of the location function would be network-based. Then, in September 1999, the FCC modified the rules for handset technologies. Even then, assisted GPS (A-GPS) was only adopted in the mobile networks synchronized to GPS time, namely code-division multiple access (CDMA) and integrated digital enhanced network (iDEN, a variant of time-division multiple access). The largest networks in the world, GSM and now 3G, are not synchronized to GPS time, and, at first, this meant that other technologies (such as enhanced observed time difference, now extinct) would be the E-911 winners. As we all now know, GPS and GNSS are the big winners for handset location. E-911 became the major driver for GPS in the United States, and indirectly throughout the world, but only after GPS technology evolved far enough, thanks to the seven technologies I will now discuss. Technology #1. Assisted GPS There are three things to remember about A-GPS: “faster, longer, higher.” The Olympic motto is “faster, stronger, higher,” so just think of that, but remember “faster, longer, higher.” The most obvious feature of A-GPS is that it replaces the orbit data transmitted by the satellite. A cell tower can transmit the same (or equivalent) data, and so the A-GPS receiver operates — faster. The receiver has to search over a two-dimensional code/frequency space to find each GPS satellite signal in the first place. Assistance data reduces this search space, allowing the receiver to spend longer doing signal integration, and this in turn means higher sensitivity (Figure 1). Longer, higher. FIGURE 1. A-GPS: reduced search space allows longer integration for higher sensitivity. Now let’s look at this code/frequency search in more detail, and introduce the concepts of fine time, coarse time, and massive parallel correlation. Any assistance data helps reduce the frequency search. The frequency search is just as you might scan the dial on a car radio looking for a radio station — but the different GPS frequencies are affected by the satellite motion, their Doppler effect. If you know in advance whether the satellite is rising or setting, then you can narrow the frequency-search window. The code-delay is more subtle. The entire C/A code repeats every millisecond. So narrowing the code-delay search space requires knowledge of GPS time to better than one millisecond, before you have acquired the signal. We call this “fine-time.” Only two phone systems had this time accuracy: CDMA and iDEN, both synchronized to GPS time. The largest networks (GSM, and now 3G) are not synchronized to GPS time. They are within 62 seconds of GPS time; we call this “coarse-time.” Initially, only the two fine-time systems adopted A-GPS. Then came massive parallel correlation, technology number two, and high sensitivity, technology number three. #2, #3. MPC, High Sensitivity A simplified block diagram of a GPS receiver appears in Figure 2. Traditional GPS (prior to 1999) had just two or three correlators per channel. They would search the code-delay space until they found the signal, and then track the signal by keeping one correlator slightly ahead (early) and one slightly behind (late) the correlation peak. These are the so-called “early-late”correlators.   FIGURE 2. Massive parallel correllation. Massive parallel correlation is defined as enough correlators to search all C/A code delays simultaneously on multiple channels. In hardware, this means tens of thousands of correlators. The effect of massive parallel correlation is that all code-delays are searched in parallel, so the receiver can spend longer integrating the signal whether or not fine-time is available. So now we can be faster, longer, higher, regardless of the phone system on which we implement A-GPS. Major milestones of massive parallel correlation (MPC): In 1999, MPC was done in software, the most prominent example being by Snaptrack, who did this with a fast Fourier transform (FFT) running on a digital signal processor (DSP). The first chip with MPC in hardware was the GL16000, produced by Global Locate, then a small startup (now owned by Broadcom). In 2005, the first smartphone implementation of MPC: the HP iPaq used the GL20000 GPS chip. Today MPC is standard on GPS chips found in mobile phones. #4. Coarse-Time Navigation We have seen that A-GPS assistance relieves the receiver from decoding orbit data (making it faster), and MPC means it can operate with coarse-time (longer, higher). But the time-of-week (TOW) still needed to be decoded for the position computation and navigation: for unambiguous pseudoranges, and to know the time of transmission. Coarse-time navigation is a technique for solving for TOW, instead of decoding it. A key part of the technique involves adding an extra state to the standard navigation equation, and a corresponding extra column to the well known line-of-sight matrix. The technical consequence of this technique is that you can get a position faster than it is possible to decode TOW (for example, in one, two, or three seconds), or you can get a position when the signals are too weak to decode TOW. And a practical consequence is longer battery life: since you can get fast time-to-first-fix (TTFF) always, without frequently waking and running the receiver to maintain it in a hot-start state. #5. Low Time-of-Week A parallel effort to coarse-time navigation is low TOW decode, that is, lowering the threshold at which it is possible to decode the TOW data. In 1999, it was widely accepted that -142 dBm was the lower limit of signal strength at which you could decode TOW. This is because -142 dBm is where the energy in a single data bit is just observable if all you do is integrate for 20 ms. However, there have evolved better and better ways of decoding the TOW message, so that now it can be done down to -152 dBm. Today, different manufacturers will quote you different levels for achievable TOW decode, anywhere from -142 to -152 dBm, depending on who you talk to. But they will all tell you that they are at the theoretical minimum! #6, #7. Host-Based GPS, RF-CMOS Host-based GPS and RF-CMOS are technologies six and seven, if you’re still counting with me. We can understand the host-based architecture best by starting with traditional system-on-chip (SOC) architecture. An SOC GPS may come in a single package, but inside that package you would find three separate die, three separate silicon chips packaged together: A baseband die, including the central processing unit (CPU); a separate radio frequency tuner; and flash memory. The only cost-effective way of avoiding the flash memory is to have read-only memory (ROM), which could be part of the baseband die — but that means you cannot update the receiver software and keep up with the technological developments we’ve been talking about. Hence state-of-the-art SOCs throughout the last decade, and to date, looked like Figure 3. FIGURE 3. Host-based architecture, compared to SOC. The host-based architecture, by contrast, needs no CPU in the GPS. Instead, GPS software runs on the CPU and flash memory already present on the host device (for example, the smartphone). Meanwhile, radio-frequency complementary metal-oxide semi-conductor (RF-CMOS) technology allowed the RF tuner to be implemented on the same die as the baseband. Host-based GPS and RF- CMOS together allowed us to make single die GPS chips. The effect of this was that the cost of the chip went down dramatically without any loss in performance. Figure 4 shows the relative scales of some of largest-selling SOC and host- based chips, to give a comparative idea of silicon size (and cost). The SOC chip (on the left) is typically found in devices that need a CPU, while the host-based chip is found in devices that already have a CPU.   FIGURE 4. Relative sizes of host-based, compared to SOC. In 2005, the world’s first single-die GPS receiver appeared. Thanks to the single die, it had a very low bill of materials (BOM) cost, and has sold more than 50 million into major-brand smartphones and feature phones on the market. Review We have seen that E-911 was the big catalyst for getting GPS into phones, although initially only in CDMA and iDEN phones. E-911 became the driver for all phones once GPS evolved far enough, thanks to the seven technology enablers: A-GPS >> faster, longer, higher Massive parallel correlation >> longer, higher with coarse-time High-sensitivity >> cheap antennas Coarse time navigation >> fast TTFF without periodic wakeup Low TOW >> decode from weak signals Host-based GPS, together with RF-CMOS g single die. Meanwhile, as all this developed, several important spin-off technologies evolved to take this technology beyond the mobile phone. The most significant of all of these was long-term orbits (LTO), conceived on May 2, 2000, and now an industry standard. Long-Term Orbits Why May 2, 2000? Remember what happened on May 1, 2000: the U.S. government turned off selective availability (SA) on all GPS satellites. Suddenly it became much easier to predict future satellite orbits (and clocks) from the observations made by a civilian GPS network. At Global Locate, we had just such a network for doing A-GPS, as illustrated in Figure 5. On May 2 we said, “SA is off — wow! What does that mean for us?”And that’s where LTO for A-GPS came from. FIGURE 5. Broadcast ephemeris and long-term orbits. Figure 5 shows the A-GPS environment with and without LTO. The left half shows the situation with broadcast ephemeris only. An A-GPS reference station observes the broadcast ephemeris and provides it (or derived data) to the mobile A-GPS receiver in your mobile phone. The satellite has the orbits for many hours into the future; the problem is that you can’t get them. The blue and yellow blocks in the diagram represent how the ephemeris is stored and transmitted by the GPS satellite. The current ephemeris (yellow) is transmitted; the future ephemeris (blue) is stored in the satellite memory until it becomes current. So, frustratingly, even though the future ephemeris exists, you cannot ordinarily get it from the GPS system itself. The right half of the figure shows the situation with LTO. If a network of reference stations observes all the satellites all the time, then a server can compute the future orbits, and provide future ephemeris to any A-GPS receiver. Using the same color scheme as before, we show here that there are no unavailable future orbits; as soon as they are computed, they can be provided. And if the mobile device has a fast-enough CPU, it can compute future orbits itself, at least for the subset of satellites it has tracked. Beyond Phones. This idea of LTO has moved A-GPS from the mobile phone into almost any GPS device. Two of most interesting examples are personal navigation devices (PNDs) in cars, and smartphones themselves that continue to be useful gadgets once they roam away from the network. Now, of course, people were predicting orbits before 2000 — all the way back to Newton and Kepler, in fact. It’s just that in the year 2000, accurate future GPS orbits weren’t available to mobile receivers. At that time, the International GNSS Service (IGS) had, as it does now, a global network of reference stations, and provided precise GPS orbits organized into groups called Final, Rapid and Ultra-Rapid. The Ultra-Rapid orbit had the least latency of the three, but, in 2000, Ultra-Rapid meant the recent past, not the future. So for LTO we see that the last 10 years have taken us from a situation of nothing available to the mobile device, to today where these long-term orbits have become codified in the 3rd Generation Partnership Project (3GPP) and Secure User Plane Location (SUPL) wireless standards, where they are known as “ephemeris extension.” Imagine GPS is now reaching 100 percent penetration in smartphones, and has a strong and growing presence in feature phones as well. GPS is now in more than 300 million mobile phones, at the very least; credible estimates range above 500 million. Now, imagine every receiver ever made since GPS was created 30 years ago: military and civilian, smart-bomb, boat, plane, hiking, survey, precision farming, GIS, Bluetooth-puck, personal digital assistant, and PND. In the last three years, we have put more GPS chips into mobile phones than the cumulative number of all other GPS receivers that have been built, ever! Frank van Diggelen has worked on GPS, GLONASS, and A-GPS for Navsys, Ashtech, Magellan, Global Locate, and now as a senior technical director and chief navigation officer of Broadcom Corporation. He has a Ph.D. in electrical engineering from Cambridge University, holds more than 45 issued U.S. patents on A-GPS, and is the author of the textbook A-GPS: Assisted GPS, GNSS, and SBAS.