For my senior design project I worked on implementing a GPS receiver using a National Instruments USRP software-defined radio.

Goals

My primary goal was obviously to produce a system capable of receiving GPS transmissions using the NI USRP and use that data to compute the location of the receiver, but I had several milestone goals on the way to that. These were:

USRP Hardware

The National Instruments USRP device allows applications to receive (and transmit) complex samples of up to 20 MHz bandwidth centered around a carrier frequency tunable from 50 - 2200 MHz.

Unfortunately, while the device itself worked exactly as expected and was easy to pull data from, I never got a recording with a good GPS signal in it, due to a combination of an antenna with poor reception at that frequency and poor signal quality in the lab where I did my testing.

Of course, because I knew that my recordings could have problems, either due to these or several other factors, I did the bulk of my development with a recording done by SETI, which I could be certain had a strong signal from GPS satellite #27 in it. Really the lack of usable data from the USRP only became an issue in the last few days when I needed a signal with multiple satellites in order to get data which I could feed into a position estimation algorithm.

GPS Transmissions

There are currently 32 GPS satellites in various orbits about the earth. Each of these satellites is putting out, among other things, a 25 watt signal at 1575.42 MHz (known as the L1 carrier frequency) containing a 1023-bit repeating signal called the Coarse/Acquisition (C/A) code as well as a 50 bits per second signal called the navigation message.

BPSK

Binary Phase-Shift Keying (BPSK) is what you get if you use the simplest possible method to turn a sequence of bits into a radio-frequency signal at some carrier frequency. The process goes as follows:

  1. Have an oscillator of some sort producing a sine wave at the designated carrier frequency.
  2. Turn the sequence of bits into a waveform by representing 1 as an amplitude of +1 and 0 as an amplitude of -1.
  3. Multiply these two sequences together.

DSSS

Direct-Sequence Spread Spectrum (DSSS) is a method of allowing multiple transmitters of equal power to coexist on the same carrier frequency simultaneously without any active coordination between them, at the cost of increased signal bandwidth and higher transmitter and receiver bitrates.

To use DSSS, you first have to designate a set of N-bit sequences called chip codes (also sometimes called spreading codes, because one of the effects of the technique is to spread out the spectrum of the original signal over a wider envelope). These chip codes must be selected to have the property that their auto-correlations and cross-correlations at every possible offset are bounded at some level significantly smaller than their auto-correlation at an offset of 0. In other words, the patterns need to look as dissimilar as possible no matter their relative alignments.

Then the transmission process requires that each transmitter have its own chip code which it will use that no other transmitter will be using. This chip code gets repeated much faster than the actual data rate (ideally there will be an integer number of repetitions of the chip code per data bit), and the two sequences (chip bits and data bits) get XORed together. Since the signals will tend to be represented as positive and negative amplitudes at this point and the resulting signal will be BPSK-modulated, this process simplifies to “multiply together the chip signal, the data signal, and the carrier signal”.

Now if the resulting signal is multiplied again by a chip code at the reciever, the result depends on which chip code is used as well as whether the chip code is aligned correctly. If a chip code is used which is not present in the signal, the bounded cross-correlation value guarantees that the result won’t be very large. Similarly if a chip code is used which is present in the signal, but it is applied at the wrong offset, the boundedness of the auto-correlation guarantees a small result. But if a chip code which is present in the signal is applied at the correct offset, the self-cancelling property of the XOR operation will yield the original data portion of the signal back again (plus the carrier of course, unless that got removed beforehand as well).

Of course, in the presence of noise (and for the purposes of this discussion, transmissions using chip codes other than the one we are trying to recieve look like noise) this despreading operation is less obvious and tends to be more of a statistical bias towards positive or negative values, but this can generally be remedied by low-pass filtering the signal.

GPS Reception Process

Quadrature Sampling

Almost by definition, the frequency domain representation of a real-valued signal will have negative-frequency components whose values are the complex conjugate of the corresponding positive-frequency components. But this restriction only applies to baseband signals (that is, signals centered around DC). When a signal is modulated up to some carrier frequency, there is no such requirement that the sideband below the carrier frequency be similar to the sideband above the carrier frequency.

