Omni Calculator logo

LFSR Calculator

Created by Davide Borchia
Reviewed by Anna Szczepanek, PhD and Rijk de Wet
Last updated: Jan 18, 2024


Generating random numbers on a deterministic machine like a computer is complicated — this is where linear-feedback shift registers (LFSR) come in handy, and you can try them out with our LFSR calculator. With a little bit of math and some computer science knowledge, you will learn everything you need about this special type of register.

Here we will guide you through the many questions you might have, like:

  • What an LFSR is;
  • Fibonacci LFSR vs Galois LFSR;
  • How an LFSR works;
  • The applications of linear-feedback shift registers; and
  • How to use our LFSR calculator.

What is an LFSR?

First: what is a shift register? It's a type of electronic logic circuit that stores and transmits data by moving one bit in a particular direction of a register at every step: a basic type of computer memory. We already have a bit shift calculator that talks about this principle — go check it out!

Shift register
A simple representation of a shift register.

Long story short, a shift register is a series of flip-flops connected in a sequential fashion. Every flip-flop corresponds to a bit of memory (they are at the base of every digital memory in use today). In a shift register, the output of each flip-flop is the input of the next one. There are various types of shift registers — the type most commonly used sees the output bit of the register being also the input bit of the next cycle. This is the basis of digital memories.

If you ask a computer scientist what a flip-flop is, they likely won't tell you "a type of summer shoes" — not because they don't spend time outside, but because computer memory is based on an element with the same name. A flip-flop is a circuit with two stable states (bistable): if we call them 1 and 0, it is straightforward to see why they are so valuable for computing. It consists of an input, a pair of complementary outputs (if one of them outputs 1, the other one outputs 0) and a reset. Flip-flops can store one bit of memory, either outputting 0 (low) or 1 (high). When triggered by the input, the circuit switches to the high state until a signal from the reset moves it back to the low state.

If the input bit (the bit entering the register) of the current state of the shift register is the result of some linear operation of the previous state, then we have a linear-feedback shift register or LFSR.

The logic gates XOR (exclusive or) and NXOR (its negation) are the two linear functions used in LFSR: one is the one's complement of the other, meaning that the math underlying is almost the same.

logic gates for LFSR
The XOR (left) and NXOR (right) logic gates.

Here is the truth table for the XOR gate. As you can see, it corresponds to calcualte the bitwise binary addition operation (modulo 2 addition) — this will make things easier to understand for sure.

If you want to learn more about binary operations, check our related calculators! They are not strictly bitwise, so that the output can be different than just 1 and 0, but also 10, 11, etc... Try the binary addition calculator or its sibling, the binary subtraction calculator.

Input 1

Input 2

Output

0

0

0

0

1

1

1

0

1

1

1

0

🔎 When referring to linear operations, we mean a transformation of a vector space onto itself. The operation XOR, for example, takes as input two "vectors" spanning the discrete values 1 and 0, giving another vector in the same space as a result.

To define an LFSR, it is necessary to specify the bits used as arguments in the linear operation: their positions are called taps. In mathematical terms, they correspond to a vector of 0s and 1s, with 1s in the positions of the desired taps.

The register's initial state is called seed, and it highly affects the outcome of the operations of the LFSR.

The output of an LFSR is a sequence of bits (0s or 1s) that are "collected" at the end of the register. The sequence depends on the chosen function and the type of LFSR, but it always obeys specific rules.

It is periodic (unless the register collapses into the null vector, which consistently transforms to itself) with a maximum number of steps to return to the initial configuration equal to 2n12^n-1, where nn is the length of the register. This number is called the period of the LFSR.

As said before, if the sequence collapses in the null vector, there it remains with trivial periodicity. In that case, the register is not considered an LFSR, and 0,0,...,00,0,...,0 is not allowed as a seed.

Fibonacci LFSR and Galois LFSR: a compendium

There are two main types of LFSR:

  • Fibonacci LFSR; and
  • Galois LFSR.

Each of them is defined using the same set of objects, but they differ in how such objects are used.

Fibonacci LFSR

