On Finding a Nearly Minimal Set of Fault Detection Tests for Combinational Logic Nets

A procedure is described for finding, by shortcut methods, a near-minimal set of tests for detecting all single faults in a combinational logic net. The procedure should prove useful for nets which are too large to be treated by more exact methods 2. The set of tests so found also appears useful for diagnosing (i.e., locating) faults. The class of faults considered is that which causes connections to be stuck at logical one or logical zero. The nets considered may include AND, OR, NAND, NOR, and NOT gates. The bases of the procedure are the ``path sensitizing'' concept, and reduction of a net to its ``equivalent normal form,'' abbreviated enf. It is shown that if a set of tests can be found which detects an appropriate subset of faults in the enf, this set will detect all faults in the original net. The enf also provides a vehicle for systematically finding the most desirable tests, namely those which each detect many faults in the net. The procedure is illustrated in detail by an example.