In the end it turns out that the simplest way to reason about the whole process is that the signal at baseband is actually complex-valued, turns into a real-valued signal when modulated onto a carrier, and then comes back as a complex-valued signal again after demodulation. For historical reasons, the real and imaginary components of this complex signal are referred to as the “In-Phase” and “Quadrature” components.

This is relevant even in cases where we are transmitting and receiving a purely real signal. A phase or frequency mismatch between the oscillator used to transmit the signal and the oscillator used to receive the signal will manifest as a constant or time-varying rotation of the signal values around the complex plane.

Doppler Shift

The GPS satellites can be moving at speeds of up to several kilometers per second relative to a reciever. This manifests as a time-varying amount of Doppler shifting which can be up to 10 kHz or so in either direction. As mentioned in the previous section, this will cause the data signal from the satellite to rotate arount the complex plane at a rate of up to 10 kHz. Or seen a different way, the difference between the ideal carrier frequency used to demodulate the signal and the doppler-shifted carrier frequency that the arriving signal actually has will manifest as a residual carrier signal which is a complex sinusoid at up to 10 kHz. Either way, this rotation of the data signal will need to be accounted for in the receiver.

Signal Acquisition

There are just two main parameters which need to be known in order to decode a GPS signal: the C/A code offset and the Doppler shifting of the carrier frequency. The process of acquiring a lock on a particular GPS satellite consists of testing every combination of code offset and carrier frequency to see which yields the strongest evidence of data when applied to the incoming signal.

Signal Acquisition

Signal Acquisition

Signal Tracking and Decoding

Once a suitable carrier frequency and code offset have been located, decoding can begin. The decoding process essentially just produces a local oscillator signal and chip signal, and multiplies them both with the input (to remove the chip signal and the residual carrier signal), low-pass filters the result (to remove all the high-frequency noise because the actual data rate is much lower now that the signal has been despread), and captures data at 50 bits per second.

Naive Decoder

Naive Decoder

But the carrier frequency can change over time due to Doppler shifting, also the acquisition process gives a coarse estimate of the carrier frequency and we need a more precise value for decoding. It is necessary to add a feedback loop which will maintain the frequency and phase of the local oscillator. Observing that the imaginary component of the signal should be zero on average, the feedback loop can estimate the angle of phase mismatch using the arctangent of the ratio of the imaginary part of the signal to the real part.

Partial Decoder

Partial Decoder

It is also necessary to add a code offset feedback loop. This could be accomplished by periodically testing early or late versions of the chip signal for a larger magnitude result, but can be done in a more continuous fashion by duplicating the decoding process with an early and a late chip signal and using the difference of their magnitudes to gently push the code offset forward or backward.

Full Decoder

Full Decoder

Computing Location

The data from each GPS satellite includes a satellite-local timestamp \(S_i\) for each subframe as well as ephemeris data necessary to compute the location of the satellite at a given time. The receiver can give each subframe a local timestamp \(R_i\) as well, but this value will have some unknown offset \(T_0\) from satellite time.

If we knew the value of \(T_0\) it would be easy to compute the distance to a satellite by calculating the time of flight and therefore distance as \(D_i = c * (R_i + T_0 - S_i)\).

If we knew the receiver’s position \(\vec{P_r}\) we could compute the distance to a satellite by using the ephemeris data and the satellite time to compute \(\vec{P_i}\) and calculating distance as \(D_i = \left|\left|\vec{P_r} - \vec{P_i}\right|\right|\).

Combining these two methods of estimating distance, we can conclude that \(\left|\left|\vec{P_r} - \vec{P_i}\right|\right| = c * (R_i + T_0 - S_i)\). Since we know \(\vec{P_i}\), \(R_i\), and \(S_i\) from the transmissions themselves the distance computation requires only that this equation be solved simultaneously for four different satellites to compute the unknowns \(T_0\) and \(\vec{P_r} = [X_r, Y_r, Z_r]\).

Conclusion

I didn’t achieve all the goals that I set out to reach, and in retrospect this project seems to have been much more of a “research” project than a “design” project, but I successfully implemented the acquisition and decoding procedures and gained some experience with the optimization tradeoffs necessary to make them run quickly, and I gained a much more fundamental understanding of quadrature signals and spread-spectrum communications.