The 20,000km view: How GPS works

Jamey Sharp

wow. many word. so dense

• this is an introduction; there's no quiz
• please hold questions to the end

Portland State Aerospace Society

Launching amateur rockets... For Science!

Commercial GPS receivers:
not built for rockets!

I'm a rocket scientist and you can too

Outline

• Time-of-flight positioning
• Signal vs Noise
• History and Politics
• GPS Modernization
• Data Layer
• Open Hardware and Software

Time-of-flight positioning

take a deep breath

GPS: What is it?

GPS: What isn't it?

• Purely passive, can't track you
• ... of course, your phone might send your GPS track somewhere

GPS: What isn't it?

• No maps
• ... just position: latitude/longitude/altitude/time

How does "trilateration" work?

Oops: Time-of-flight, not distance

• each satellite transmits "the time now is ..."
• receiver gets time-delayed messages:
  • 20,000km away: now - 67ms
  • 25,000km away: now - 83ms
  • 30,000km away: now - 100ms
  • 35,000km away: now - 117ms

but that's not all!

Doppler measurements provide an independent velocity estimate

Theory of relativity

• Special relativity: at 14,000km/hour, clocks run slower by 7.2 microseconds/day
• General relativity: at 20,000km altitude, clocks run faster by 45.9 microseconds/day

Want a clock that seems to run at 10.23MHz?

Run it at 10.2299999954326MHz —IS-GPS-200G

Signal vs Noise

take a deep breath

Nearest GPS satellite:
20,000km straight up

How far is 20,000km?

How far is 20,000km?

How much power does a GPS satellite transmit?

500W

20,000km later...

.0000000000000005W

and they're all transmitting at once

how could this ever work?

Direct Sequence Spread Spectrum!

A pure sine wave has all its power at one frequency

Carefully choose a pseudo-random sequence of +1 and -1

Multiply the signal by the pseudo-random sequence

How do you get your signal back?

De-spreading piles all the energy back into one power spike

What if there's interference?

• the interfering signal gets spread out
• while the real signal gets put back together

Accidental interference:

unlikely!

US military "anti-spoofing"

uses a secret spreading code

History and Politics

take a deep breath

Navigation has been the product of military history

...and global time synchronization is along for the ride

1707: Scilly naval disaster

1714: Longitude prize

prizes collected by John Harrison from 1736 to 1773

1773: Harrison's Chronometer H5

October 1940

LORAN-A development begins

June 1942

LORAN-A's successor

• 1946: Cyclan
• 1952: Cytac
• Eventually called "LORAN-C"

Made In Oregon

First field test locations:

• Hillsboro
• Medford
• Palo Alto

1961: Clock synchronization

1957: Navy → Coast Guard

1957

Transit

Transit use cases

• reset INS on submarines used as ICBM mobile launch platforms
• later used by civilians for precise surveying

Transit limitations

• might wait several hours for a satellite to be in view
• must observe the satellite for two minutes
• single pass accuracy: 200 meters
• compute time for position fix: 15 minutes

Transit influence on GPS

• dual-frequency for ionospheric correction
• satellite orbit determined by inverse operation
• global clock synchronization to 50 microseconds

1973: Pentagon thinks up GPS

prototype "Block I" sats launched 1978-1985

1983: KAL flight 007 shot down over USSR

1989-1994: first 24 "Block II" satellites

1995: GPS constellation declared "fully operational"

Selective Availability

• degraded civilian accuracy
• intended to prevent non-US military use
• limited usability for safety-critical applications
• turned off in 2000
• improved civilian receiver accuracy from 100 meters to 20 meters

GPS Modernization

• 1998: announced by White House
• 2000: authorized by Congress as "GPS III"
• 2008: contract awarded to Lockheed Martin
• 2014: first Block III launch planned
• 2016: first actual Block III launch?

given consequences of GPS failure,

can we trust GPS?

Other GNSS systems

• Russia: GLONASS
• Europe: Galileo
• China: Compass
• regional systems launched by France, India, and Japan

GPS Modernization

take a deep breath

why is US military GPS more accurate than ours?

ionosphere (85km-600km) delay

bad news: GPS receiver can't measure this

good news: it's frequency dependent

for science!

side note: Measuring the Total Electron Content in the ionosphere is one piece of citizen science you can do with GPS if you already know your location

why is US military GPS more accurate than ours?

