## Speaking satellite: Galois LFSR

#### 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 $k$:

$S_0[k]=a_0y[k-1]$

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

$y[k]=S_{N-1}[k]$

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

### Exemplifying the Galois LFSR algorithm

#### 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 ($1$) leading the polynomial simply represents $x^0$ (since $x^0 = 1$), and does not correspond to a coefficient within the algorithm.

$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}$

giving rise to an array of polynomial coefficients:

$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]$

It should be further noted that this polynomial is valid only for the Fibonacci LFSR algorithm; to properly implement in a Galois LFSR, vector $a$ 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 $S[0] = 111011011000011001000100110$ 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 $y[k=0]=0$.

#### 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 ($S_{j=0}$) of the $k=1$ iteration, $S_0[k]=a_0 \cdot y[k-1]$ becomes $S_0[1]= 0 \cdot 0 = 0$.

Similarly, the second value, $S_{j=1}[k=1]$ is obtained from the previous equation set. Specifically, $S_j[k]=S_{j-1}[k-1]\oplus a_jy[k-1]$ becomes $S_1[1]=S_{0}[0] \oplus 0 \cdot 0 = 1$ XOR $(0 \cdot 0) = 1$ XOR $0 = 1$. This process is repeated until all 27 digits of the shift register have been updated. Lastly, the new output value $y[k=1]$ 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 $a_j \cdot y[k-1]$ becomes 0, since $y[k-1]=0$ and any number multiplied by zero is zero. Therefore, the current shift register value is simply the logical XOR of the value ($S_{j-1}[k-1]$) and zero. Alternatively, when the output value of the previous iteration ($y[k-1]=0$) is one, the current position value of this iteration’s shift register is the logical XOR of $S_{j-1}[k-1]$ and the current index within the coefficient vector, $a_j$, since $a_j \cdot y[k-1]$ is simply $a_j$.

#### 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.

### Conclusion

In closing, the Galois LFSR algorithm is a beautiful technique to produce pseudo-randomized binary values while maintaining a very level of predictability, orthogonality, and simplicity. I hope this walk-through of the algorithm and the first twenty shift register states have been helpful! Feel free to drop a comment below with a question or other information you would like to see in this section!