How a GPS Receiver Gets a Lock

From: Tom Clark (W3IWI)

Any GPS receiver locking up on a GPS satellite has to do a
two-dimensional search for the signal. The first dimension is time -- the
GPS signal structure for each satellite consists of a 1023 bit long
pseudo-random number (PRN) sequence sent at a rate of 1.023 megabits/sec,
i.e. the sequence repeats every millisecond. To acquire in this
dimension, the receiver needs to set an internal clock to the correct one
of the 1023 possible time slots by trying all possible values. Most
receivers stop and dwell at each of the possible steps for a couple of
milliseconds, i.e. the receiver take 1-2 seconds to try all the
possibilities.

The second dimension is frequency. The receiver must correct for
inaccuracies in the apparent doppler frequency of the satellite and
"zero-beat" the signal. For reasons that I won't go into here (related to
the 1 msec code repeat cycle and a fellow named Nyquist), the coarsest
frequency steps a receiver can take during initial acquisition is 500 Hz,
but the receiver's crystal oscillator may be off by up to +/- 10 kHz or
so, so there are 20ish frequency cells that have to be tested. And this
process must happen for all N satellites that are in use. So, the
acquisition process can be quite laborious.

The usual search strategy is to start at an oscillator frequency
predicted on the basis of (a) what is my approximate position? (based on
either the last known position or the guess you "typed in"), (b) where
are the satellites now and what is their apparent velocity (based on the
almanac data downlinked from the satellite and stored in the receiver's
memory), and (c) what is the best guess for the receiver's crystal
oscillator error (based on the last known error and the current
temperature). At this frequency, the receiver tries all 1023 possible
code phases and if it sees some power, it will initiate a finer search.
If none of the 1023 states "smells" a satellite, it offsets the
oscillator to the next test value and repeats the process until something
"smells promising".

When you start "blinded", the receiver goes thru its initial search,
finds nothing and steps outwards. After a long while it may decide to
start all over again at the "zero" predicted value, or it may continue
into oblivion and initiate an "all sky" search on its own.

After the receiver "smells" a signal, it establishes two tracking loops
-- one is a phase-locked loop in the frequency domain and the other is a
time-locked loop in the 1023 bit code space domain with the goal of
tracking both the code and carrier phases for that signal.

Once it acquires lock on the first satellite it can start extracting data
from the GPS signals. The GPS signal structure has a 1500 bit message
sent at a rate of 50 bits/second taking 30 seconds. Most receivers
require the copying of a complete, unbroken 1500 bit message block to use
the signals. If you start decoding right at the beginning, it takes 30
seconds. If you started one bit late, the first complete message block
that can be decoded starts 30 seconds later, so you don't get the message
until 60 seconds after initial acquisition, and the average latency is 45
seconds.

To get a coarse 2-D position fix and make sure that the receiver's clock
is correct requires data from 3 satellites. The GPS-38/40/45 strategy is
to start with the highest satellites in the sky and try to get 3
satellites in lock. After the first 3 are found, the receiver has a
fairly complete story on the time/frequency characteristics and it
immediately opens up and looks for more satellites, and it uses them
after another 30-60 seconds (average 45 sec).

The Garmin receiver seems to have two channels, and it multiplexes them
amongst up to satellites it is searching for. Other receivers have more
physical channels, so the can do more parallel searches.

In this thread, people also questioned the absolute cold-start, factory
default, receiver is totally stupid, etc. reset times. If the almanac has
been erased, each GPS satellite sends down approximate, abbreviated
satellite orbital elements called the almanac data. A comple almanac set
takes 25 of the 30 second message blocks, i.e. 12.5 minutes, to be sent.
Also in the completly stupid, cold-start mode the Garmin receivers seem
to assume that the position is invalid as well as the almanac data, so it
begins searching for PRN1, PRN2 .... all the way up to PRN32 trying to
find the first 3 usable satellites. This wide search can take 20 minutes
or more.

To finish the story on how these receivers work, all the code generators
and tracking oscillators are implemented in VLSI DSP chips and the
tracking loops are closed in software by the receiver's computer. The
fundamental observables that are used for navigation are the precise
clock phase extracted by the code-locked loop with a precision of about
0.1 of the 1023 bit sequence (i.e. 100 nsec = 30 meters of "pseudorange")
and the carrier phase and phase rate averaged with a filter of a few
seconds (phase rate = frequency offset). The carrier phase/rate and the
code phase are smoothed in a (probably Kalman) filter to average out
measurement noise, selective avability diddles, etc. When 4 satellites
are being tracked, the set of 4 pseudoranges + 4 phase rates are combined
to give a 3-D position, 3-D velocity, clock timing bias and oscillator
frequency error, which is what you see on the LCD display.

Hope this tutorial helped to answer some of the questions ----

Regards, Tom Clark