• "L1" civilian signal at 1575.42MHz
• "L2" military signal at 1227.60MHz

better news: GPS modernization

• "L2" frequency will add a new "L2C" civilian signal
• new "L5" frequency will also be available to civilians

that's nice
but I'm impatient

WAAS/SBAS

• measure ionosphere delays from known locations
• then broadcast corrections from satellites

codeless tracking

• hacks to use L2 even though we can't decrypt it
• GPS modernization may break existing codeless receivers in 2020

Data layer

take a deep breath

navigation message

50 bits per second

complete message: 30 seconds

fishing for satellites

• locking a satellite requires knowing which spread spectrum code to look for
• how can you guess which satellites to look for if you don't know where you or the satellites are?
• try randomly until you get lucky for the first one, but then...

almanac

• approximate orbital parameters for all satellites: yay!
• ...but rotates through 1 or 2 every 30 seconds
• 12.5 minutes to recieve full almanac ("cold start")

better plan: try all satellites at once!

• FFT trick: compute intensive, but computers are fast now
• find all visible satellites in less than 1/10th of a second

found the visible satellites; now what?

need each satellite's precise orbit

e·phem·er·is /iˈfem(ə)ris/

noun: ephemeris; plural noun: ephemerides

a table giving the calculated positions of a celestial object at regular intervals throughout a period.

ephemeris

• detailed orbit, but only for the satellite you're listening to
• sent every 30 seconds
• between 18 and 48 seconds to full ephemerides ("warm start")

hot start

Given

• current ephemerides,
• accurate UTC time,
• position within 100km...

Lock and position fix should take less than a second!

but I'm impatient!

assisted GPS

• gets current ephemerides from a high-speed network, like cell data or wi-fi
• your phone almost certainly does this
• your phone might not support GPS at all without network assistance

assisted GPS shortcuts

• assisted recievers often have pretty good current time from network
• phones usually have approximate current location from cell towers
• together, it's easy to guess which satellites to look for

but I'm picky!

satellite ephemerides are a best-guess forecast

once per week, control segment reports what last week's orbits really were

surveying

• surveyors don't need a quick answer, they need a very accurate one
• record raw data over 24 hours to average out errors
• a week later, use accurate ephemerides to analyze the recorded measurements

other navigation message stuff

• clock corrections
  • even atomic clocks drift—and yes, GPS cares
  • like ephemeris, different for each satellite and sent only by that satellite
• satellite health
• ionospheric data
• UTC corrections

GPS modernization

• changes all the encoding details
• but the big picture is the same

Open hardware and software

take a deep breath

where's the openness?

good news

GPS operation is well-documented by US government

bad news

GPS hardware is the worst kind of proprietary

documentation only available with lots of money and an NDA

do we need their hardware?

1991-1992: Matjaž Vidmar's homebrew GPS/GLONASS receivers

• ham radio enthusiast and EE prof in Slovenia
• head of Laboratory for Radiation and Optics at the University of Ljubljana

1991-1992: Matjaž Vidmar's homebrew GPS/GLONASS receivers

Motorola 68k CPU + DSP CPU + discrete electronics

2011-2013: Andrew Holme's homebrew GPS receivers

2011-2013: Andrew Holme's homebrew GPS receivers

discrete electronics + FPGA + Raspberry Pi

other open projects using COTS hardware

• Clifford Kelley's OpenSourceGPS (late '90s to 2012)
• Andrew Greenberg's GPL-GPS (2005 Master's thesis)

current: PSAS' GPS RF frontend

GPS RF frontend possibilities

• stream into a BeagleBoard, accelerate using DSP core
• stream into an FPGA
• stream into a PC over USB and do everything in software
• log raw data from flying on a rocket—coming July 20th!

how hard is this, really?

• it kind of is rocket science
• but you can totally learn it
• I have a B.Sc. in CS, never taken a class in DSP or radio
• just read lots of Wikipedia articles

Summary
aka, GPS in 1 minute

take a deep breath

what is GPS?

find your position by trilateration from satellites

missing features: maps and surveillance

amazing science results

• theory of relativity confirmed
• method to measure ionosphere's total electron content due to solar wind

amazing engineering results

• signal that's below the noise floor still detectable due to direct sequence spread spectrum

positioning is still evolving

• GPS modernization
• other countries' systems

military created GPS
but we make it
awesome

come play at PSAS!