Speaking satellite: The 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.

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

The first 20 shift registration states returned by the Galois encoding algorithm for the L2:CM signal.

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!

Home page

Full article list

Fuel me

Aaron J. Pung, Ph.D.