The GPS PRN (Gold Codes)
First read the previous post about the basics of GPS encoding.
PRN (“Psuedo Random Noise”) sequences are used as part of the CDMA scheme in GPS. But they don’t just use any random number. In fact, it’s not random, it’s a kind of pseudo-random number. One of the reasons you want a spreading code that looks random is to ensure you have good autocorrelation properties. It also helps the spreading properties.
A signal that’s statistically random doesn’t repeat itself at any point in its sequence and so it has very good autocorrelation properties. We also want the different codes for each satellite that are nearly orthogonal so the cross correlation of one code will be very high even when many satellite codes are mixed in. This is the scheme used to create pseudo-random sequences with all these properties for GPS:
The Gold Codes are generated using a pair of shift registers with feedback. Let’s make a software emulation of a shift register in python! A shift register is just a list of bits that has an input end and an output end. The GPS registers are length 10. We’ll start them out with all 1’s, calculate the feedback, and then shift all the numbers over to the right. Taking it step by step:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Now we take feedback from a couple of positions in the register and modulo 2 add them together. Specifically for GPS, the first shift register (G1) is defined to have feedback from positions 3 and 10 (note the 1 indexing):
Now we have the number to push back into the fist position. Let’s “clock” the shift register and put the feedback in:
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Neat! Now just keep going…
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
Etc., etc., etc. Lets put this in a function and clean things up.
1 [0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
Notice we have a place defined to have some output. The shift registers can be tapped at different locations to define an output. These spots are modulo 2 added together to make an output from the register. This function returns that value.
Since we defined this generically we can use it for the other shift register used for the C/A code, G2, which has feedback from positions 2,3,6,8,9, and 10:
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
The C/A Code
The “coarse acquisition” code, or C/A code, in GPS is made of two shift registers, G1 and G2. G1 has feedback from position 3 and 10, and G2 has feedback from 2,3,6,8,9, and 10. The output of each is modulo 2 added to produce the code. To make different satellite codes different spots on the G2 register are tapped.
To produce a bit for PRN #1 we tap position 2 and 6 as the output (according to the GPS spec). We modulo 2 add this to the output of G1 (always position 10).
Lets make the first 10 bits of PRN #1:
[1, 1, 0, 0, 1, 0, 0, 0, 0, 0]
To make things a little clearer, we can draw a diagram of this shift register feedback and output system.
Feedback lines are in blue. Output (in red) from G1 is always from position 10. Different choices for the two G2 outputs are assigned to different satellites. Everything is modulo 2 added. In this example to current C/A output is a 1:
Each satellite is assigned a different 1023 bit long PRN (a Gold Code). This is decided by choosing different spots to tap the G2 shift register. In the above example we are looking at PRN #1, which is defined as being tapped from position 2 and 6. To make PRN #2 we would tap 3 and 7. Here is the list of PRN assignments from the GPS spec:
Final PRN Code
So now we have all the pieces to write our PRN creator! Given the input of satellite number (SV) we can now compute the 1023 bit long chip for that satellite:
And now test with, say, satellite #24:
See previous post and the next post to continue learning about GPS sinals.