In short: A linear feedback shift register (LFSR) is a shift register whose input is the XOR of a few chosen stages; with the right taps, an n-bit LFSR cycles through all 2n−1 non-zero states, giving cheap pseudo-random patterns for logic BIST and, as a MISR, compact response signatures.
Why a shift register with XOR feedback is so useful
A plain shift register just delays data. Feed it back through an XOR gate and it becomes a deterministic sequence generator that needs only n flip-flops and a handful of XOR gates. A 32-bit LFSR costs 32 flops and 3 XORs, yet it walks through 4,294,967,295 distinct states before repeating. No counter plus lookup table comes close on area, and the critical path is a single XOR delay, so it runs at the full clock rate of the chip.
That economy is why LFSRs sit inside CRC engines, scramblers in PCIe and USB links, spread-spectrum codes in GPS, and, most relevant to VLSI interviews, the test hardware of almost every large SoC.
How the feedback works
Take four flops with the characteristic polynomial x4 + x3 + 1. The exponents name the tap positions: stage 4 and stage 3 feed the XOR, and the constant term 1 is the input to the first flop. Seed it with 0001 and clock it. Each tick the new bit is Q3 ⊕ Q2, and the rest of the word moves left.
The full 15-state loop is 0001, 0010, 0100, 1001, 0011, 0110, 1101, 1010, 0101, 1011, 0111, 1111, 1110, 1100, 1000, then back to 0001. Every non-zero 4-bit value appears exactly once. That is a maximal-length sequence, often called an m-sequence.
Key fact: An n-bit LFSR has at most 2n−1 states, not 2n. The all-zero state is a lock-up: XOR of zeros is zero, so the register never leaves it. XNOR-based LFSRs invert this and lock up on all-ones.
Maximal length needs a primitive polynomial
Not every tap choice gives the full period. Taps at stages 4 and 2 give x4 + x2 + 1, which splits the state space into short cycles. The condition is that the feedback polynomial be primitive over GF(2): irreducible, and with x generating the full multiplicative group. In practice you never derive it by hand; you look it up.
| Width n | Primitive polynomial | Period (2n−1) |
|---|---|---|
| 3 | x³ + x² + 1 | 7 |
| 4 | x⁴ + x³ + 1 | 15 |
| 8 | x⁸ + x⁶ + x⁵ + x⁴ + 1 | 255 |
| 16 | x¹⁶ + x¹⁵ + x¹³ + x⁴ + 1 | 65,535 |
| 32 | x³² + x²² + x² + x + 1 | 4,294,967,295 |
Two implementation styles exist. The Fibonacci form above puts all XORs in one feedback path. The Galois form places XORs between stages, so each gate sits on a short local path and the timing is better for wide registers. Both produce the same sequence for the same polynomial, only the internal state encoding differs. Interviewers love asking which is faster; the answer is Galois, because the longest path is always one XOR regardless of tap count.
Pseudo-random, not random
The output is statistically random-looking. Over one period an m-sequence has 2n−1 ones and 2n−1−1 zeros, runs of consecutive bits follow a geometric-like distribution, and its autocorrelation is nearly a perfect impulse. But it is fully deterministic and reproducible: same seed, same polynomial, same stream. That reproducibility is exactly what test needs and exactly why it must never be used for cryptography. The Berlekamp-Massey algorithm recovers an n-bit LFSR completely from just 2n observed output bits.
Key fact: Adjacent LFSR outputs are the same sequence shifted by one clock, so they are strongly correlated. Scan-based BIST therefore inserts a XOR-network called a phase shifter between the LFSR and the scan chains to decorrelate them.
Where it earns its keep: logic BIST
In logic BIST, an LFSR acts as the test pattern generator. It loads random patterns into the scan chains, the chip captures the logic response, and a multiple-input signature register (MISR), which is an LFSR with the circuit outputs XORed into each stage, folds millions of response bits into one n-bit signature. At the end you compare that signature with a golden value computed in fault-free simulation.
- No tester bandwidth needed. Patterns are made on-chip, so in-system and field self-test (automotive ISO 26262 start-up tests, for example) works without external equipment.
- Aliasing is tiny. A faulty response can still compress to the golden signature with probability about 2−n. For a 32-bit MISR that is roughly 2.3 × 10−10.
- Random-pattern-resistant faults. Wide AND/OR cones get exercised with very low probability, so BIST typically needs test points or a top-up of deterministic ATPG patterns, or LFSR reseeding.
- X-sources must be blocked. One unknown value reaching a MISR corrupts the whole signature, so X-bounding is mandatory.
Industrial flows automate all of this: Synopsys DFTMAX LogicBIST, Siemens Tessent LogicBIST and Cadence Modus can insert the controller, phase shifter and MISR, then compute signatures through fault simulation. Memory BIST uses a different engine (March algorithms), though LFSRs often supply its address and data randomisation.
Design checklist and common interview traps
- Never seed with all zeros in an XOR design. Add a reset-to-seed or a lock-up detector.
- To visit all 2n states, add a NOR-of-lower-bits term in the feedback (a de Bruijn modification).
- Check reachability of your seed: with a primitive polynomial every non-zero seed lies on the one big cycle.
- Clock-gating or hold conditions during capture must not step the MISR.
Engineers who want this practised on real flows can explore the counters and sequence generators article, and design-service teams like Avecas apply the same techniques in production DFT insertion. For structured training, see ChipXpert's VLSI training programmes.
Want to build and verify LFSRs, MISRs and full BIST flows hands-on? Explore the Digital Electronics and DFT tracks in the CourseTron courses.
FAQ
Why can't an XOR-based LFSR use the all-zero state?
Because 0 ⊕ 0 = 0, the feedback bit is always zero and the register stays at zero forever. That is why the maximum period is 2n−1.
How do I know which taps give a maximal sequence?
The feedback polynomial must be primitive over GF(2). Use published tap tables (such as those in Xilinx application note XAPP052) or verify by simulating the period in a script.
What is the difference between an LFSR and a MISR?
An LFSR generates a sequence with no data input. A MISR has the same feedback structure but XORs a parallel response bit into each stage, so it compresses data into a signature.
Can an LFSR be used for encryption?
Not on its own. It is linear, so 2n output bits reveal its entire state. Cryptographic designs combine several LFSRs with nonlinear functions, and even those are now considered weak.