LFSR Calculator — step a shift register and read its cycle

The LFSR calculator above runs a linear feedback shift register step by step. You give it a length, a seed and a set of taps; it shifts, computes feedback, and emits one bit per step. It also runs the register until it returns to its starting state so it can tell you the cycle length and whether that cycle is the longest the register can achieve.

This is a teaching tool and Arb Digital says so plainly. Linear feedback shift registers are excellent for explaining sequence generation, test patterns and the arithmetic behind cyclic codes, and they are catastrophic as a source of unpredictable numbers. That second point is not a caveat tucked away at the bottom of the page, it is one of the two things the page is for.

What This LFSR Calculator Does

A shift register holds a fixed number of bits. On each step every bit moves one place along, one bit falls off the end and becomes the output, and a new bit is shifted in at the other end. What makes it a feedback register is that the new bit is computed from the current contents rather than supplied from outside, and what makes it linear is that the computation is an exclusive-or of selected stages, which is addition in the field of two elements.

The tool implements both standard arrangements. In the Fibonacci form the feedback is computed outside the register by exclusive-oring the tapped stages together and shifting the single result in at the front. In the Galois form the output bit is exclusive-ored into several stages as it shifts, which puts the same amount of work in parallel rather than in a chain. The two produce the same set of cycle lengths for the same polynomial, but not the same bit order, which surprises people who expect them to be interchangeable.

Alongside the output stream, the tool walks the whole cycle from your seed and reports how many distinct states it visits before repeating. Comparing that against the theoretical maximum tells you immediately whether your tap choice gives a maximal length sequence or one of the short cycles that a badly chosen polynomial produces.

How to Use It

1. Set the register length first. The seed and the tap positions are both interpreted against it, so changing the length afterwards reinterprets everything.
2. Give a seed containing at least one 1. An all-zero register feeds itself zeros forever and never leaves that state, which the tool reports rather than showing a blank stream.
3. Enter the taps as stage numbers. Position 4 and position 3 on a four-bit register means the polynomial x⁴ + x³ + 1, and the highest tap should normally equal the register length.
4. Choose Fibonacci or Galois. Both are correct implementations, and both are used in real hardware; they simply order the output bits differently.
5. Read the cycle length before the stream. A short cycle means the taps are wrong for the length, and no amount of reading the bits will make that obvious on its own.

The Formula: How Each Step Is Computed

Label the stages 1 to n from the left. In the Fibonacci arrangement, the output on each step is the contents of stage n. The feedback bit is the exclusive-or of every tapped stage. The new state is the feedback bit followed by the old stages 1 through n−1.

Work the default and it becomes concrete. The register is four bits, the seed is 1001 and the taps are stages 4 and 3, which is the polynomial x⁴ + x³ + 1. Step one outputs the rightmost bit, a 1, and the feedback is 1 exclusive-or 0, which is 1, so the register becomes 1100. Step two outputs 0 and feeds back 0, giving 0110. Step three outputs 0 and feeds back 1, giving 1011. Continuing, the register visits fifteen distinct non-zero states and then returns to 1001, so the cycle length is fifteen. That is 2⁴ − 1, the maximum for a four-bit register, so this tap choice gives a maximal length sequence. The first fifteen output bits are 100110101111000, containing eight ones and seven zeros.

That eight-to-seven split is not a coincidence. In any maximal length sequence the number of ones exceeds the number of zeros by exactly one over a full period, because the all-zero state is the single state the register can never visit. The tool reports the count so you can check the property yourself on any polynomial you try.

Why an LFSR Is Not a Random Number Generator

The output of a maximal length register passes a great many statistical tests. The ones and zeros balance, runs occur at the expected frequencies, and the autocorrelation is flat. None of that makes it unpredictable, and the distinction matters enormously.

