Hong Life CalculatorsUnderstanding the LFSR calculator — concept and principle
A linear-feedback shift register (LFSR) is a simple circuit that produces a long, pseudo-random-looking bit sequence. LFSRs are used in test pattern generation, scramblers, counters and checksums. This calculator runs a Fibonacci-style LFSR with your register length, taps, feedback gate and seed, shows the output bits and finds the period.
How it is calculated
At each clock:
- Output = last stage Qn
- Every bit moves one stage along (Q1 → Q2 → … → Qn)
- Q1 receives the XOR (or XNOR) of the tapped stages
Period = number of steps until the seed returns
Maximal length = 2ⁿ − 1, reached with suitable taps (from a published table)
A maximal sequence contains 2ⁿ⁻¹ ones and 2ⁿ⁻¹ − 1 zeros
The principle
An n-bit register has 2ⁿ possible states, and each state determines the next one, so the sequence must eventually repeat. With XOR feedback, the all-zeros state maps to itself, so it can never be part of a longer cycle; the longest possible cycle visits the other 2ⁿ − 1 states. Which taps achieve this corresponds to choosing a primitive polynomial in algebra over two elements; tables list suitable taps for each length. Because the feedback is linear, the sequence looks random but is completely predictable.
Worked example
Default inputs: n = 4, maximal-length taps from the table, XOR, seed 1000, show 30 steps.
- Taps used = 4, 3.
- Running the register gives output bits 0001 0011 0101 1110 0010 0110 1011 11.
- The state returns to the seed after 15 steps, which equals 2⁴ − 1 = 15, so maximal length: yes.
- After 30 steps (two full periods) the register is back at 1000.
- Ones in one full period = 8 (= 2³), zeros 7.
How to read the result
A period of 2ⁿ − 1 means the taps are maximal. A shorter period means the register cycles through only part of its states, which is usually undesirable for test patterns or counters. Longer registers give astronomically long periods, which is why they are used to generate long test sequences cheaply in hardware.
Common mistakes
- Starting from the lock-up state (all zeros for XOR, all ones for XNOR).
- Mixing tap numbering conventions between sources.
- Leaving out the last stage n from the taps.
- Using an LFSR where cryptographic security is needed.
Frequently asked questions
Why is the maximum period 2ⁿ − 1 and not 2ⁿ?
The lock-up state maps to itself, so it cannot be part of the main cycle.
What is the difference between XOR and XNOR feedback?
XOR locks up in the all-zeros state; XNOR locks up in the all-ones state.
Where are LFSRs used?
Built-in self-test, scramblers, pseudo-random counters and CRC calculation.
Are LFSR outputs random?
They have good statistical balance but are fully predictable.
Sources: P. Alfke, "Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators", Xilinx Application Note XAPP 052 (1996)