Introduction

Along with the Fibonacci Linear Feedback Shift Register (LFSR) algorithm, a Galois-based can also be created. In fact, the Galois algorithm is more computationally efficient than the Fibonacci algorithm, and it is also used in validating the IS-GPS-200 standards.

While building any algorithm, it is always helpful to have values to validate against. With many algorithms, this is easy — the algorithms typically exist in multiple programming languages, and intermediate states can be easily calculated by hand. However, this is not the case with the Galois-based LFSR routine. For this reason, I will cover Galois LFSR algebraic algorithm and the first twenty shift register states.

The Algorithm

Equations describing the Galois LFSR algorithm are given below for a given iteration [math] k [/math]:

[math] i\hbar\frac{\partial}{\partial t}\left|\Psi(t)\right>=H\left|\Psi(t)\right>[/math]

[math] S_0[k] = a_0y[k-1] [/math]

[math] S_j[k]=S_{j-1}[k-1]\oplus a_j \cdot y[k-1], j>0 [/math]

[math] y[k]=S_{N-1}[k] [/math]

Here, the [math] S [/math] represents a particular value of the shift register at position [math] j [/math] (with indexing starting at zero), [math] a_j [/math] is the [math] j^{th} [/math] polynomial coefficient, and [math] y[k-1] [/math] is the output value of the previous iteration. Finally, [math] \oplus [/math] represents the XOR logic function.

The Setup

Consider the Galois LFSR algorithm used for L2 CM phase code assignments of the IIR-M satellite block. The algorithm uses the following polynomial; note that the powers of the polynomial begin indexing at 1. Additionally, the ([math] 1 [/math]) leading the polynomial simply represents [math] x^0 [/math] (since [math] x^0 = 1 [/math]), and does not correspond to a coefficient within the algorithm.

[math] f(x)=1+x^3+x^4+x^5+x^6+x^9+x^{11}+x^{13}+x^{16}+x^{19}+x^{21}+x^{24}+x^{27} [/math]

giving rise to an array of polynomial coefficients:

[math] a=[0,0,1,1,1,1,0,0,1,0,1,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1] [/math]

It should be further noted that this polynomial is valid only for the Fibonacci LFSR algorithm; to properly implement in a Galois LFSR, vector [math] a [/math] needs to be reversed.

For SVD=10 and PRN=10, the initial L2:CM shift register state state is defined as the octal value 733031046. Converting the octal value to binary, an initial state of [math] S[0] = 111011011000011001000100110 [/math] is reached. Since no LFSR algorithms have been applied to the starting state, this also matches the shift register state at iteration 0 in the table below. Also shown in the table is the starting output value, or [math] y[k=0]=0 [/math].

The first iteration

 With the initial shift register state and output value in hand, the second iteration can be constructed. Starting with the first value ([math] S_{j=0} [/math]) of the [math] k=1 [/math] iteration, [math] S_0[k]=a_0 \cdot y[k-1] [/math] becomes [math] S_0[1]= 0 \cdot 0 = 0 [/math].

Similarly, the second value, [math] S_{j=1}[k=1] [/math] is obtained from the previous equation set. Specifically, [math] S_j[k]=S_{j-1}[k-1]\oplus a_jy[k-1] [/math] becomes [math] S_1[1]=S_{0}[0] \oplus 0 \cdot 0 = 1 [/math] XOR [math] (0 \cdot 0) = 1 [/math] XOR [math] 0 = 1 [/math]. This process is repeated until all 27 digits of the shift register have been updated. Lastly, the new output value [math] y[k=1] [/math] is defined as the last value in the newly modified shift register; in this case, that value happens to be 1.

Shift register computation can be further simplified. When the output of the previous iteration is zero, the product [math] a_j \cdot y[k-1] [/math] becomes 0, since [math] y[k-1]=0 [/math] and any number multiplied by zero is zero. Therefore, the current shift register value is simply the logical XOR of the value ([math] S_{j-1}[k-1] [/math]) and zero. Alternatively, when the output value of the previous iteration ([math] y[k-1]=0 [/math]) is one, the current position value of this iteration’s shift register is the logical XOR of [math] S_{j-1}[k-1] [/math] and the current index within the coefficient vector, [math] a_j [/math], since [math] a_j \cdot y[k-1] [/math] is simply [math] a_j [/math].

The first 20 iterations

The table below lists the first 20 shift register states for the L2CM code phase assignments of the IIR-M, IIF, and subsequent satellite blocks with PRN=10.