Introduction to GNSS II: GPS Signal Processing

12 min readSep 10, 2020

This is my second story for GNSS introduction.

My first story introduced some basic principles of GPS positioning, today I will focus on GPS signal structure and introduce how to extract the information needed for positioning from GPS signal.

Start with Sides

Before serving the main dish, let’s first see how GPS became a game-changer in the Gulf War, which is believed to be the first high-tech war in history. Before the Gulf War, fixed landmarks are used as references for localization and navigation. Under bad weather conditions (e.g., nighttime or fog) or difficult terrain conditions (e.g., desert), landmarks will have great uncertainty, making it hard to locate position accurately.

The existence of GPS allowed the alliance to know their accurate positions, and also enabled precision strike to hit Iraqi’s military facilities, oilfield, and communication network, ending the war in just six weeks. The victory of the Gulf War does not only belong to the alliance, we should also give credit to GPS.

Let’s look at another old news. In 2007, a Chinese Ph.D. candidate Xingxin Gao (now a professor at Stanford) submitted a paper and got scolded by Chinese media and treated as a traitor afterwards. In that paper, she decoded Beidou’s civil signal before it has been released by the Chinese government four years later. So, can Beidou’s military signal be hacked using the technique in the paper? And is she really a traitor, as said by some mainstream?

Before answering the questions, let’s go through some background of signal processing, and then introduce GPS signal structure to understand the civil and military signal. In the end, some interesting animations will show how to extract information for satellite signals.

Signal Processing

Signal is a function that conveys information about some measurements. In electronics, it refers to any time-varying electromagnetic wave that carries information. Signal needs to be processed so that the carried information can be extracted and used.

Characteristics of Signals

The three main features of signals are:

Amplitude (A) ⇒ the peak of the signal from the center line
Frequency (f) ⇒ how often signal sequences repeats across time
Phase (ϕ) ⇒ how many degrees the signal shifts from the original point

From left to right: signal with different amplitudes, frequencies, and phases.

Signal Modulation

Modulation is the process of imposing data signal onto a carrier wave. A Carrier wave is usually a sine wave with higher frequency. It contains no information but helps the data to be correctly extracted by the user with the existence of environmental noises.

Three commonly used modulation schemes are Amplitude Shift Keying (ASK), Frequency Shift Keying (FSK), and Phase Shift Keying (PSK).

In ASK, the amplitude of the signals is modulated to represent the signal levels (0 and 1), while frequency and phase remain untouched. Similarly, FSK modulates data signal on the carrier wave’s frequency, and PSK on the phase.

For the above-mentioned modulation schemes, only one user is allowed for one segment of frequency (frequency band), or the other way around, one frequency band is allocated to one user, which is a waste on the limited band resources.

Code-Division Multiple Access (CDMA)

CDMA is a technique for allowing multiple users on one frequency band at the same time. Each user is assigned a pseudorandom noise (PRN) code (this will be introduced later), just like the bar codes assigned for different products in shopping malls.

Diagram for CDMA modulation. The transmitted signal is the XOR of the data signal and PRN code.

Correlation

Correlation measures how two signals match with each other. If two signals are highly matched, then their correlation will be high. If they differ in shape, phase, or frequency, then the correlation would be low.

Second correlation example. Correlation of sine waves is still a sine wave. There are multiple peaks as long as the phase matches (when signal 2 turns red).

Third correlation example. The more signal frequencies differ, the less their correlation amplitude will be.

Demodulation

The inverse process of signal modulation is demodulation, which extracts data information from the received signals.

For the CDMA system, the separation between the data for the desired user and data for others is important because all uses share a same frequency band. PRN code functions as a key for communication with the received signal and the user.

Different users have different keys (PRN codes).
One door (data modulated for one user) can be only opened by one key.
Inserting the key into the door is done by correlation.

The user will generate PRN code locally to correlate with the received signal. If the signal matches the local PRN code in phase, a correlation peak occurs. Sign of the correlation peak indicates if the datum modulated is 1 (positive correlation peak) or -1 (negative correlation peak).

GPS Signal Structure

GPS uses CDMA and PSK for signal modulation; thus, it’s composed of three parts: carrier wave, pseudorandom code, and data (navigation message). Pseudorandom code and data are modulated through PSK onto carrier wave, which is in the form of a sine wave. Then satellites will transmit the GPS signal out into space.

Carrier wave

Legacy GPS signal operates on two frequency bands, L1 band (1575.42 MHz) and L2 band (1227.6 MHz). This means there are two carriers wave used to modulate data. Such high frequencies ensure the propagation of signal would not be influenced by all weather conditions and can penetrate through clouds and other obstacles.

GPS satellites have a speed of 3.9km/s, thus due to the Doppler effect, the frequency of the received signal may not be the original L1 or L2 frequency. The frequency difference is then called the Doppler shift. Typically, the Doppler shift is within ±10kHz.

PRN code

PRN codes are the signatures of the GPS signals because two different PRN codes have no correlation, which helps users to distinguish GPS signals from different satellites. The minimum pulse of PRN code is commonly referred to as a chip (shown in GPS signal structure figure), which is used to measure the length of the PRN code. The reciprocal of the period of a chip is called chip frequency.

Two kinds of PRN codes are modulated on the GPS signals. One is called Coarse/Acquisition (C/A) code, which is public for civil use, and the other one is called Precision (P) code, which is encrypted for authorized users only such as the military.

Table of the PRN characteristics.

Higher code frequency leads to better precision, that’s why C/A code is called Coarse/ Acquisition code and P code Precision code.

It’s not hard to decode C/A code. After receiving the whole GPS signal lasting for 50 code periods (50 ms), the C/A code sequence can be derived using Xingxin Gao’s method. This is because in 50 ms, C/A code will repeat 50 times, and then we can use its correlation characteristics to decode the sequence.

However, it’s impossible to use the same method to hack P code. Since the period of P code lasts for 1 week, then one needs to collect the signal consistently for 50 weeks (notice that one year has about 52 weeks)! Even if assuming that P code sequence would not change during the whole time, it requires a space of at least 93877 TB to store the 50 weeks’ data, not to mention the post-processing needed afterwards.

PRN Code Correlation

The randomness of the PRN code can be shown by correlation. A correlation peak only happens once when the PRN code correlates with itself of zero phase difference. Random signals have the same property. But actually, PRN code is not random because the code sequence is fixed, thus it’s called pseudorandom code.

Correlation of satellite №1’s C/A code (PRN1) with a phase delayed version of itself. The blue dot marks the first chip of the PRN code, and the red dot is the correlation result at the current time. The correlation time series is similar to the first correlation example of random noise.

The correlation of two different PRN codes doesn’t have a peak. In this way, user can’t use PRN2 to demodulate data on PRN1 because the correlation is always around 0. This makes it possible to separate the data modulated on one satellite with the other.

Navigation message

The navigation message is the data modulated on carrier waves and PRN code. The minimum pulse of the data signal is referred to as a bit (shown in the GPS signal structure figure), which is the smallest measurement of transmitted data. The navigation message is broadcasted by each satellite at 50 bits per second and provides essential information for positioning solutions.

Table of the GPS navigation message.

GPS Data Demodulation

Data demodulation is the process to extract navigation messages from the modulated GPS signal. As introduced before, it’s achieved by performing correlation of received signal and a copy of local signal generated by the user. The copied signal is composed of carrier wave and PRN code, without navigation message (the user doesn’t know anyway).

In order to have a correlation peak, receive and copied signals should have the same:

Carrier wave frequency,
Carrier wave phase,
PRN code sequence, and
PRN code phase.

This process is implemented by signal acquisition and tracking.

For different satellite signals, these attributes differ, because satellites have different distances and relative speeds w.r.t. user. Different distances lead to different signal time delays, thus different phases for carrier wave and PRN code. Different relative speeds lead to different Doppler shifts of the carrier frequency.

Thus, we need to acquire and track each satellite signal separately.

Signal Acquisition

The user knows the PRN code sequence for each satellite but doesn’t know which satellites are visible. If the received signal doesn’t have the transmitted signal of a certain satellite, then it indicates the satellite is not visible. The process to determine visible satellites is called signal acquisition.

Signal acquisition can be implemented by detecting the correlation peak of the received signal and copied signal. Before acquisition, carrier wave frequency and code phase are unknown, so the user will traverse different combinations of Doppler shifts and code phases to generate a copied signal to correlate with the received signal.

Diagram of signal acquisition for one satellite. The horizontal axis searches all the possibilities of the C/A code phase, each bin representing one chip. The vertical axis searches the possibilities of the Doppler shift, each bin representing 500 Hz. A correlation peak is expected at the bin where the signal (circle at the upper right) locates.

In this way, signal acquisition is a 3D search in the following dimensions:

satellite dimension (equal to total number of GPS satellites, 31)
Doppler dimension (equal to 41, if bin size = 500 𝐻𝑧 within ± 10 𝑘𝐻𝑧 range)
code phase dimension (equal to PRN code length if bin size = 1 chip)

The total search space is 31 × 41 × 1023 (HUGE!) for C/A signal acquisition. For P code signal, it’s even worse given that the P code phase dimension is 6.18 × 10¹²!!

Speedup Using Priors

It would be very slow if searching for every possibility. If using some priors to reduce search space, signal acquisition can speed up a lot.

With almanac data including estimated satellite position, the user knows all visible satellites given the user’s rough location, reducing one dimension for satellite search. With ephemeris data, the user could estimate the Doppler shift and code phase in a narrower interval, greatly reducing the remaining 2D search space.

After using C/A signal to decode GPS information and obtain current time, the user can reduce P code phase to a few possibilities. C/A code acquisition serves as a pre-step for P code acquisition, which is why C/A code is called coarse acquisition code.

