Bounds on pseudoexhaustive test lengths

摘要

Pseudoexhaustive testing involves applying all possible inputnpatterns to the individual output cones of a combinational circuit.nBased on our new algebraic results, we have derived both genericn(cone-independent) and circuit-specific (cone-dependent) bounds on thenminimal length of a test required so that each cone in a circuit isnexhaustively tested. For any circuit with five or fewer outputs, andnwhere each output has k or fewer inputs, we show that the circuit cannalways be pseudoexhaustively tested with just 2k patterns. Wenderive a tight upper bound on pseudoexhaustive test length for a givenncircuit by utilizing the knowledge of the structure of the circuitnoutput cones. Since our circuit-specific bound is sensitive to thenordering of the circuit inputs, we show how the bound can be improved bynpermuting these inputs