In the case of the Fibonacci LFSR, the value of the bits specified by the taps is summed using XOR operations, resulting in a final value that then becomes the new input of the shift register. On the "opposite side" of the register, the last bit becomes part of the output.

🔎 Fibonacci is a well-known name in mathematics — and not only there! Check out our Fibonacci sequence calculator to learn more!

In mathematical terms, we can use a set of two formulas to describe the behavior of a Fibonacci LFSR. Let's introduce the symbols in the formulas: X=[X1,...,Xn]\vec{X} = [X_1, ..., X_n] is the shift register itself. It is a vector with elements Xi{0,1}X_{i} \in \{0, 1\} (i.e., either 11 or 00).

The taps are specified by the vector of the connection coefficients, noted as c=[c1,...,cn]\vec{c} = [c_1, ..., c_n]. Both of these vectors have length nn. We defining the element-wise product of the register and the connection coefficient vectors as Y\vec{Y} with elements Yi=ciXi(t)Y_i=c_i X_i(t). The register at the LFSR obeys the rules:

Xi(t+1)=Xi1(t)  for 2inX1(t+1)=Y1(t)...Yn(t)\footnotesize X_{i}(t+1) = X_{i-1}(t)\ \ \text{for}\ 2\leq i\leq n \\ \footnotesize X_{1}(t+1) = Y_1(t)\oplus ... \oplus Y_n(t)

Where \oplus is the XOR operation or binary addition.

As you can see, we shift the register in the first equation, "ejecting" XnX_{n} at the time tt, thus creating the X\vec{X} vector at the t+1t+1 state, with an empty space in the first position.

The second equation is how we build that first element: a binary addition of all the elements of X\vec{X} at the time tt, multiplied by the corresponding connection coefficients, that are equal to 11 only in correspondence of the taps.

Fibonacci Linear-Feedback Shift Register
A Fibonacci linear-feedback shift register. The taps are marked with a striped background.

To "start" the register, we need to feed it a seed, an initial value on which we first apply the rules of the LFSR. The same holds for a Galois LFSR, but the operating principle differs. Let's take a look!

Galois LFSR

In a Galois linear-feedback shift register, we first have to shift every bit that is not a tap to the right. This causes the rightmost bit to be "ejected" and moved to the input.

But this is not all for the output bit. It is also added to each tap before the result moves to the space to the right.

Galois LFSR
Example of a Galois Linear-Feedback Shift Register.

This causes the register to shift unchanged if the output bit is 00, taking as new input 00, while in the case of output bit 11, the tap bits switch, then the register moves to the right. In this case, the input bit is 11.

The two types of LFSR produce the same result — minus a reflection and a translation — when the taps are the ones generating a maximally long LFSR. In such a register, all possible states are visited — except the null state, which would make the register collapse in a sequence of 0s. The seed choice is not relevant since it would introduce only a shift in the output.

In order to obtain this kind of coupled outputs, the taps of the Galois register must be the counterparts of the ones of the Fibonacci register. We mean that if the taps of the latter are

1,4,6,121,4,6,12

which translates to

1,0,0,1,0,1,0,0,0,0,0,11,0,0,1,0,1,0,0,0,0,0,1,

then the taps we need to use are

1,7,9,121,7,9,12

for a Galois LFSR. The transformation is clear when we look at the corresponding vector:

1,0,0,0,0,0,1,0,1,0,0,11,0,0,0,0,0,1,0,1,0,0,1

Examples of the use of Linear-Feedback Shift Registers

Let's see an example of a linear-feedback shift register in action.

First, consider a Fibonacci type. The initial state is 10011001, while the taps are 11011101. Here we mark both output and taps on the initial state:

1001110\textcolor{lightgray}{0}\underline{1} \textcolor{red}{\rightarrow 1}

Now we need to add modulo 2 the "tapped" bits. 101=01\oplus 0\oplus 1=0, and thus the new input bit is 00:

0100001\textcolor{lightgray}{0}\underline{0} \textcolor{red}{\rightarrow 0}

And repeat these operations!