Signal Tracking

Doppler shift and code phase obtained in signal acquisition are only rough estimations down to the level of 500 Hz or 1 chip. Signal tracking can fine-tune the estimation to an accurate level and obtain the carrier phase accurately at the same time.

It’s called tracking because, in this step, the user will dynamically adjust the estimations which may change slowly across time.

Different modules are used to track different attributes:

Frequency-locked loop (FLL) ⇒ tracking carrier frequency
Phase-locked loop (PLL) ⇒ tracking carrier phase
Delay lock loop (DLL) ⇒ tracking code phase

All these lock loops are electronic control systems based on negative feedback.

Positive / Negative Feedback System

Feedback occurs when outputs of a system are routed back as inputs, forming a circuit or loop.

There are two types of feedback: positive feedback, and negative feedback. For a positive feedback system, its output is used to increase the input. For a negative feedback system, its output is used to decrease the input.

An example of feedback can be adjusting water temperature when bathing. If water temperature (output) is too high, then you rotate the faucet to the cold direction (negatively adjusting input), thus the water is cooler, and at the end achieving a suitable temperature at the end. No one would rotate the faucet to hot direction if feeling too hot (positively adjusting input) unless wanting to be scalded.

We can see that a positive feedback system will make things worse as it will exaggerate the difference of the system’s input and output, but a negative feedback system will negatively adjust the difference to keep it stabilized. That’s why the lock loops used in GPS signal tracking are all negative feedback systems, also known as negative feedback loops.

Negative Feedback Loop

A diagram of the negative feedback loop is depicted below:

It’s composed of three modules:

Discriminator will calculate the discrepancy between input VI and output VO.
Loop filter will calculate output based on the history of discrimination results. Filter output is the negative of the generator’s input, hence “negative” feedback.
Generator will generate a new output signal based on its input.

Lock loops (FLL, PLL, DLL) used in signal tracking share a similar structure of negative feedback loop. The main difference is how each module works.

FLL and PLL

FLL and PLL are used to track carrier wave frequency and phase respectively, thus the generator will generate a sine wave. For FLL, the discriminator will calculate the frequency difference to the received signal and user’s copied signal. Similarly, PLL will discriminate phase difference of the two signals.

Here is an animation showing how FLL works. Suppose after signal acquisition, the rough estimation of the Doppler shift has an error of 100 Hz compared with the true value. The phase difference is unknown and assumed to be 17.2 degrees.

The upper plot shows the received (recv) signal and copied (copy) GPS signal, and the lower plot shows the loop filter output. As we can see the frequency difference quickly drop to 0, but phase difference remains the same. After a while in the zoomed-in plot of filter output, we can see that it is slightly oscillating around the center repeatedly, achieving dynamic stability.

Here is an animation showing how PLL works under the same setting.

As we can see phase difference drops but not down to zero. And the output is not around the center of the plot (0 value), indicating constant bias. This is due to a frequency difference of 100 Hz, which makes PLL discriminator functions ill.

Another animation showing how to use FLL and PLL to overcome the situation occurred in the above two animations.

A simple solution is to use FLL first, and then switch to PLL after FLL tracks the signal for a while to have zero frequency difference. Notice that the received signal will flip for some time, this is because the navigation data will be modulated on the signal, and tracking loops are supposed to overcome this situation.

DLL

DLL is used to track code phase of the PRN signal, so it generates a code signal and discriminates code phase difference. DLL generates another two copies of early and late code signal using for discriminator, and the purpose is to make sure the present signal locates at the peak of the correlation results when stabilized, shown in the animation.

Demodulation after Tracking

PLL and DLL make sure the copied signal has the maximum correlation with the received signal. Data demodulation is then indicated by correlation result. If the correlation is above 0, the data modulated on the signal is +1, otherwise it’s -1.

The previous animations are showing an ideal case, using single satellite signal without any noise. However, in reality, the received signal is a combination of signals transmitted by several satellites and environmental noise.

The animation shows an example of a received signal and how data is being demodulated.

The last two plots show the results of data demodulation for satellite ID 1 and 2. Channel I and Q are the correlation results for two copied signals generated by the user. Channel I is used as an indicator of the sign of data, and Q is basically channel noise. After loop filter status changed to PLL, the data bit can be reflected by channel I output.

Obtaining the above result is only the first step for data demodulation, and there remains a lot of work to be done if the user wants to extract navigation messages from the GPS signal correctly and stably. However, it is beyond the interest of this story and thus will not be introduced here.

Some Takeaways

GPS signal is a combination of carrier wave, PRN code (C/A or P code), and navigation message.
C/A code is public for civil use, military P code is encrypted and unhackable.
Users will generate a local signal matching with the received one through signal acquisition and tracking.
Correlation plays an important role in data demodulation.

And also, welcome to visit my repo if you would like to see the code for generating the interesting animations!