Linear Feedback Shift Register (LFSR) Calculator

Simulate an LFSR with custom initial state, tap positions, and number of clock cycles.

LFSR Configuration

Enter a binary string (e.g., 1011 for a 4-bit register)
Positions counted from 1 (leftmost = MSB = position N). Example: 4,3 for a 4-bit LFSR with taps at bits 4 and 3

Result

Output Bit Sequence
--
output stream
Register Size --
Tap Positions --
Period Detected --
Max Period (2^n - 1) --

State Transitions

feedback = XOR of tapped bits

What Is a Linear Feedback Shift Register?

A Linear Feedback Shift Register (LFSR) is a shift register whose input bit is a linear function (typically XOR) of its previous state. LFSRs are widely used in digital systems for generating pseudo-random sequences, error detection codes, scrambling, and encryption.

The register consists of a series of flip-flops connected in a chain, where the output of one feeds the input of the next. The feedback function takes certain bit positions (called taps), applies XOR to them, and feeds the result back into the register.

LFSR Types

Fibonacci LFSR

Also called external feedback. The tapped bits are XORed and fed to the input (leftmost bit).

new_bit = XOR(tap1, tap2, ...)

Galois LFSR

Also called internal feedback. Feedback is applied at the tap positions within the register.

Internal XOR at each tap position

Maximum Length

An LFSR with n bits can produce a maximum-length sequence of 2^n - 1 states before repeating.

Period = 2^n - 1 (for primitive poly)

How an LFSR Works

  1. Start with an initial state (seed) loaded into the register. The all-zeros state is typically avoided for XOR feedback.
  2. At each clock cycle, XOR the bits at the tap positions to produce the feedback bit.
  3. Shift all bits one position to the right. The rightmost bit is the output bit.
  4. Insert the feedback bit at the leftmost position.
  5. Repeat for the desired number of clock cycles.

Tap Positions and Polynomials

The choice of tap positions determines the sequence properties. A set of taps corresponds to a characteristic polynomial. For the LFSR to produce the maximum-length sequence, the characteristic polynomial must be a primitive polynomial over GF(2).

Applications of LFSRs

  • Pseudo-Random Number Generation: Fast hardware-based PRNGs for testing and simulation.
  • Cryptography: Stream ciphers often combine multiple LFSRs for key stream generation.
  • Error Detection: CRC (Cyclic Redundancy Check) codes use LFSR-based division.
  • Digital Communications: Scrambling data to ensure DC balance and clock recovery.
  • Built-In Self-Test: Testing digital circuits using LFSR-generated patterns.