1010 01101 11110 00111 10011 110\textcolor{lightgray}{1}\underline{0}\textcolor{red}{\rightarrow\ 0} \\ 11\textcolor{lightgray}{0}\underline{1}\textcolor{red}{\rightarrow\ 1} \\ 11\textcolor{lightgray}{1}\underline{0}\textcolor{red}{\rightarrow\ 0} \\ 01\textcolor{lightgray}{1}\underline{1}\textcolor{red}{\rightarrow\ 1} \\ 00\textcolor{lightgray}{1}\underline{1}\textcolor{red}{\rightarrow\ 1}

Now take a break: the next state of the register would be 10011001, which is equal to the initial state: from now on, the states would repeat, cycling indefinitely.

The sequence we found is 10010111001011, with period 7. It would expand this way: 10010111001011100...10010111001011100...

animated fibonacci lfsr
Animation of the working principle of a Fibonacci type LFSR. The segments turn red when they are "1".

Do you want to try the same example but with Galois LFSR? We got your back!
Remember: initial state 10011001, taps 11011101.

The first output would be 11: it means we are in for a change. Let's see how the register behaves at the next step.

1001  110\textcolor{lightgray}{0}\underline{1}\ \textcolor{red}{\rightarrow\ 1}

The second step has 00 as output. No changes in the register, just a shift:

1010  010\textcolor{lightgray}{1}\underline{0}\ \textcolor{red}{\rightarrow\ 0}

Repeat those steps, and let's see what happens.

0101  11100  00110  00011  11111  101\textcolor{lightgray}{0}\underline{1}\ \textcolor{red}{\rightarrow\ 1} \\ 11\textcolor{lightgray}{0}\underline{0}\ \textcolor{red}{\rightarrow\ 0} \\ 01\textcolor{lightgray}{1}\underline{0}\ \textcolor{red}{\rightarrow\ 0} \\ 00\textcolor{lightgray}{1}\underline{1}\ \textcolor{red}{\rightarrow\ 1} \\ 11\textcolor{lightgray}{1}\underline{1}\ \textcolor{red}{\rightarrow\ 1}

Stop! See the last state? It's the same as the initial state, so we reached the end. This is another period 7 register, with output 10100111010011.

animated galois lfsr
Animation of a Galois LFSR in operation.

How to use our LFSR calculator?

You can use our LFSR calculator to find out many things about a selected LFSR. Here we will guide you through it!

First, you have to insert the seed and the taps. Make sure that they have the same length.

Then, choose the type of LFSR you want to use for your register: either Fibonacci or Galois. Choose the desired kind of output too:

  • Output: this will show you the sequences of output bits. To make it easier to read, we separated the string into groups of 8 bits.
  • Steps: the calculator will give you the detailed iterations of the register.
  • Period: you will only get the number of steps repeated in the output.

The last field allows you to specify the desired length of the output/steps you need, but it won't affect the period calculation. If that value is undefined, the calculator will cut the sequence at the end of the first period.

💡 We added the possibility of computing the LFSR using the NXOR gate too! Click on advanced mode and select NXOR: the linear operation applied to the register will change accordingly.

While using our LFSR calculator, you may encounter messages that help you understand the behavior of the register you are using.

For example, if you inserted the correct set of taps, you may find a maximally long LFSR, which means that the period of the LFSR is maximum (equal to 2n12^n-1, where nn is the length of the register). We will tell you when you are doing so, since they are particularly interesting. You can find tables with the taps for such sequences online, like in this file: these "special taps" correspond to the exponents of characteristic polynomials. Place the tap in the position marked by the exponent (if you see xx, place a 11 in the first position).

If you accidentally end up with a null register, we will stop the calculator and let you know. Change your numbers and try again.

⚠️ The length of the output of an LFSR can grow pretty quickly: the maximal length of a 16 bit register is 65535. Even if our calculator can compute such a long sequence, it would take time: that's why we added a "dangerous calculations" choice in the advanced mode. The default is no, and it stops calculations at 10,000 steps. Are you bold or particularly curious? Select yes and be patient!

