How does GPS work? July 6, 2011

Image via Wikipedia

How GPS works

Well, dear reader, here we both are again: time for another Hub Tech Insider primer on one of the most fundamental technologies driving today’s revolutions in mobile commerce, location-based services and applications, smartphone features, and so much more.

You know that I’m talking about GPS, the Global Positioning System.

You also realize, if you have been to this blog before, that you are about to get a complete rundown on the nuts-and-bolts of GPS technology from its nascent conceptual underpinnings through today’s location-aware mobile applications.

But first, a history lesson (you should have been expecting that too from me, Dear Reader):

The challenge of navigation: a brief history

The magnetic compass arrived in Western Europe from China sometime in the 12th century. The compass was a seminal invention in the history of navigation, providing orientation – however most travelers still depended on familiarity with the region through which they were traveling, using sight navigation perhaps supplemented with some rudimentary observation of the stars.

The magentic compass of course could not determine a person’s position. The use of the stars was the primary method used to determine position. Devices such as the astrolabe, the quadrant and the sextant provided navigators with important new sources of navigational and positioning data, and they opened up new territories to exploration, as they enabled the traveler to easily determine latitude, which is the distance above or below the Earth’s equator.

Being an experienced sailor, and also as a result of my time involved in a naval military career, I have received training with the above three navigation instruments. Using a sextant to navigate can be fun, but the learning curve can be quite steep, particularly for beginners. And there is also a major problem with using these instruments to determine a precise location: when navigating using the stars as a visual point of reference, there is no way to determine your longitude, which is the distance east or west around the globe.

Accurate latitude without accurate longitude position information led to many great naval disasters – the navigators of wooden sailing ships on the high seas, and their Captains, did not accurately know their own position. Easy and accurate measurement of longitude was so important to navigation at sea, that in 1714, Queen Anne of Great Britain, then the world’s most preeminent sea power, established a reward of 20,000 pounds sterling (equivalent to 1.9 million pounds or $2.8 million dollars in year-2000 dollars), to be paid to the first person or persons capable of developing a practical method of determining longitude at sea.

This first sea-worthy, highly accurate chronometer was developed by John Harrison (1693-1776), a carpenter, in 1761. His struggles and tribulations suffered during the decades-long gestation period for his device were chronicled in the excellent movie “Longitude“, which I highly recommend.

Incidentally, the key innovation of Harrison’s seaworthy chronometers, which were later designated as models H1, H2 &  H3, was dubbed the “Grasshopper Escapement“.

In 2008, world-renowed physicist Stephen Hawking (yes, that’s right, the wheelchair-bound, Cambridge, England-residing, computer-voiced supergenius, we all know who he is) unveiled the Corpus Clock, a very unique clock, the work of horologist (a horologist is a clock-maker, or someone who studies chronology. Horo is Greek for “Hour” or “Time”) John Taylor, who has built a disturbing public timepiece[VIDEO]  which utilizes an ‘upgraded’ type of grasshopper escapement. If you are like me, and love to fool around with electronics and electric circuits, you already know John Taylor as the inventor of the thermostatic switch, used in umpteen millions of household appliances.

Harrison’s chronometer also incorporated two other mechanical engineering advances: a gridiron pendulum that consists of lengths of brass and iron arranged in such a way that the length of the pendulum from pivot to bob is always constant, regardless of the temperature. The grasshopper escapement described above, in concert with the other features of the Harrison chronometer, such as lignum vitae (a self-lubricating wood) rollers mounted on non-corroding brass spindles, helped to virtually eliminate friction from the Harrison device.

A British Captain leaving on a long sea voyage would set the Harrison chronometer to the exact same time kept in Greenwich, England. This is the origin of what is known as GMT, or Greenwich Mean Time. GMT is a way of universally telling time across the world. For example, the Eastern Standard time zone, within which Boston is located, can be refferred to as “GMT-5″, which means the time in Boston will be five hours behind the time in Greenwich, England. While I’m on the subject of GMT, know that GMT is referred to as “Zulu” in the U.S. military.  As in “United States Navy SEAL team 6 will deploy to HVT#1 compound in Abbotabad, Pakistan at 0530 Zulu”.

