Support Our Free Tools
Enable marketing cookies to see relevant ads and help us keep these calculators free.
LFSR Calculator
Linear Feedback Shift Register calculator for generating pseudo-random sequences
Calculate LFSR Sequence
Binary string (0s and 1s only). Cannot be all zeros.
Binary string indicating tap positions. Must match seed length.
Choose the type of linear feedback shift register
Choose what to display in the results
Number of output bits/steps to show (max 1000)
NXOR is the negation of XOR operation
LFSR Results
Output Sequence
Configuration: Fibonacci LFSR, XOR operation
Input: Seed: 1001, Taps: 1101
Example Calculation
4-bit Fibonacci LFSR
Seed: 1001
Taps: 1101 (positions 1, 2, and 4)
Operation: XOR
Expected Period: 15 (maximal length)
Step-by-Step
1001 → 1 (output bit)
XOR: 1⊕0⊕1 = 0 (new input)
0100 → 0 (next state)
Continues until returning to 1001...
Support Our Free Tools
Enable marketing cookies to see relevant ads and help us keep these calculators free.
LFSR Types
Fibonacci LFSR
Tapped bits XOR'd to create input
Most commonly used type
Galois LFSR
Output bit affects tap positions
Alternative implementation
LFSR Tips
Seed cannot be all zeros (null state)
Maximal length period = 2ⁿ - 1
Used for pseudo-random generation
Common in cryptography and testing
Understanding Linear Feedback Shift Registers
What is an LFSR?
A Linear Feedback Shift Register (LFSR) is a type of shift register where the input bit is determined by a linear operation (XOR or NXOR) on selected bits of the register. LFSRs are used to generate pseudo-random sequences with deterministic behavior.
Key Applications
- •Pseudo-random number generation
- •Cryptographic applications
- •Circuit testing and fault detection
- •Signal processing and communications
LFSR Parameters
- Seed: Initial state of the register
- Taps: Positions used for feedback calculation
- Period: Number of steps before repeating
- Maximal Length: Period = 2ⁿ - 1 (maximum possible)
XOR vs NXOR
0⊕1=1
1⊕0=1
1⊕1=0
0⊙1=0
1⊙0=0
1⊙1=1
Mathematical Formulation
Fibonacci LFSR
X₁(t+1) = c₁X₁(t) ⊕ c₂X₂(t) ⊕ ... ⊕ cₙXₙ(t)
Xᵢ(t+1) = Xᵢ₋₁(t) for 2 ≤ i ≤ n
- X⃗: Register state vector
- c⃗: Connection coefficient vector (taps)
- ⊕: XOR operation
- t: Time step
Galois LFSR
1. Shift all bits right
2. If output bit = 1: XOR taps with 1
3. If output bit = 0: no change to taps
Galois LFSRs produce the same sequences as Fibonacci LFSRs but with different tap configurations and implementation.
Maximal Length Sequences
For an n-bit LFSR to generate a maximal length sequence (period = 2ⁿ - 1), the tap configuration must correspond to a primitive polynomial. These special tap patterns ensure the LFSR visits all possible non-zero states exactly once before repeating.
Related Math Calculators
Support Our Free Tools
Enable marketing cookies to see relevant ads and help us keep these calculators free.