Introduction

   Welcome back! From our last conversation about general Linear Feedback Shift Registers, we mentioned there were two flavors of LFSR algorithms: Fibonacci and Galois. Although we ran through a basic implementation of the Fibonacci technique, we can dive into a lot more detail.

The Fibonacci LFSR

   One of the main points we mentioned in the discussion of the Fibonacci LFSR is that real-world satellite systems like the L1:C/A utilize two shift registers, and each initial bit string is much longer. Let’s walk through some of the changes.

   The first change is that the initial bit string (which we’d previously defined as a simple 5-digit string of 1,0,0,0,0) is 10 characters in length. The second major change is the use of a second bit string; initially defined by choosing a satellite number, the number is then used with a sort of look up table to produce the second 10-digit bit string. The third major change is the use of a much larger polynomial. In our previous case, we only used a mod-2 polynomial 3 terms in length. In real-world applications, the polynomial for L1:C/A bit strings is 27 terms in length, including 12 non-zero coefficients.

Graphical representation

   Graphically, computation of the L1:C/A algorithm can be shown in a space-efficient manner, as illustrated by the graphic below from Kim’s “Area-Efficient Universal Code Generator for Multi-GNSS Receivers“:

   Based on our previous discussion, we can begin to pick apart certain portions of the code generator. For instance, the top gray-background box labeled “Initial ROM1” is the initial bit string we were handed in our previous example. In this case (at least for L1:C/A), this bit string is 10 digits long, consisting of all ones. The second bit string (represented by the gray-background box labeled “Initial ROM2” is also a 10-bit-long string of ones.

Feedback

The numbers above each of these ROM boxes (labeled SR1 and SR2, respectively) detail the feedback taps, providing the non-zero coefficients of the polynomials used with the ROM1 and ROM2 bit strings. The first 10-digit bit string, “Initial ROM1”, always uses a polynomial with non-zero coefficients located at the 3rd and 10th index.

These feedback taps are represented by the two vertical lines coming off of the “3” and “10” box above the “Initial ROM1” gray background. The second 10-digit bit string also has an associated polynomial, defined by indices 2, 3, 6, 8, 9, and 10. Feedback at these indices is illustrated by the nodes coming off of boxes 2, 3, 6, etc.

Output

   In our previous lesson, we saw that each iteration of the LFSR provided us with a single output; in our simplified case, this was simply the last digit of the current LFSR state. In the realistic Fibonacci example, this is still the case, but just like we had one output value for one LFSR, here we will have one output value for each LFSR, resulting in two output values.

   As with our previous example, the output of our first LFSR is simply the last digit of the current LFSR state. For an initial LFSR state of ten ones, the last digit (and therefore our output value) is one. The output value of the second LFSR is a bit more complicated, since it is calculated. Initially, we begin our LFSR problem with two 10-digit shift registers and two known arrays of feedback taps, one for each 10-digit shift register. Unlike our previous example, we’re also provided with a satellite number. The satellite number, in turn, corresponds to a set of output taps; for example, the satellite number “1” corresponds to output taps 2 and 6. Therefore, for. each generation the LFSR is calculated, the output is not simply the last digit of our current LFSR state, but rather the value produced by XOR‘ing the values located at the 2nd and 6th indices, respectively. In the first generation, this value is 1 XOR 1 = 0.

   But we’re not done yet — now we truly have two output values for two LFSRs: (1) the last digit extracted from our first LFSR, and (2) the result of our XOR from the two indices we gathered from our lookup table based on satellite number. To get the final output for a given generation, we have to XOR these two values together. Since the final digit from our first initial shift register is 1 and our output from the second LFSR is 0, our final output for this generation is 1 XOR 0 = 1.

Conclusion

   In closing, the Fibonacci LFSR algorithm is a simple and elegant technique to produce pseudo-randomized binary values while maintaining a very level of predictability, orthogonality, and simplicity. In this tutorial, we expanded on the previous tutorial’s example of a 5-digit Fibonacci LFSR. To me, this technique is considerably more easy to implement compared to the Galois implementation, but both have their merits!