Design for Testability: MISR Deep Dive The Mathematics of Compaction
The previous article introduced the MISR as the hardware mechanism that compresses a long response stream into a short final signature. The explanation was intentionally kept at the level of behavior: bits go in, state evolves, a signature comes out, and the probability of aliasing is bounded by 1/2^W. That level of understanding is sufficient to use a MISR. It is not sufficient to reason about why a particular MISR design is good or bad, why its feedback polynomial matters, or why the same property that makes it efficient also introduces the aliasing risk that was described qualitatively before.
This article goes deeper. The goal is to make the internal mechanics of the MISR transparent, so that when the tradeoffs come up in a real flow, the reasoning behind them is accessible.
Starting From the Ordinary Shift Register
The easiest way to understand a MISR is to start from something simpler and add components one at a time.
A standard shift register of width W is a chain of W flip-flops. Each clock cycle, the bit in position i moves to position i+1. A new bit enters at position 0. The bit at position W-1 is either discarded or observed. After W cycles, the register holds the last W bits of the input stream, and nothing older.
This is useless for compaction. It remembers only the tail of the stream. Everything that arrived earlier is gone, and two different long streams that happen to share the same final W bits will produce identical register states. The aliasing probability is not 1/2^W — it is essentially 1 for any stream longer than W.
What is needed is a mechanism that mixes incoming bits with the existing state so that old bits continue to influence the register’s future evolution even after they would have been shifted out. That mechanism is XOR feedback.
Adding Feedback: The Linear Feedback Shift Register
A Linear Feedback Shift Register (LFSR) modifies the ordinary shift register by XORing selected bits of the current register state into the input of one or more stages. The positions where this feedback is applied are called the tap positions, and the pattern of taps defines the feedback polynomial.
With feedback, each new state is a function of the entire previous state, not just the last input. Bits from earlier cycles influence the state for as long as the LFSR runs, through the recurrence. This is the property that makes the LFSR useful for compaction.
But a standard LFSR has no external input. It generates sequences from its initial state. To compact an external bitstream, inputs must be injected into the register while it runs. This is the step that turns an LFSR into a MISR.
The MISR: Injecting External Data Into the Recurrence
A MISR is an LFSR with one additional modification: at each clock cycle, external response bits are XORed into the register state as it updates. The external inputs arrive in parallel across multiple positions in the register, which is why the name includes “Multiple Input.”
The result is that each new state of the MISR depends on both the history of all previous inputs (through the LFSR recurrence) and the current cycle’s inputs (through direct injection). Every bit of the response stream, from cycle 1 through cycle L, is folded into the final state. No bit is discarded.
The Matrix View of MISR Evolution
Like the decompressor, the MISR can be described exactly by a matrix equation over GF(2). This is important because it connects the MISR to the same algebraic framework used to analyze the decompressor, and it makes the aliasing probability argument rigorous rather than intuitive.
At each clock cycle, the MISR state update is a linear operation on the current state and the new input. This can be written as:
This expression shows that the final signature is a linear combination of all input vectors, each weighted by a different power of the transition matrix T. Every input cycle’s contribution is mixed into the final state through a distinct matrix weight. This is the formal reason why earlier inputs are not lost: they appear as terms T^(L-k) * s_k in the sum, and as long as T is invertible (which a well-designed LFSR transition matrix always is over GF(2)), these terms are independent.
Why the Feedback Polynomial Matters
The feedback polynomial determines the transition matrix T, and T determines the mixing properties of the MISR. Not all polynomials are equally good.
A polynomial is called primitive over GF(2) if the LFSR it defines cycles through all 2^W — 1 non-zero states before repeating. A primitive polynomial produces a maximal-length sequence, meaning the LFSR visits every possible non-zero state exactly once per period. This is the property that determines the quality of the MISR as a signature analyzer.
For compaction specifically, what matters is that T^k is a different matrix for every k in the range 0 to 2^W — 2. If two different powers T^(L-k) and T^(L-j) were equal, then inputs at cycles k and j would contribute identically to the final signature, and any fault that flipped a bit at cycle k but not cycle j (or vice versa) would cancel in the sum and produce no change in the signature. This is precisely aliasing.
In industrial MISR design, primitive polynomials are standard. For common register widths, primitive polynomials are tabulated and well-known. The ATPG tool selects them automatically, but the test engineer should understand why the choice matters.
How a Long Stream Maps to a Short Signature
It is worth spelling out the compaction ratio explicitly in the temporal dimension, because this is where the MISR’s efficiency is most dramatic.
Consider a design with C = 512 internal scan chains, each of length L = 5,000. The total response bitstream after one capture contains 512 * 5,000 = 2,560,000 bits. In an uncompressed design, the tester would need to store and compare all 2,560,000 expected bits per pattern.
Get Rana Umar Nadeem’s stories in your inbox
Join Medium for free to get updates from this writer.
With a MISR of width W = 32:
The 80,000x compaction ratio is not achieved by discarding most of the response. It is achieved by folding all 2,560,000 bits into a 32-bit register state through the MISR recurrence. Every bit of the response contributes to the final signature. The compaction is lossless in the information-theoretic sense that any single-bit error anywhere in the 2,560,000-bit stream will, with probability (1–1/2³²), change the final signature.
The Aliasing Mechanism Made Exact
The previous article stated the aliasing probability as 1/2^W. That result can now be derived from the matrix framework, which makes it more than a rule of thumb.
Define the error vector e_k = s_k XOR s_k_good, where s_k is the actual (possibly faulty) response at cycle k and s_k_good is the fault-free response. The MISR computes the correct signature for a fault-free response. A fault is undetected (aliased) if and only if the final error contribution to the MISR state is zero:
The assumption of uniform random error patterns is what makes this a probability statement rather than a guarantee. It is a good assumption for independent, uncorrelated fault effects across different scan cells and different shift cycles. It breaks down when error patterns are highly structured, which can happen with specific fault models or with correlated physical defects. This is one reason why MISR-based compaction is combined with multiple independent patterns rather than relying on a single long shift sequence.
Multiple Capture Cycles and Signature Reset
In practice, the MISR is not run continuously across the entire test from start to finish. It is reset between patterns. Each test pattern corresponds to one MISR accumulation window: load seed, shift in, capture, shift out into MISR, read and compare final state, reset MISR to zero, repeat.
Resetting between patterns is important for two reasons. First, it ensures that the expected signature for each pattern is computed independently, which keeps the ATPG precomputation tractable. Second, it prevents error accumulation: if the MISR were not reset and a fault corrupted the signature for pattern k, the corrupted state would influence the signatures for all subsequent patterns, making fault diagnosis impossible.
MISR Reset Flow Per Pattern:
1. Reset MISR to all zeros
2. Shift in compressed seed (W channels for L cycles)
3. Apply capture clock (functional frequency)
4. Shift out scan cells into MISR (L cycles)
5. Compare MISR[0..W-1] to M_expected for this pattern
6. If mismatch: device flagged as fail
7. Goto 1 for next pattern
Note: Steps 2 and 4 can overlap in time using EDT's
simultaneous shift architecture (covered in a later article)When the MISR is Not Enough: Diagnostic Limitations
The MISR is an excellent go/no-go detector. It is a poor diagnostic tool.
When a device fails, the tester knows which pattern produced a signature mismatch. It does not know which scan cell produced the wrong value, which fault caused it, or where in the scan chain the error appeared. The compaction that makes the MISR efficient is exactly what destroys the spatial and temporal information needed for diagnosis.
Diagnosis requires uncompacted data. In practice, when a failing device needs to be diagnosed, the test program is run in a special diagnostic mode where the MISR is bypassed and individual scan chain outputs are observed directly, either through dedicated diagnostic scan-out paths or through a reduced-compression mode with fewer chains per output channel. This diagnostic flow is slower and uses more tester bandwidth, but it is only applied to the small subset of devices that fail production test.
This separation of production test and diagnostic test is a fundamental architectural feature of any compressed test flow. The MISR handles scale. Diagnosis handles depth. Neither mode is sufficient alone.
Closing Remarks
The MISR is a compact piece of hardware that performs an outsized engineering function. A 32-bit register with a handful of XOR gates compresses 2.5 million response bits into a 32-bit signature with a fault escape probability of roughly 2 in 10 billion per pattern. The mechanism behind this is not heuristic or approximate — it is a consequence of the algebraic properties of linear recurrences over GF(2), and specifically of the primitive polynomial that governs the state transition matrix.
The key ideas to carry forward are these. First, feedback is what makes the MISR different from a shift register: it ensures that every input bit influences the final state through the recurrence, so nothing is discarded. Second, the primitive polynomial ensures that the transition matrix powers are all distinct, which minimizes aliasing by ensuring independent mixing weights for every input cycle. Third, the aliasing probability of 1/2^W follows from the linearity of the mapping and the surjectivity of the error-to-delta-state transform, not from statistical heuristics. Fourth, the MISR’s efficiency comes at the cost of diagnostic resolution, and the two modes of test operate on different data paths for this reason.
Understanding the MISR at this level makes the next layer of the compression architecture accessible. The following article will examine how the decompressor and the MISR are integrated with the ATPG engine to form a complete end-to-end compression flow, and how the compression ratio, pattern count, and masking strategy are co-optimized as a system.
This article is part of an ongoing series on Design for Testability. The full series is on my Medium profile.
Further Reading:
- Xilinx XAPP052 — Efficient Shift Registers and LFSR Counters (primitive polynomial tables)
- IEEE Xplore — MISR-Based Compaction in Scan Test: Theory and Practice
- Siemens EDA Tessent Documentation — MISR Configuration and Signature Analysis
- Synopsys DFTMAX — Compactor Architecture and Aliasing Analysis
- Academia — Linear Feedback Shift Registers and Their Application to Signature Analysis
Connect with Me:
- GitHub: ranaumarnadeem
- Medium: @ranaumarnadeem
- LinkedIn: Rana Umar Nadeem
#VLSI #ASICDesign #LogicSynthesis #ClockGating #LowPowerDesign #RTLDesign #DigitalDesign #DFT #BackendDesign #EDA #Cadence#Genus #Sky130 #RTLtoGDSII #SemiconductorEngineering #PowerOptimization #TechBlog #PREMAPPING #LEC #COP #SOACP #distance #controllibility #modus #scan_chains
