Circuit partitioning for pseudo-exhaustive test

Pseudo-exhaustive testing is not suitable to total dependency circuits in which at least one output is functionally dependent on all the inputs. Even for a partial dependency circuit, the size of a pseudo-exhaustive test set may still be too large to be applicable in practice. In such cases, pseudo-exhaustive test can be achieved by partitioning techniques. The principle is to partition the circuit into subcircuits such that the output of each subcircuit is functionally dependent on only a small number of inputs. Then the subcircuits are pseudo-exhaustively tested. Moreover, since the time complexity of test generation and fault simulation grows faster than a linear function of circuit size, it is cost-effective to partition large circuits to reduce these costs. A circuit partitioning tool, Autonomous, is presented to partition digital combinational portions of the circuit into different structural subcircuits so that each subcircuit can be pseudo-exhaustively tested. The effectiveness of partitioning method is shown by applying the method to different examples and practical VLSI designs