A COORDINATED CIRCUIT PARTITIONING AND TEST-GENERATION METHOD FOR PSEUDO-EXHAUSTIVE TESTING OF VLSI CIRCUITS

In this paper, we present a circuit partitioning and test pattern gene ration technique for pseudo-exhaustive built-in self-testing of VLSI c ircuits. The circuit partitioning process divides a given circuit into a set of subcircuits which can be exhaustively tested, while the test pattern generation process generates reduced exhaustive test patterns for each subcircuit using a linear feedback shift register (LFSR). In conventional approaches, these two problems are considered separately . However, in this paper, both problems are considered and solved in t he same phase. A graph theoretic model of VLSI circuits is proposed. B ased on this model, a circuit partitioning algorithm using the concept of minimum vertex cut is devised to partition the circuit into a set of exhaustively testable subcircuits with restricted hardware overhead . Each time a subcircuit is generated by the partitioning algorithm, t he test pattern generation problem is considered. A new algorithm, bas ed on the subcircuit modification technique, is proposed with the obje ctive of generating reduced exhaustive test patterns of limited length (e.g., less than or equal to 2(20)) using LFSR's, for each of the sub circuits. This task is embedded in the circuit partitioning process it self, leading to an efficient and well-coordinated solution. Experimen ts using ISCAS benchmark circuit simulation have been conducted. The r esults demonstrate that the proposed method is very good.