Just for fun, let's try it with a mirroring output. Choose a maximally length taps sequence, like 0100101001, and a random seed, 1101111011. Insert them in our LFSR calculator.

Select "Fibonacci" and "output": the result is

11011000 11111001 10100100 001010111011000\ 11111001\ 10100100\ 0010101

Now switch to "Galois":

11000110 11101010 00010010 110011111000110\ 11101010\ 00010010\ 1100111

We need to reverse it — let us do that for you!

11100110 10010000 10101110 110001111100110\ 10010000\ 10101110\ 1100011

Now let's find the correct shift. Maybe look for a group of clustered 11s or 00s, like...

11011000 11111001 10100100 001010111011000\ \textcolor{red}{11111}001\ 10100100\ 0010101

In the Galois output, the same cluster is broken between the end and the beginning of the sequence:

11100110 10010000 10101110 1100011\textcolor{red}{111}00110\ 10010000\ 10101110\ 11000\textcolor{red}{11}

Shifting the Galois output ten times to the right, we would find the same output of the Fibonacci LFSR.

🔎 Our LFSR generator allows you to use both the Galois and the Fibonacci type. However, the Fibonacci one is the most commonly used: that's why we set it as default!

Conclusions

Now you should know what a LFSR is and how a LFSR works.

LFSR, shift registers, and flip-flops are all parts of a computer we never see, yet they allow for such a complex machine to function as we know it. Go to our Hamming codes calculator if you want to learn more about how computers work behind the keyboard and monitor!

Try our LFSR calculator in all the possible ways and discover which sequences are the longest or which taps give the maximally long outputs!

FAQ

What is a LFSR?

LFSRs are shift registers that apply linear operations to their bits according to a certain set of rules. There are two types of LFSRs: Galois and Fibonacci. They differ in the way they perform the operation.

What are the uses of LFSR?

LFSR are used in cryptography to generate pseudo-random numbers and in circuit testing to create sequences containing all possible inputs for a given n-bit register. The (almost) random nature of the output of an LFSR allows the simulation of noise in signals and helps overcome interference in signal transmissions.

What are the taps of an LFSR?

The taps of a linear-feedback shift register are the bits that are effectively used in the linear operation. They can be specified as a binary vector. In some instances, they correspond to a maximal-length LFSR, a sequence of all the possible states of the register.

What is a pseudo-random number generator?

Computers are intrinsically deterministic (only when a physical phenomenon acts on them, it is possible to have a non-deterministic behavior): this makes it difficult to generate truly random numbers on them. Mathematicians developed algorithms that generate sequences of numbers that resemble their random counterparts but are entirely defined by an initial value: the seed.

How do I calculate a Fibonacci LFSR?

In order to calculate a Fibonacci LFSR, add the bits in the register marked by the connection coefficients, modulus 2, and consider the result as new input in the register. The last value exits as an element of the output.

How do I calculate a Galois LFSR?

In a Galois LFSR, shift every bit to the right if the output bit is zero, and use 0 as new input bit too. If the output bit is 1, all of the bits are shifted to the right, but the ones marked by the taps must switch from 1 to 0 and vice-versa. In this case, the next input is 1.

Davide Borchia
Initial state (seed)
Connection coefficients
LFSR type
Fibonacci
Type of output
Output
Number of digits in the output/steps
Check out 659 similar math calculators
2D distance30 60 90 triangle3 sides triangle area… 656 more
People also viewed…

Central angle

The central angle calculator finds the angle at the center of a circle whose legs (radii) extend towards an arc along the circumference. Using two of the three parameters (central angle, radius, or arc length), find the third!

Coffee kick

A long night of studying? Or maybe you're on a deadline? The coffee kick calculator will tell you when and how much caffeine you need to stay alert after not sleeping enough 😀☕ Check out the graph below!

Greatest common denominator

Quickly calculate the greatest common denominator of a group of numbers with our handy tool!

Snowman

The perfect snowman calculator uses math & science rules to help you design the snowman of your dreams!
Copyright by Omni Calculator sp. z o.o.
Privacy, Cookies & Terms of Service