1
$\begingroup$

Are the actual 1023 bit sequences for each of the 32 GPS satellites available to consumers? I found the IS GPS 200 but it doesn't list the entire sequences. Are verified sequences available for download anywhere online?

I'm trying to validate my python CA PRN generator. Also, what does the last footnote (**** The two-tap coder utilized here is only an example implementation that generates a limited set of valid C/A codes.) mean? Which codes is it valid for?

enter image description here

$\endgroup$
3
$\begingroup$

I have a PRN generator that I have validated with live captured signals that is available on the Mathworks Exchange site at this address and equally runs in Octave (Update: I also pasted the core of this in a code block below):

https://www.mathworks.com/matlabcentral/fileexchange/14670-gps-c-a-code-generator

The two tap coder is as given in the diagram in that spec and copied in the figure below:

GPS C/A Code Generator

What they mean by “two tap coder” is the selection and addition of two outputs of the G2 generator in the diagram and that this is just one way to generate the sequences (a very convenient way). An alternate approach which I have done is to implement the generator with one LFSR. In this case you simply convolve the coefficients for the two generator polynomials. This results in a length 20 shift register and non-maximum length sequence (since it clearly can be factored), and will generate 1023 different sequences each 1023 long, depending on how you seed it. (So if you change the state of the 20 elements with any 20 consecutive chips from a PRN of interest, it will continue to run the code for that SV). So when they mention it will only generate a limited selection of the Gold Codes, they mean it won’t generate all 1023 possible codes (because with the selection of two taps there are only $9!=42$ combinations -if I did that right, and if so then I highly suspect that the selection of which of the 1023 different codes to use was based on the assumption of using this 2-tap generator). The two-tap generator shown won’t generate all possible Gold Codes for these polynomials used but it will indeed generate all the GPS C/A codes.

This is because the Gold Code (which is the GPS C/A code) is formed by adding two maximum length sequences in GF(2) (basically x-or'ing the output). Doing that is identical to what could be done with one generator where the polynomials are multiplied together, and you multiply polynomials by convolving their coefficients.

The advantage of doing that with just one long LFSR would be the creation of a flexible code generator capable of creating any maximum length sequence up to $2^{20}-1$ including all the GPS C/A codes and many other compound codes.

The interesting point about the Gold Code is that if you delay one of the generators relative to the other by even 1 chip, the result will be a completely new 1023 length sequence. So since there are 1023 possible delays, there are 1023 total possible sequences that can be generated, each 1023 long.

Further an interesting point about maximum length sequences in general, is if you GF(2) add the sequence to a delayed version of itself, it will create the exact same sequence just at a completely different delay! Thus you see what is happening in the Gold Code Generator with the "two-tap coder" which is used to select the satellite; in the figure I gave we select taps 2 and 6 resulting in SV1 (which should match the first part of the table that you didn't post). The table you have shows the equivalent delay of the G2 coder for each two tap selection that is made.

Since a login is required for the MathExchange site, here is a copy of my code with the front-end error-trapping removed (for brevity):

function g=cacode(sv,fs)
% function G=CACODE(SV,FS) 
% Generates 1023 length C/A Codes for GPS PRNs 1-37
%
% 
% g: nx1023 matrix- with each PRN in each row with symbols 1 and 0
% sv: a row or column vector of the SV's to be generated
%    valid entries are 1 to 37
% fs: optional number of samples per chip (defaults to 1), fractional samples allowed, must be 1 or greater.
%
% For multiple samples per chip, function is a zero order hold. 
%
%
% For example to generate the C/A codes for PRN 6 and PRN 12 use:
% g=cacode([6 12]),
% and to generate the C/A codes for PRN 6 and PRN 12 at 5 MHz use
% g=cacode([6 12],5/1.023)
% 
%
% Dan Boschen 12-30-2007
% boschen@loglin.com


% table of C/A Code Tap Selection (sets delay for G2 generator)
tap=[2 6;
    3 7;
    4 8;
    5 9;
    1 9;
    2 10;
    1 8;
    2 9;
    3 10;
    2 3;
    3 4;
    5 6;
    6 7;
    7 8;
    8 9;
    9 10;
    1 4;
    2 5;
    3 6;
    4 7;
    5 8;
    6 9;
    1 3;
    4 6;
    5 7;
    6 8;
    7 9;
    8 10;
    1 6;
    2 7;
    3 8;
    4 9
    5 10
    4 10
    1 7
    2 8
    4 10];

% G1 LFSR: x^10+x^3+1
s=[0 0 1 0 0 0 0 0 0 1];
n=length(s);
g1=ones(1,n);   %initialization vector for G1
L=2^n-1;

% G2 LFSR: x^10+x^9+x^8+x^6+x^3+x^2+1
t=[0 1 1 0 0 1 0 1 1 1];
q=ones(1,n);    %initialization vector for G2

% generate C/A Code sequences:
tap_sel=tap(sv,:);
for inc=1:L
    g2(:,inc)=mod(sum(q(tap_sel),2),2);
    g(:,inc)=mod(g1(n)+g2(:,inc),2);
   g1=[mod(sum(g1.*s),2) g1(1:n-1)];
   q=[mod(sum(q.*t),2) q(1:n-1)];
end

%upsample to desired rate
if fs~=1
    %fractional upsampling with zero order hold
    index=0;
    for cnt = 1/fs:1/fs:L
        index=index+1;
        if ceil(cnt) > L   %traps a floating point error in index
            gfs(:,index)=g(:,L);
        else
            gfs(:,index)=g(:,ceil(cnt));
        end
    end 
    g=gfs;
end
$\endgroup$
  • $\begingroup$ What does 'GF(2)' mean? What does the 'code delay chips' in table 3-I mean? $\endgroup$ – Seth Oct 24 '18 at 2:49
  • $\begingroup$ GF(2) is a Galois Field with two elements. It just simply defines the math you would get by using an Xor gate to do the additions shown. The delay is what I mentioned in the test if you implemented the Gold Code by GF(2) adding the two generator outputs by first delaying the G2 generator before adding; each output is 1 chip and the code itself is 1023 chips long $\endgroup$ – Dan Boschen Oct 24 '18 at 2:53
  • $\begingroup$ So for example is you take the two generators and delay one by one chip and then add the two, you will get a code sequence out. If you then added even just one more delay of one additional chip- you would get a completely different code out. Summing the two taps out of G2 like they do has the same effect as delaying that generator that number of taps as they give in the table (much simpler than actually having a long delay) $\endgroup$ – Dan Boschen Oct 24 '18 at 2:56
  • $\begingroup$ So you could decide to use their two tap approach to synthesize that amount of delay needed, or physically actually delay G2 relative to G1 before GF2 adding fhem (as adding a generator output to a delayed version of that same generator results in an output that is the same sequence at even yet another delay so their approach with the two-taps is a simple and elegant way to accomplish this. $\endgroup$ – Dan Boschen Oct 24 '18 at 3:03
  • $\begingroup$ Do you happen to have a python implementation? $\endgroup$ – Seth Oct 24 '18 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.