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.

IterationOutputShift register state
00111011011000011001000100110
11011101101100001100100010011
21101010011111001100110110101
30110001100110101100111100110
41011000110011010110011110011
51101000110000100001101000101
60110000110001011010010011110
71011000011000101101001001111
81101000100101011100000011011
91110000111011100100100110001
100111100110100111000110100100
110011110011010011100011010010
121001111001101001110001101001
130100011001111101101100001000
140010001100111110110110000100
150001000110011111011011000010
161000100011001111101101100001
170100110100101110100010001100
180010011010010111010001000110
191001001101001011101000100011
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!

Advertisement
%d bloggers like this: