Saved

Press the star next to a tool's name to save it.

All my tools

Linear Feedback Shift Register Calculator

Use this LFSR calculator to run a linear-feedback shift register in Fibonacci or Galois form and see the output bits, the first states, the period and whether it is maximal.

Restored your last values ·

Enter the length n, the taps as bit numbers separated by commas (bit n is always a tap), and a seed that is not zero. Pick the Fibonacci or the Galois form. The calculator runs the register, shows the output bits and the first states, and finds the period for registers up to 20 bits.

Everything is worked out in your browser. Nothing you type is sent anywhere.

–

–

Enter the register length, the taps and a seed, then press Run.

An LFSR calculator runs a linear-feedback shift register: a row of bits that shifts one place at every step, with a new bit made by adding some of the bits together. Enter the register length, the taps and a seed, and press the button. The calculator shows the output bits, the feedback polynomial, the first states, and for registers up to 20 bits it finds the period and tells you whether it is the maximal length of 2ⁿ − 1. The forms follow the Wikipedia page on linear-feedback shift registers, and the work is done in your browser. This is a linear feedback shift register calculator for both the Fibonacci and the Galois form.

How to use the LFSR calculator

  1. Enter the register length n.
  2. Enter the taps as bit numbers, including n, for example 4, 3.
  3. Enter a seed that is not zero, and choose the form.
  4. Press Run.

How the Fibonacci form works

The page describes the Fibonacci LFSR: the bits at the tap positions are added modulo 2, which is the XOR operation, the register shifts one place to the right, and the XOR result enters at the left end. The bit that leaves at the right end is the output. The page's example is a 16-bit register with taps at bits 16, 14, 13 and 11, which corresponds to the feedback polynomial x¹⁶ + x¹⁴ + x¹³ + x¹¹ + 1. The calculator numbers the bits from the left, so bit 16 is the rightmost one, the output. For a 3-bit register with taps 3 and 2, the polynomial is x³ + x² + 1. Starting from 001, the output bits are 1, 0, 0, 1, 0, 1, 1, and then the sequence repeats, after 7 steps.

How the Galois form works

In the Galois form, the bits that are not taps just shift to the right. When the output bit is 1, the bits at the tap positions are flipped, which is the same as XORing them with the output bit. The page gives the mask 0xB400 for the 16-bit example, and the calculator uses the same mask. The Galois and Fibonacci forms with the same polynomial produce sequences of the same period, but the sequences and states differ. The Galois form needs fewer operations in each step in a computer program, which is why it is often used.

The period and maximal length

An n-bit register has 2ⁿ − 1 non-zero states, so its sequence must repeat after at most that many steps. The page explains that the register has the maximal length, a period of exactly 2ⁿ − 1 steps, if and only if its feedback polynomial is primitive over the field with two elements. A necessary condition is an even number of taps, counting the term of power 0. The page's table lists a few: x³ + x² + 1 with period 7; x⁴ + x³ + 1 with period 15; x⁸ + x⁶ + x⁵ + x⁴ + 1 with period 255; x¹⁶ + x¹⁵ + x¹³ + x⁴ + 1 with period 65,535; and x²⁴ + x²³ + x²² + x¹⁷ + 1 with period 16,777,215. The calculator counts the steps until the register returns to the seed. It confirms the periods 7, 15, 255 and 65,535 for the first four, and also 65,535 for the 16-bit polynomial of the page's Fibonacci example.

Choosing taps

Not every set of taps gives a long period. A register of 4 bits with taps 4 and 2 has a period of only 6, and the calculator reports that it is not maximal. If you need a maximal-length sequence, start from a known primitive polynomial such as those in the table above. The page also notes that mirroring the taps gives another polynomial of the same period.

Using an LFSR

An LFSR is a very cheap way to make a long repeating sequence of bits that looks random, and it needs only a row of bits and a few XOR operations. Because the feedback is linear, the sequence can be predicted from a short stretch of its output, so a single LFSR should not be used where an attacker could gain from guessing the next bit. Use this calculator to study the sequences, to check a choice of taps, or to test an implementation against the expected output.

An example run

Take a 4-bit register with taps 4 and 3 and the seed 0001. In the Fibonacci form, the output bits are 100010011010111 and then the cycle repeats, so the period is 15, which is 2⁴ − 1, and the register is maximal. With taps 4 and 2 instead, the output is 100010100010 and the period is only 6, so the register is not maximal. Entering both in the calculator shows the difference at once and is a good way to see why the choice of taps matters.

Typing tips

Separate the taps with commas. A seed in binary can have leading zeros, which show the register length, and a seed in hex or decimal is converted to n bits.

Common mistakes

  • Using a seed of zero. The register stays at zero forever.
  • Leaving out the tap at bit n. The tap at n is always needed.
  • Counting the bits from the other end. Here bit 1 is the leftmost.
  • Assuming any taps give the maximal period. Only primitive polynomials do.
  • Using an LFSR as a secure random source. It is predictable.

What next

Use this often? Add Linear Feedb to your Home screen.

Frequently asked questions

What is an LFSR calculator?

A tool that runs a linear-feedback shift register and shows its output bits, states and period.

What is a maximal-length LFSR?

One whose sequence has the period 2ⁿ − 1, which happens exactly when its feedback polynomial is primitive. For n = 4, x⁴ + x³ + 1 has period 15.

What is the difference between Fibonacci and Galois LFSRs?

The Fibonacci form XORs the tap bits to make the new bit. The Galois form XORs the output bit into the tap positions.

What happens with a seed of zero?

The register stays at zero forever, so the seed must not be zero.

Are LFSRs secure random generators?

No. The feedback can be worked out from a short stretch of the output, so they are only used as building blocks.

What went wrong?

We only receive the reason you pick, never what you typed into the tool.

Thanks for your feedback.

More Developer Tools