Introduction
Along with the Fibonacci Linear Feedback Shift Register (LFSR) algorithm, a Galoisbased 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 ISGPS200 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 Galoisbased 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[k1] [/math]
[math] S_j[k]=S_{j1}[k1]\oplus a_j \cdot y[k1], j>0 [/math]
[math] y[k]=S_{N1}[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[k1] [/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 IIRM 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[k1] [/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_{j1}[k1]\oplus a_jy[k1] [/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[k1] [/math] becomes 0, since [math] y[k1]=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_{j1}[k1] [/math]) and zero. Alternatively, when the output value of the previous iteration ([math] y[k1]=0 [/math]) is one, the current position value of this iteration’s shift register is the logical XOR
of [math] S_{j1}[k1] [/math] and the current index within the coefficient vector, [math] a_j [/math], since [math] a_j \cdot y[k1] [/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 IIRM, IIF, and subsequent satellite blocks with PRN=10
.
Iteration

Output

Shift register state

0

0

111011011000011001000100110

1

1

011101101100001100100010011

2

1

101010011111001100110110101

3

0

110001100110101100111100110

4

1

011000110011010110011110011

5

1

101000110000100001101000101

6

0

110000110001011010010011110

7

1

011000011000101101001001111

8

1

101000100101011100000011011

9

1

110000111011100100100110001

10

0

111100110100111000110100100

11

0

011110011010011100011010010

12

1

001111001101001110001101001

13

0

100011001111101101100001000

14

0

010001100111110110110000100

15

0

001000110011111011011000010

16

1

000100011001111101101100001

17

0

100110100101110100010001100

18

0

010011010010111010001000110

19

1

001001101001011101000100011
