Speaking satellite: The Galois LFSR


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_j[k]=S_{j-1}[k-1]\oplus a_j \cdot y[k-1], j>0


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.


giving rise to an array of polynomial coefficients:


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
The first 20 shift registration states returned by the Galois encoding algorithm for the L2:CM signal.


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!

%d bloggers like this: