Speaking satellite: Linear Feedback Shift Registers (LFSR)

Introduction

Linear Feedback Shift Register (LFSR) algorithms are an elegant solution in communication between satellites and their terrestrial receivers. Given the limited bandwidth of the receiver and transmitter systems, codes transmitted between the systems are often in done a binary stream of zeros and ones.

Practically speaking, a single receiver needs to be able to capture a large number of streams from an equally large number of transmitters. To accomplish this, it’s imperative that the signal from one transmitting satellite will not be confused with the signal from a second transmitting satellite. But how is this accomplished? In a word, orthogonality.

The orthogonality of a signal is significant because it allows high auto-correlation of a known receiver code with the code transmitted from one satellite, while providing a low auto-correlation between the same receiver code with a second satellite. Consequently, orthogonality increases with the statistical randomness of the transmitted binary stream. But how do you ensure that a code seems statistically random, while also controlling its output so each variable within the system is known? This is where LFSRs come in.

Linear Feedback Shift Registers (LFSR)

Linear feedback shift registers (LFSR) is a way to generate a string of zeros or ones with near-random distribution, but doing so in a controlled and methodical manner. In a nutshell, LFSRs begin with one or two binary strings of digits. Each iteration, the value of every position within the LFSR changes based on a very simple set of rules. The output of each generation is a single value — the very last digit in the updated LFSR sequence.

Although there are numerous techniques that may be applied to LFSRs, satellite systems tend to use two methods in particular: the Fibonacci technique and the Galois technique. Since both techniques are applicable to the same problem, it is possible to convert one technique to the other, but that conversion is not done here.

Anatomy of an LFSR

Shown above is a graphical layout for the Fibonacci LFSR. $S_0$ , $S_1$ , etc. represent the values of the shift register at index 0, 1, etc. In the first generation, the user is handed three items: (1) a set of initial values for $S_0$ through $S_4$ , (2) a mod-2 polynomial, for example f(x)=x⁴+x²+1, and (3) and initial value for $u$ .

The coefficients of the polynomial are known as the “taps”. Since the whole polynomial would be f(x)=1x⁴+0x³+1x²+0x¹+1x⁰, our taps are placed on the $S_4$ and $S_2$ blocks.

Taking it for a test spin

The rules to the Fibonacci sequence are simple…

Start by writing out the initial sequence of values
Record the output value — this is the last value in our binary string
Begin calculating the next generation
- Insert the previous generation’s value of $u$ into the first slot
- Move each number one place to the right ( $S_0$ replaces $S_1$ , $S_1$ replaces $S_2$ , etc.)
- Calculate the new $u$ value by XOR‘ing values at each of the tap locations
- Record $u$ for use in the next generation

So far so good! Let’s take this for a spin. Here’s what we’re handed:

Initial values for $S_k$ : 1, 0, 0, 0, 0
A mod-2 polynomial: f(x)=x⁴+x²+1
Initial value for $u$ : 0

Generation 0:

Our first generation ( $k=1$ ) is: 1, 0, 0, 0, 0 with $u$ = 0. Our output is the last digit of the sequence, 0.

Generation 1:

Each value in the sequence is replaced with the value before it, except for $S_0$ , which is replaced by $u$ . This produces 0, 1, 0, 0, 0, where the red values are used in the following step: calculating $u$ by XOR‘ing $S_2$ and $S_4$ , or 0 XOR 0 = 0.

At this point, we’ve completed one iteration by finding our current bit string (0,1,0,0,0), it’s output value (0) and our value for $u$ (0)., producing $u=0$ .

Generations 0-5:

If we continue repeating these steps for each subsequent iteration, generations 2-6 will be given as follows:

k	u	Bit string	y
0	0	1 0 0 0 0	0
1	0	0 1 0 0 0	0
2	1	0 0 1 0 0	0
3	0	1 0 0 1 0	0
4	1	0 1 0 0 1	1
5	1	1 0 1 0 0	0

Generations 0 through 5 are shown for a simple Fibonacci LFSR implementation.

Conclusion

Although the output values (y) do not appear to be random in nature, keep in mind this is only iterated over 6 generations so far. The outcome, however, is that we are able to generate zeros or ones each generation without having to apply a “random” function to obtain them! If constructed into a computer algorithm, the computation time for some random generation (ex. $k=547$ ) is minimal, but the outcome is complete predictable from a minimal set of rules and input values!

In conventional LSFR algorithms for the L1:C/A satellites in orbit today, the bit string is much longer, and actually includes a second bit string, defined by which satellite in the L1:C/A constellation you’re looking at communicating with!

As usual, thank you for joining me in exploring this fascinating topic, I look forward to digging in deeper next time! Below, please feel free to visit my home page, return to the full article list, or buy me a coffee if you enjoyed this!

Home page

Full article list

Fuel me

Aaron J. Pung, Ph.D.