On the high seas, the Captain or Navigator of the vessel would then be able to determine the local time by observing the position of the sun. The difference between the local time and the time in Greenwich, which was maintained throughout the voyage accurately by the Harrison chronometer, could then be used mathematically to derive (24 hours of time is equivalent to 360 degrees of longitude) the ship’s distance from Greenwich, which is longitude.

In 1772, Captain James Cook used a Harrison-styled (for more on the fascinating backstory on Cook’s voyage, I again recommend the movie “longitude”) chronometer to explore and accurately chart the Pacific ocean for the British Admiralty. The Harrison chronometer was a huge advance in navigation, but it only worked in fair weather when the position of the sun in the sky could be observed to determine local time. This restriction was removed with the invention of radio.

Radio signal navigation

The first equipment to be used for radio navigation arrived in 1912, but it suffered from accuracy problems. Pulse radar, developed during World War II, made it possible to measure the short time differences between transmitted and received radio waves. This is the same principle used by police speed trap radars: the equipment sends out a radio pulse and measures the time it takes for the pulse to travel to a vehicle, bounce off it, and arrive back at the radar gun. The time difference tells the radar’s computer the car’s distance from the gun.

The GPS system uses a constellation of 24 active GPS satellites orbiting the Earth

The early radio navigation systems used this same principle of sending radio waves and measuring time differences. In many of the early systems, radio signals were sent from two towers, at exactly the same time, traveling at the same speed. The navigator’s radio receiver would then detect which of the two radio signals arrived at the navigator’s position first, and then would measure the amount of time that would elapse until the arrival of the second radio signal.

The navigator would be aware of the exact positions of the two signalling towers, the speed of the radio waves and the time difference between them when they arrived at the navigator’s position. If the radio waves had reached the navigator’s position at exactly the same time, expressed as [Delta] t=0, the navigator’s position would lie exactly between the two signalling towers. If instead the second radio signal arrived two time units before the first signal, then the navigator would know that their position would be closer to the second signalling tower than the first one.

Two radio signals give the position of the receiver on a line between two radio sources

Of course, this is only a one-dimensional position fix. A one-dimensional position fix is not very useful, but if three radio signalling towers are used, then the radio navigation system is capable of delivering a two-dimensional position fix. As in the previous example, the navigator’s receiver records which signal arrives at the receiver first and the time differences between the first signal and the others. Using this knowledge of the signalling tower’s positions, the speed of the three radio signals and the difference, or delta, in the arrival times of the signals, the receiver calculates a two-dimensional position.

Adding a third radio signal source allows a two-dimensional position fix to be calculated

GPS is radio navigation using satellites instead of signalling towers

GPS uses radio waves to determine position, just as in the early radio-based navigation systems like the ones described above, but with an important twist. Land based signalling towers are replaced by satellites orbiting 20,200 kilometers (12,552 miles) above Earth.

These satellites do not transmit radio pulses, however. Instead, the GPS satellites transmit a sequence of numbers that enable a GPS receiver to measure its distance from each satellite instead of its position betweenthe satellites.

Alright, Dear Reader, you know this is the point in my discussion where I’m really going to start breaking it down for you. Remember, in GPS, as in many technological wonders of our modern age, God is in the details. Stay with me, as this technical discussion will reward your dedicated attention span to this article by giving you a more complete understanding of how your GPS receiver operates and solves for position.

I am going to simplify some of the details of the transmitted number sequences in order to provide to you an easily comprehensible example, no hate emails please. This is my disclaimer.

Starting at a known time, t0 in the example I am about to describe, the satellite broadcasts a number sequence. For the purpses of illustration, let us say that the satellite in question sends the number 10 at t0, the number 23 at time t1, etc., and this satellite continues to send a different number each time segment without repeating itself for a millisecond.

GPS satellite sending and GPS receiver detecting a transmitted number sequence

The GPS receiver already has the exact same number sequence stored in its electronic memory and “knows” the exact time when the satellite began to transmit its number sequence. At time t0, the receiver starts at the beginning of the number list in its memory and advances one number for each time segment.

