Correlation time! Come on! Lets correlate

(Apologies to K. C. and the Sunshine band).

The key maths behind receiving GPS is cross-correlation – the testing of two signals to see how alike they are, in frequency and phase. For a GPS receiver this technique is used to see if the pseudo-random bit pattern is being transmitted on a given frequency, and when required, measure the phase  difference between the local sample clock and the down-converted signal.

The process can be quite easily described:

1. Stretch the 1023-bit Gold code of the Space Vehicle to match the number of samples per millisecond of the incoming data stream.
2. Multiply the sample stream with the Gold code you are hunting for, treating the 0s in the stretched Gold code as -1s. If the Gold code is in the data stream, and they are aligned in phase, then this should remove the Gold code leaving just the intermediate frequency signal and any other noise.
3. Multiply the resulting stream with the sin() and cos() functions of the intermediate frequency that you are probing, to give you an ‘I’ (in phase) and ‘Q’ (quadrature) stream.
4. Sum up the I and Q streams for a sensible period of time (usually a multiple of length of time it takes to transmit a Gold code. These two numbers will indicate how much signal is in phase with the sin() and cos() functions used in step three. This can be treated as a 2D vector to measure phase
5. Finally work out the magnitude of the vector – i^2+q^2 will give you the power level for that Gold code, with that alignment, at that frequency

This all sees like a lot of work – for each sample, there is a sin(), a cos(), three multiplies and two additions – tracking 5 space vehicles using a 5456kHz sample rate will require at least a hundred of megaflops.

Work avoidance scheme

A simple trick can save the day. For one-bit samples (where ‘1’ indicates a positive value, and ‘0’ indicates a negative value), a binary XOR is equivalent to multiplication by either 1 or -1 as it flips the bit.

This reduces the process to:

1. Stretch the Gold code from 1023 bits to match the sample rate (in bits per millisecond)
2. XOR the raw bitstream with the stretched Gold code.
3. XOR the bitstream from step 2 with a binary string, which is ‘1’ where sine of the frequency being tested is positive (and ‘0’ where it is negative) to give the I stream. Also XOR the bitstream from step 2 with a binary string, which is ‘1’ where cosine is positive (and ‘0’ where it is negative) to give the Q stream.
4. Count up the ‘1’s and ‘0’s in the I and Q streams for a sensible time period, then subtract the ‘1’s count from the ‘0’s count.
5. Finally work out the magnitude of the vector – i^2+q^2 will give you the power of that Gold code, with that alignment, at that frequency

It should also be pretty self-evident step 1 (stretching the Gold code) only needs to be performed once, and that steps 2 and 3 can be performed in any convenient order. A less obvious optimization is that in step 4, you only need to count the ‘1’s, as you can always calculate how many zeros there must have been.

So, with all that explanation out of the way, here is my code that teases out GPS signals from the bit stream from a single bit ADC:

 cos_total = 0;
 sin_total = 0;

 for(i = 0; i < MAX_WINDOW_USED; i++) {
   unsigned int gc_bit = sv->gold_code_stretched[i];
   if(data[i])
     gc_bit ^= 1;

   if(gc_bit) {
     sin_total += intermediate_freq_sin_table[i];
     cos_total += intermediate_freq_cos_table[i];
   }
 }
 total = sin_total*sin_total+cos_total*cos_total;

So that is it – the key to detecting GPS signals in 14 lines of C!