Find the signal in the noise

 GPS signals are very weak, coming in at about 120 dBm ... which is below the thermal noise floor of ~ 100 dBm! If you try plotting an FFT 2 MHz wide about the L1 frequency you won't be able to distinguish the signal from the noise.

(Figure from A Software-Defined GPS and Galileo Receiver)

But it is there, and we can find it! 

First, we need data. I used data collected with an RTL-SDR stick converted to complex output. The output from the RTL-SDR is interleaved unsigned short, whereas the input block expects signed complex numbers. I talked about this in a prior post; I use the gcc code myself. 

So when we have data we can build a very simple flow diagram in GNURadio to play back the file and visualize it using the Fast Autocorrelation Sink. As noted in a previous post, there is a bug in GNURadio which breaks the Fast Autocorrelation Sink, but it is an easy fix!

The Fast Autcorrelation Sink is documented on Balint Seeber's blog and provides links to why the fast autcorrelation sink is indeed so fast! If you aren't familiar with autocorrelation, it is the correlation of a signal with itself. At any given time the correlation of a signal with itself is perfect, but if you insert a time delay and look at a later signal compared to a previous signal we can see just how similar the later signal. 

For example let's visualize a triangle wave with a frequency of 1000 Hz - that is, 1000 peaks per second, or 1 peak per millisecond. Since each repetition of the triangle is exactly 1 millisecond apart and since there is no noise in the system we would expect that every millisecond we'd have a perfect correlation of the shifted signal to the current signal. In between those milliseconds the correlation would get worse until we were half a millisecond apart where the peaks from the original signal would line up with the troughs of the shifted signal, resulting in a negative correlation.

Here's a simple flowgraph in GNURadio to visualize the autocorrelation using the Fast Autocorrelation Block from gr-baz. First, we create a signal source of a triangle wave with a frequency of 1000 Hz. Then we insert a throttle - this throttles the rate at which the diagram runs so we can visualize the signal. Left to its own devices GNURadio would simply pump triangle waves as quickly as it could with the given CPU resources. Then we can visualize the waveform using a WX GUI signal sink and the autocorrelation using the Fast Autocorrelation Sink:

Note the color of the block interfaces: Orange. This means floating point. Most of the blocks will default to complex, which is what you'd want for a lot of radio work but in this case it just makes things confusing as you will be plotting the triangle waves in both the Re and Im space. You can double click on each block and change the types to floating point or POWERUSER TIP: Click on the block and use up/down arrows to change the type. Once the flowgraph is complete (or download it here) hit play and you should see something like this:

We see our triangle waves with a period of 1 Hz and the Fast Autocorrelation Sink showing peaks at 1 Hz, and negative peak at a rate of 1 Hz shifted by half a Hz. 

So now let's do it with a real signal. You can use the same flowgraph, we just need to substitute the signal source block for a file source and specify our complex file. And since the file is complex, we need to change the data types. Finally, the throttle should be set to the sample rate of your input source - in my case, 2048000 Hz for the RTL-SDR. For the fast autocorrelation sink you will likely want to tweak the size to make the number of milliseconds a reasonable number. For my use I did (2**18)/2. Here's the updated diagram, running with the Fast Autocorrelation Sink, which you can download from github.

We see nice peaks every millisecond. Why every millisecond?

The coarse/acquisition code for GPS (C/A) has a period of 1023 chips which are transmitted at a rate of 1.023 MBit/s. This results in period of 1 millisecond. BAM! You can read more about the encoding on wikipedia. The L1 carrier at 1575.42 MHz has two codes, the C/A code and the navigation message. The navigation message varies with time as the satellites move through space but the C/A code does not change.  The C/A code is used for locking onto the satellites: Each satellite has a different unique C/A code. Earthside a receiver generates a particular C/A code and then shifts it in time and frequency to correlate the known C/A code with the C/A code of the satellite. Since we don't have a perfect clock we have to shift in time to line up our signal with the GPS signal timing and since the satellites are moving rapidly they frequency we receive is subject to a doppler shift of up to 5kHz (10kHz if we are moving very quickly, say, on a rocket or missile)

But that's a story for another day.