When the GPS receiver detects that number 10 has arrived from the satellite, it notes it is at number 42 in its own list, which means it took seven time segments for the radio wave carrying the numbers to get from the satellite to the receiver. If the radio wave travels 3219km (2000 miles) per time unit, the receiver knows the satellite is 22,531 kilometers (14,000 miles) away. This technique is known as ranging and requires exact time synchronization between the receiver and the satellites in addition to a known number sequence.

But, of course there is a problem with time, and to solve that problem, we need to use one of Einstein’s theories. And no, I’m not making this up.

How GPS bends time

The GPS system uses a constellation of 24 satellites that transmit this time-stamped information on where they are. By multiplying the elapsed time of reception by the speed of light, the GPS receiver can calculate position from each of the satellites it is currently receiving radio signals from.

Each GPS satellite is equipped with an atomic clock, the most accurate type of chronometer available.

For accuracy to within a few meters, the satellites’ atomic clocks have to be extremely precise – plus or minus 10 nanoseconds.

10 nanoseconds? I know, I know, Dear Reader: many of us, myself included, are aware of and can easily comprehend time divisions in the milliseconds. These types of chronological measurements are used in computer programming and applications. But nanoseconds are a much smaller unit used to divide time – and there’s a big problem besides the conceptual challenges associated with grasping such minute time divisions.

These amazingly accurate atomic clocks never seem to run quite right aboard these GPS satellites. One second as measured on each GPS satellite never quite matches a second as measured on Earth.

Wait a second: what the heck? Why not? I thought you said the atomic clocks were the most accurate form of chronometer available…why is it that there are these time differences?

Well, Dear Reader, the answer is that Einstein knew what he was talking about with that relativity stuff. Mind you, I’m not talking about Einstein’s much broader scientific theory of _general_ relativity, I’m speaking of Einstein’s early relativity predictions that were later proven to be observable in the cosmos.

Einstein, relativity, and GPS

Albert Einstein’s special theory of relativity predicts that a clock that is traveling fast will appear to run slowly from the perspective of someone standing still. The GPS satellites move at around 9,000 miles per hour, and this is enough speed to make their onboard atomic chronometers slow down by 8 microseconds per day from the perspective of a GPS receiver.

This is more than enough to completely corrupt the location data. In order to counter this effect, the GPS receiver adjusts the time information it receives from each satellite by using an equation:

GPS receivers use the above equation to correct for time incongruousness that results from Einstein's theory of special relativity

The amount of time that has elapsed on Earth during the delta time interval of the satellites’ radio transmission segment is equal to the amount of time elapsed as measured on the GPS satellite in question divided by the square root of 1 minus the exact velocity of the satellite (around 9,000 MPH) divided by the speed of light, or 186,262 miles per second.

Yowza!

How GPS uses triangulation to solve for position

Solving for position using GPS satellite radio signals (corrected for time as detailed above) is accomplished by means of triangulation, which means if you know your distance from three fixed locations, you can calculate your own position. I have illustrated in my prior, simplified examples how a navigator can find their position in two dimensions.

In two dimensions, a GPS receiver measures its distance from satellite #1, which means the navigator is somewhere on the conceptual circle of potential positions that surrounds GPS satellite #1. Next, the receiver measures its distance to GPS satellite #2. The GPS receiver must then lie somewhere on the circles of potential positions that surround satellites #1 and #2. There are only two potential positions where the GPS receiver can be located, and each of these two potential positions is where the two circles of position potentialities intersect.

Triangulation is used to find position from GPS satellite receptions

The GPS then measures its distance from GPS satellite #3 and, just as before, the only potential positions for the GPS receiver are where the circles surrounding the three satellites intersect. Using triangulation, there is only one location on the Earth where all three position potentiality circles intersect, so at this point, the GPS receiver has calculated its position.

Piece of cake, right? GPS navigation sounds complex because it is, but fortunately the GPS receiver equipment performs these calculations with great speed and accuracy, hiding all the nasty math it takes to solve for position from the navigator.

GPS solves for latitude, longitude, and altitude too

