A metric towards efficient pseudo-exhaustive test pattern generation

A built-in self-test technique in which test patterns are generated exhaustively by means of a linear feedback shift register (LFSR) is treated. The goal is to find an appropriate primitive polynomial of degree d (d⩽20) so that the 2^d test patterns generated by the corresponding LFSR can exhaustively exercise all circuit outputs simultaneously. A metric quantity that naturally reflects the difficulty of deriving an appropriate primitive polynomial of degree d is presented. This metric is used in a heuristic that inserts bypass storage cells in the circuit under test, so that the cells can form an appropriate LFSR with very low addition cell overhead. Extensive experimentation shows that the approach is economical