Linear Feedback Shift Register (LFSR) Calculator
Free LFSR calculator generates pseudo-random binary sequences with Fibonacci/Galois taps and XOR/NXOR gates. Shows output period, register state transitions, and maximal-length detection for digital logic.
About This Calculator
The Linear Feedback Shift Register (LFSR) Calculator helps you generate and analyze pseudo-random binary sequences using shift registers with linear feedback. LFSRs are fundamental building blocks in digital electronics, used extensively in cryptography for stream cipher generation, in telecommunications for error detection and scrambling, and in circuit testing for generating exhaustive test patterns. Whether you are a student studying digital logic, a hardware engineer designing built-in self-test (BIST) circuits, or a researcher exploring pseudo-random number generation, this tool lets you experiment with different LFSR configurations interactively.
How the LFSR Algorithm Works
An LFSR consists of an n-bit register and a feedback function. The register stores the current state, and at each clock cycle, the bits shift to the right, ejecting the rightmost bit as output. The new leftmost bit is computed from a linear combination of tap positions using XOR (or NXOR) gates. In a Fibonacci LFSR, all tap bits are XORed together and the result becomes the new input bit. In a Galois LFSR, the output bit is XORed with the tap positions before the shift, giving a more efficient implementation. The choice of taps determines whether the LFSR achieves its maximum possible period of 2n - 1, known as a maximal-length LFSR.
How to Use This LFSR Tool
Enter a binary seed (e.g., 1001) and connection coefficients (taps) of the same length (e.g., 1101). Both must be binary strings containing only 0s and 1s. Select the LFSR type (Fibonacci or Galois) and gate type (XOR or NXOR). Optionally set a step limit for the computation. Click Generate Sequence to see the output bitstream, sequence period, and state transitions. The calculator will also tell you if your tap configuration produces a maximal-length LFSR that visits all 2n - 1 non-zero states. Use the display mode dropdown to toggle between the output sequence view and the detailed step-by-step breakdown of register states.
Frequently Asked Questions
What is a Linear Feedback Shift Register (LFSR)?
A Linear Feedback Shift Register (LFSR) is a shift register where the input bit is a linear function of its previous state, typically using XOR or NXOR gates. LFSRs are used to generate pseudo-random binary sequences for applications in cryptography, digital signal processing, and circuit testing.
What is the difference between Fibonacci and Galois LFSR?
In a Fibonacci LFSR, the feedback bits are XORed together and fed back into the first stage while all bits shift right. In a Galois LFSR, the output bit is XORed with the tap positions before shifting, processing feedback in a single step. Both types produce the same output sequence (with a possible shift and reflection) when using maximal-length taps.
What does a maximal-length LFSR mean?
A maximal-length LFSR visits all possible non-zero states before repeating, giving a period of 2n - 1 for an n-bit register. This produces the longest possible pseudo-random sequence before cycling. The calculator tells you if your tap configuration yields a maximal-length LFSR.
Why can't the seed be all zeros?
If the seed is all zeros, every subsequent state will also be all zeros regardless of taps, because XOR of zeros is always zero. The register would collapse permanently and never produce any output. This is why a seed must contain at least one 1 bit.
What are LFSRs used for in real-world applications?
LFSRs are widely used in cryptography for stream cipher generation, in wireless communication for scrambling and error detection (CRC), in built-in self-test (BIST) circuits for generating test patterns, and in digital signal processing for generating pseudo-noise sequences.
What is the period of an LFSR?
The period of an LFSR is the number of steps before the register returns to a previously visited state and the output sequence starts repeating. For an n-bit register, the maximum possible period is 2n - 1, achieved only with carefully chosen taps that make the characteristic polynomial primitive.
What is the difference between XOR and NXOR gates in LFSRs?
XOR (exclusive OR) outputs 1 when inputs differ and 0 when they match. NXOR (negated XOR) is the complement, outputting 1 when inputs match. An LFSR with NXOR gates will produce the bitwise complement of the sequence generated by the same register using XOR gates.