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.
Equations describing the Galois LFSR algorithm are given below for a given iteration :
Here, the represents a particular value of the shift register at position (with indexing starting at zero), is the polynomial coefficient, and is the output value of the previous iteration. Finally, represents the
XOR logic function.
Exemplifying the Galois LFSR algorithm
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 () leading the polynomial simply represents (since ), 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 needs to be reversed.
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 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 .
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 () of the iteration, becomes .
Similarly, the second value, is obtained from the previous equation set. Specifically, becomes
XOR . This process is repeated until all 27 digits of the shift register have been updated. Lastly, the new output value 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 becomes 0, since and any number multiplied by zero is zero. Therefore, the current shift register value is simply the logical
XOR of the value () and zero. Alternatively, when the output value of the previous iteration () is one, the current position value of this iteration’s shift register is the logical
XOR of and the current index within the coefficient vector, , since is simply .
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
|Iteration||Output||Shift register state|
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!