RFC 4086, Randomness Requirements for Security, addresses this directly. It describes shift-register generators, where bits are introduced as the exclusive-or of bits from selected fixed taps, and states that such generators are fully predictable if the initial state is known, adding that even when only one bit of each pseudo-random value is released the seed can be determined from short sequences. An n-bit register is fully determined by 2n consecutive output bits, recoverable by solving a small linear system, and the Berlekamp-Massey algorithm does exactly that in time proportional to the square of the length.

The related trap is assuming statistical testing settles the question. NIST Special Publication 800-22 Revision 1, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, is explicit that statistical testing cannot serve as a substitute for cryptanalysis. A generator can pass every test in a suite and still be trivially predictable, and an LFSR is the textbook demonstration of that gap. If you need unpredictable values, use your platform's cryptographic random source, and if you only need arbitrary values for a simulation or a draw, the random number generator covers that case.

Where Shift Registers Genuinely Belong

They are excellent at the jobs that need a long, cheap, exactly repeatable sequence. Built-in self-test in silicon uses them to generate pseudo-random test patterns and to compress the responses into a signature, because the pattern must be reproducible on every chip and every test run. Scramblers in communication links use them to break up long runs of identical bits so a receiver's clock recovery keeps working, and the receiver runs the same register to undo it.

Direct-sequence spread spectrum uses maximal length sequences as spreading codes, relying on the flat autocorrelation rather than on any secrecy. Cyclic redundancy checks are shift-register arithmetic too: a CRC is polynomial division carried out by exactly this hardware, which is why the two subjects are always taught together. If you want the error-detection and correction side of that story, the Hamming code calculator and the parity bit calculator approach it from the coding end.

The common thread is that none of these applications needs the sequence to be secret. They need it to be long, balanced, cheap in gates and perfectly reproducible, and an LFSR delivers all four. The failure cases are exactly the applications that quietly assume unpredictability as well.

Choosing Taps, and What Goes Wrong When You Do Not

A register reaches its maximum cycle of 2ⁿ−1 only when its tap set corresponds to a primitive polynomial over the field of two elements. Tap sets that do not are perfectly legal and produce shorter cycles, sometimes dramatically shorter, and frequently different cycle lengths from different seeds.

That last behaviour is the one that causes real confusion. With a maximal polynomial every non-zero seed lands on the same single long cycle, so the seed only chooses your starting point. With a non-maximal one the state space splits into several disjoint cycles, and the sequence you get depends on which cycle your seed happens to sit in. Testing one seed and concluding the register is fine is therefore not a valid test, which is why this tool reports the cycle length for the seed you actually gave it. The short-cycle preset above demonstrates the effect directly.

The number of stages tapped should also be even for a maximal sequence, counting the implicit feedback into stage one, which is a quick sanity check before you trust a tap list copied from somewhere. Beyond that, published tables of primitive polynomials are the practical route; deriving them by hand is real work, and guessing produces short cycles far more often than not.

Common Mistakes to Avoid

• Seeding with all zeros — the register is stuck there permanently, because the exclusive-or of nothing but zeros is zero.
• Using the output as a random source — twice the register length in output bits is enough to recover the state and predict the rest.
• Assuming any tap set gives a long cycle — only primitive polynomials do, and the rest produce short cycles that vary with the seed.
• Testing one seed and declaring success — with a non-maximal polynomial different seeds sit on different cycles of different lengths.
• Expecting Fibonacci and Galois to emit identical bits — they have the same cycle structure and a different output order, so a stream from one will not match the other.

Related Free Tools From Arb Digital

For arbitrary values without any of this machinery, use the random number generator, and for the strength of a secret rather than the shape of a sequence, the password entropy calculator. The bitwise calculator performs the exclusive-or operations behind each step, the number base converter rewrites register states in hex or decimal, and the modulo calculator covers the modular arithmetic these polynomials live in. The Hamming code calculator and parity bit calculator cover error detection, and the text to binary converter turns text into bits you can feed through. More in the free online tools hub.

Frequently Asked Questions

This tool is provided for education only. A linear feedback shift register is not a cryptographic random number generator and must never be used to produce keys, tokens, nonces or any other value whose unpredictability matters. Use a vetted cryptographic random source for those.