The GPS system is really super because it uses these three intersecting spheres of position potentialities to determine a three dimensional position comprised of latitude, longitude, and altitude.

My examples above stress the importance of time synchronization and the satellites’ exact positions. This will help me explain the concept of Selective Availability, or SA, later in this article. For now, just remember that if the receiver is not exactly synchronized to the satellites or if it does not know the satellites’ precise positions, the position the GPS receiver calculates will be inaccurate.

Signals from just three GPS satellties are enough for a GPS receiver to calculate its position, but a fourth GPS satellite signal is used to synchronize the time between the satellites’ highly accurate onboard atomic clocks and the less accurate quartz chronometer onboard the GPS receiver itself.

If radio signals from only three GPS satellites are available, one signal must be used to synchronize time, leaving only two signals to calculate a two-dimensional position.

The knowledge of the GPS satellites’ exact positions is the other vital aspect of positioning with GPS signals. A GPS receiver would not be able to accurately determine its own position with simply the radio signal time difference information from the GPS satellites, it must also know the exact positions of the GPS satellites in order to determine its own location on the Earth. Each satellite knows its own position, as well as the positions of all of the other GPS satellites in the GPS satellite constellation, and each satellite sends this orbital position information down to the GPS receiver.

GPS satellite position information

As I explained above, the GPS receiver has a list of satellite positions that is transmitted to it from the GPS satellites, but how does it know the positions of the GPS satellites when the GPS receiver is turned off or is moved while the power to the GPS receiver is turned off? How will it know where the satellites are when it is turned back on?

If a GPS receiver has been turned off for more than six months or has been moved more than 300 miles while it was turned off, then its internal almanac is inaccurate and cannot be used. Fortunately, all the GPS satellites transmit an updated orbital position almanac with regularity.

When a GPS receiver is turned on, it initially performs a check on its latest received orbital position almanac. If the GPS receiver determines that this almanac makes no sense according to a set of predefined parameters, then the GPS receiver will wait until it receives a new almanac so it can then calculate its position.

This delay between when a GPS receiver is turned on and when it calculates its position is called Time To First Fix (TTFF). Sometimes solving for the first position fix reading can take a while, and the reason behind this is usually that the GPS receiver is waiting for a new almanac from the GPS satellites.

So far in my discussion of the GPS system, I have spoken only of two entities: the satellites and the GPS receiver users. The third component of the GPS system is ground control. Ground stations monitor the satellite positions, control the satellites and determine the overall GPS system health.

Ground control also maintains the up-to-date orbital positioning almanac that is beamed to the GPS satellites, and in turn, down to the GPS receiver units on the Earth.

The United States military, Navstar, WAAS, the ionosphere and Selective Availability

How’s the above for a section title heading? A mouthful?

The concept of the GPS system was conceived of in 1960 to increase the accuracy of intercontinental ballistic missiles. Just another example of your tax dollars at work for you Americans out there, and another example of military space technology come down to Earth in the form of some civilian technology innovations.

The U.S. Air Force began the development of the GPS system and called it the Global Positioning System. Soon afterwards, the other branches of the U.S. military became involved in the development of the GPS system and the Pentagon changed the system’s name to Navstar – a name that did not stick. The entire system cost nearly $10 billion to develop and was fully operational in April, 1995.

Eighteen satellites is the minimum number needed to cover the entire Earth, but the actual number of GPS satellties that make up the GPS constellation in orbit flunctuates between 24 and 29 due to factors such as maintenance of spare satellites and upgrading of GPS satellites.

The GPS system designers had to deal with an interesting problem that affected the accuracy of the radio waves being transmitted through the Earth’s ionosphere and down to the GPS receivers on Earth. The Earth’s ionosphere slows down the satellite radio waves and would potentially affect the accuracy of the position data determined buy the GPS receivers.

The GPS system designers used two techniques to overcome the error in the GPS radio signals introduced by the ionopshere, one for civilian GPS receivers, and one for military receivers.

You see, the GPS system was designed by the U.S. military, and there was a very valid concern that the system could be used by America’s enemies as well as the U.S. military. After all, any country or group could potentially receive the radio signals beamed down to the Earth by the GPS satellites. As these radio waves are simply radio broadcasts, there is no point-to-point secure radio transmission to ensure who is using the GPS system and for what purpose they are using it.

GPS satellites beam two types of radio signals down to the GPS receivers: Precision Code, or P Code, and CA Code, or Coarse Acquisition Code. The CA code was public, and any receiver could detect it. The P code was made so complex that only military receivers, known as authorized users, can detect and use it for navigation.

The CA code is transmitted at 1575.42 MHz, which is called the L1 frequency. Each civilian GPS receiver is programmed with with a model that reports how much the L1 signal slows down when it hits the ionosphere. Based on this model, the GPS receiver can correct for ionospheric interference.

The solution for military receivers is more complex, but this complexity brings with it more accuracy. The P code is transmitted on the L1 frequency and at 1227.6 Mhz, which is called L2. Radio waves of different frequencies slow down differently when they hit the Earth’s ionosphere, so military GPS receivers compare the delay between L1 and L2 to figure out how much they slowed down. Comparing two signals is more accurate than using an ionosphere model because the model may be slightly off for any given GPS receiver location, whereas the comparison of the L1 and L2 radio signals is always accurate.

WAAS, or Wide Area Augmentation System, correction data decreases the impact of an inaccurate ionosphere model in civilian GPS receivers.

Selective Availability, WAAS, and Differential GPS

P code is inherently more accurate than the CA code transmitted by the GPS satellties, so military GPS receivers are generally accurate to 1 meter, or 3.3 feet. The CA code provides accuracy to about 15 meters, or 49.2 feet, which is less accurate than the P code, but still accurate enough to be deadly in the hands of the wrong people, so the GPS system designers decided to limit the usefulness of the CA code by making it deliberately less accurate than it was designed to be. The policy of deteriorating the CA code accuracy is called Selective Availability (SA).

Selective Availability randomly introduced position error into the CA code. The deliberate error changed the accuracy of a civilian (unauthorized) receiver from 15 meters (49.2 feet) to somewhere between 15 meters (49.2 feet) and 100 meters (328 feet). Selective Availability was a nuisance and as GPS use spread, many people complained. As a result, on May 2, 2000 the U.S. military eliminated SA at the behest of the U.S. government. Civilian GPS receivers are now nominally accurate to 15 meters, or 49.2 feet, as a result of this SA elimination.

While SA was still being enforced, some clever people developed a way around it using a technique known as Differential GPS. DGPS detects and eliminates the random error of SA and makes civilian receivers accurate to approximately 5 meters (16.4 feet). Since the removal of SA, DGPS is still used because it still increases civilian receiver accuracy, but is quickly being replaced by WAAS.

The FAA, or Fedral Aviation Administration in the United States determined that GPS is not accurate enough to be used for aviation, so it has added a form of differential GPS called WAAS to increase accuracy.

WAAS is more accurate than current DGPS services, it is available for locations in the U.S., parts of Canada and Mexico and it is free. GPS receivers equipped with WAAS have increased accuracy, from 15 meters (49.2 feet) to 3 meters (9.8 feet). unfortunately, the WAAS correction signals are most easily received in flat, open spaces, so you may not be able to pick tthem up in mountainous terrain.

Still more to come from the Hub Tech Insider on GPS – Build Your Own GPS

In upcoming articles, I will delve much deeper into DGPS, or Differential GPS, and illustrate for you some of the very innovative ways in which DGPS has been employed in applications such as coastal sea or littoral navigation, and even how it is used to keep track of the maintenance needs of huge public works such as dams and bridges.

I am also really excited about an upcoming feature I am hard at work on, a more hands-on article in which I will demonstrate how you can build your very own, battery-powered GPS receiver. I will then take you through some very basic computer programming code, written in a language called Processing, also known as Wiring, which is very similar to the C computer language. (C is one of my favorite computer programming languages, I must admit. Any computer programming language that utilizes a C-type syntax, I enjoy working with – except Java. No hate mail.)

