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!

 

Advertisements

2 thoughts on “Correlation time! Come on! Lets correlate

  1. i really appreciate your time and effort to explain the basic details of gps. i have a question.

    you wrote: (where ‘1’ indicates a positive value, and ‘0’ indicates a negative value)
    and also: subtract the ‘1’s count from the ‘0’s count

    i think it should be reversed: 1 negative 0 positive. can you please provide more details if i misunderstood?

    Like

    • Hi Roman,

      After thinking it through, I am pretty sure that you are correct. I’ll update my source code.

      However, the decoding is pretty insensitive to this, as absolute phase is not important and inverting the sine and cosine values ends up giving a 180 degree phase shift, that disappears when the BPSK data is decoded.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s