Bounds on pseudoexhaustive test lengths

Pseudoexhaustive testing involves applying all possible input patterns to the individual output cones of a combinational circuit. Based on our new algebraic results, we have derived both generic (cone-independent) and circuit-specific (cone-dependent) bounds on the minimal length of a test required so that each cone in a circuit is exhaustively tested. For any circuit with five or fewer outputs, and where each output has k or fewer inputs, we show that the circuit can always be pseudoexhaustively tested with just 2/sup k/ patterns. We derive a tight upper bound on pseudoexhaustive test length for a given circuit by utilizing the knowledge of the structure of the circuit output cones. Since our circuit-specific bound is sensitive to the ordering of the circuit inputs, we show how the bound can be improved by permuting these inputs.