The built-from-scratch GPS unit I will demonstrate how to build is portable, battery powered, and includes a bluetooth module for communicating wirelessly with your PC. You will be able, once you have followed my complete and detailed instructions for constructing this GPS device, to poll the GPS module for data, known as sentences in GPS parlance, to extract location data in the NMEA protocol. NMEA stands for National Maritime Electronics Association, and the NMEA protocol is fundamental to digital, programmatic interactions with GPS modules.

As you can well imagine, I intend to break it all down as usual, and I think it will be fun to finally post some of my terrible computer programming code. As you know, I am not a professional programmer, but a PMO Director, but for some strange reason, ever since I was a little, tiny tiny nerd boy, I have been programming computers. I just don’t talk about it too much, because programming computers is just something I have always done, not something I hang out my shingle on, so to speak.

Anyways, don’t worry, just like the code I write for ecommerce sites, this GPS code is simple, easy to follow, and always, always runs. When you see the latitude and longitude information flowing from this device wirelessly onto your PC, you will be very happy. There is nothing like getting involved hands-on with technology to increase your understanding of difficult tech concepts, and I hope you will have as much fun building your own wireless bluetooth GPS module as I did.

Homemade, battery-powered GPS unit with Bluetooth module on a solderless breadboard

I will also show you how to run this GPS code on multiple platforms, such as Linux and Mac OS X, not just Windows PC machines. I always like to get my code running on all three platforms if possible – I will demonstrate how to get your development environment running for Processing coding on all three types of personal computer systems.

You probably already know that a complete glossary of GPS technology terminology is in the works too here at the Hub Tech Insider.

Want to know more?

You’re reading Boston’s Hub Tech Insider, a blog stuffed with years of articles about Boston technology startups and venture capital-backed companies, software development, Agile project management, managing software teams, designing web-based business applications, running successful software development projects, ecommerce and telecommunications.

About the author.

I’m Paul Seibert, Editor of Boston’s Hub Tech Insider, a Boston focused technology blog. You can connect with me on LinkedIn, follow me on Twitter, even friend me on Facebook if you’re cool. I own and am trying to sell a dual-zoned, residential & commercial Office Building in Natick, MA. I have a background in entrepreneurship, ecommerce, telecommunications and software development, I’m the Director, Technical Projects, I’m a serial entrepreneur and the co-founder of twitterminers.com and Tshirtnow.net.

More Articles From Boston’s Hub Tech Insider:

• Twelve Tips For Agile Project Planning and Estimating
• Eight ways to tell if your Project Team is on the Way Up, or on the Way Down
• The Twenty Laws of Testing Computer Software
• Why Designing for a VUI is harder than designing for a GUI
• The Hub Tech Insider Glossary of Mobile Web Terminology
• The Hub Tech Insider Glossary of Stock Options Terminology
• How many Stock Options should executives at a startup be granted?
• Agile Development In Practice
• What is ‘Management By Walking Around’?
• Boston Area Video Game Companies
• Demandware eCommerce
• How to expand your professional network on LinkedIn
• How to use LinkedIn in your job search
• Twitter and network effects
• How much bandwidth does a smartphone use? How much bandwidth does an Apple iPad use? How much bandwidth does an Apple iPhone use?
• What is Scrum?
• What is a “Use Case”?
• What is a “User Story”?
• What is Indirect Spend?
• What is EDIINT? What is AS2, AS1, AS3 and AS4?

Related articles

• GPS group slams LightSquared’s new plan (infoworld.com)
• Sat nav to benefit car insurance (autonetinsurance.co.uk)
• The GPS navigation system (jiaho.wordpress.com)
• Surprise! Your GPS Device (Probably) Isn’t Spying On You (businessinsider.com)
• What is the Difference Between GPS and RFID Tracking? (brighthub.com)
• Understanding GPS Coordinates (brighthub.com)
• Satellite Clock Errors and GPS Tracking Errors (brighthub.com)
• GPS, Wi-Fi: How your iPhone knows where you are (macworld.com)
• MapQuest Integrates Skyhook: Can It Outperform Google Maps? (nytimes.com)
• Help Entering Your GPS Coordinates (brighthub.com)