MOS Test Pattern Generation Using Path Algebras

There is extensive evidence that the classical, stuck-at fault model, operating at the gate level, is inadequate for testing MOS VLSI circuits. By contrast, a ``nonclassical,´´ switch-level model¿directly representing open and short circuits in the interconnect and transistors stuck-open or stuck-on¿allows important effects such as MOSFET bidirectionality and tristate behavior to be taken into account. This paper describes a new switch-level method for generating the singular cover of an MOS primitive gate using path algebras. The method yields tests to cover all specified interconnect open and short circuits, and all irredundant transistor stuck-open and stuck-on faults, should such tests exist. It relies on specification of an appropriate algebra by redefinition of the operators used in computing powers of a matrix. Two such algebras are required¿one to generate tests for open circuit faults and the other for short circuit faults. Test generation for networks of primitive gates is achieved in two stages: after deriving singular covers for the primitives, a variant of the D-algorithm with modified ``D-drive´´ is used. The approach is unified and powerful, having the potential to detect parasitic latch behavior and to generate tests for any of the current MOS VLSI technologies. In common with most present automatic test generation methods, it is restricted to combinational logic. Practical limits on the size of circuit which can be dealt with appear comparable to those set by use of the classical D-algorithm.