LFSR Calculator
Generate pseudo-random sequences using Linear Feedback Shift Registers
Number of bits in the shift register (typically 4-8 for examples)
Comma-separated tap positions (e.g., "3,4" means taps at positions 3 and 4). Taps determine the feedback polynomial.
Initial register value as binary (e.g., "1011") or decimal (e.g., "11"). Cannot be all zeros.
Number of output values to generate (1-1000)
How to Use This Calculator
Enter Number of Bits
Specify the size of your shift register (number of bits). Common values are 4, 8, or 16 bits.
Enter Tap Positions
Enter the tap positions (comma-separated) that determine the feedback. For example, "3,4" means taps at positions 3 and 4.
Set Initial State
Enter the initial value of the register as binary (e.g., "1011") or decimal (e.g., "11"). The initial state cannot be all zeros.
Generate Sequence
Click Generate to create the pseudo-random sequence. The calculator will show the binary sequence, decimal values, and the period.
Formula
Feedback = XOR of bits at tap positions
New bit = (state >> 1) | (feedback << (n-1))
Feedback Calculation:
feedback = b[tap₁] ⊕ b[tap₂] ⊕ ... ⊕ b[tapₖ]
where b[i] is the bit at position i, and ⊕ is XOR
Shift Operation:
new_state = (old_state >> 1) | (feedback << (n-1))
Shifts register right, inserts feedback bit at the left
Feedback Polynomial:
P(x) = xⁿ + x^tap₁ + x^tap₂ + ... + 1
The polynomial determines the sequence period
Example (4-bit, taps at 3,4):
Initial: 1011
Tap positions 3 and 4: bits at positions 3 and 4 are 1 and 1
Feedback: 1 ⊕ 1 = 0
New state: 0101 (shift right, insert 0 at left)
About LFSR Calculator
A Linear Feedback Shift Register (LFSR) is a shift register whose input bit is a linear function of its previous state. LFSRs are widely used in digital systems for generating pseudo-random sequences, error detection and correction codes, cryptography, and testing digital circuits.
What is an LFSR?
An LFSR consists of a shift register (a series of flip-flops) and feedback taps. At each clock cycle, the register shifts right, and a new bit (calculated as the XOR of tapped bits) is inserted at the left. This creates a deterministic but pseudo-random sequence.
Applications
- Cryptography: Generating stream cipher keys and pseudo-random numbers
- Error Detection: CRC (Cyclic Redundancy Check) codes use LFSR principles
- Scrambling: Data scrambling in communications systems
- Testing: Built-in self-test (BIST) for digital circuits
- Spread Spectrum: Direct sequence spread spectrum systems
- Random Number Generation: Hardware random number generators
Maximal-Length LFSRs
A maximal-length (or maximum-length) LFSR has a period of 2ⁿ - 1 (where n is the number of bits), meaning it cycles through all possible non-zero states exactly once before repeating. Such LFSRs use primitive polynomials and are highly desirable for pseudo-random number generation.
Common Tap Configurations
Examples of maximal-length LFSRs:
- 4-bit: Taps at 3,4 (period = 15)
- 5-bit: Taps at 3,5 (period = 31)
- 6-bit: Taps at 5,6 (period = 63)
- 7-bit: Taps at 6,7 (period = 127)
- 8-bit: Taps at 4,5,6,8 (period = 255)
Properties
- Deterministic: Given the same initial state and taps, always produces the same sequence
- Periodic: Eventually repeats the same sequence
- Efficient: Hardware implementation is simple and fast
- Predictable: Not cryptographically secure if the taps are known
Frequently Asked Questions
What is the maximum period of an n-bit LFSR?
The maximum period is 2ⁿ - 1 for an n-bit LFSR. This occurs when using a primitive polynomial. The all-zero state is excluded because it would cause the LFSR to remain stuck at zero.
How do I choose good tap positions?
For maximal-length sequences, you need tap positions that correspond to a primitive polynomial. Common configurations are well-documented. For a 4-bit LFSR, taps at positions 3 and 4 give a maximal-length sequence (period = 15).
Why can't the initial state be all zeros?
If the LFSR starts with all zeros, and the feedback is calculated from tapped bits (which are also zero), the feedback will always be zero. This causes the LFSR to remain stuck at the all-zero state forever, generating no useful sequence.
Are LFSRs cryptographically secure?
No, basic LFSRs are not cryptographically secure. Given enough output bits, the taps can be determined using techniques like the Berlekamp-Massey algorithm. For cryptographic applications, LFSRs are often combined with non-linear functions or multiple LFSRs.
What's the difference between Fibonacci and Galois LFSRs?
Fibonacci (or external-XOR) LFSRs feed back into the input. Galois (or internal-XOR) LFSRs have XOR gates between stages. Both generate the same sequence, but Galois LFSRs are typically faster in hardware implementations.