Multiple path sensitization for hierarchical circuit testing

The HPath algorithm for multiple-path sensitization in hierarchical, multilevel descriptions, which is based on semiregular structures within many VLSI circuits, is discussed. The algorithm which has been derived, implemented, and tested is applicable to circuits which can be described as semiregular and pseudocombinational for performance of testing functions related to test pattern generation, design-for-testability, built-in self-test, and diagnosis. HPath sensitizes the target paths, which may consist of multiple bits, one by one through hierarchically described circuits. Depending on the specification of each path, HPath propagates the path block by block in either the forward or backward direction. HPath is, in fact, a control mechanism which determines which path to sensitize and which block to propagate through. The sensitization is actually done by its two major components, GPath and FPath. GPath is an implicit enumeration algorithm which utilizes symbolic manipulation to achieve multiple-path sensitization for gate-level circuits. FPath is a rule-based subsystem which sensitizes multiple paths for functional-level descriptions through a sequence of rule applications. It is shown that GPath is not as efficient as FPath