The problem of finding a minimum number of patterns to exercise the logic elements of a combinational switching net is investigated. Throughout, the word “testing” refers to exercising of this kind; or, equivalently, to fault diagnosis where each line of the net can be directly observed. Any set of permanent faults can be selected to test against, examples of which range from “stuck-at” faults (allowing the most economical test) to “any possible fault” (requiring the most complete test). The method used depends upon exact structural analysis rather than upon search algorithms or random pattern generation. The types of results presented appear to be fundamentally new. In particular, the maximum number of patterns required to test any one of an infinite class of nets is frequently found to be finite and extremely small. For example, any nontrivial connected tree of 2-input nand gates can be tested for “any possible fault” by exactly five patterns—no more and no less. The method in brief: Given a set F of switching functions and a set of required inputs for each (collectively denoted T ), a “testing” function is defined for each element of F for each positive integer r . If the lines of a net can be mapped to the domain of the testing functions P ( T, r ) so that the gates perform consistent with these functions, we say the net “accepts” P ( T, r )—and then r patterns are sufficient to test the net for T . Only nets in which each logic element is intended to realize the same switching function are discussed here. Trees (nets without fanout) are studied first, and the conditions under which a tree of identical gates “accepts” a partial function on an arbitrary domain is established. Then the common symmetric switching functions are separately investigated to find for each a minimum value of r such that all trees composed solely of the function accept P ( T, r ) (for various T ). In most cases, as in the example given, the number of patterns required to test any such tree is extremely low. The conditions under which all nets (nontrees included) accept a set of partial functions with arbitrary domain are then established. These conditions are rarely met in practice, even where F consists of a single function. However, many subclasses of nets can be identified which require only a few patterns at most (depending on the function and the class of faults selected). These subclasses often contain nets of arbitrary size and complexity, and frequently consist of exactly those nets for which a related graph can be “colored” (i.e., h -node colored for some particular h ) in the classical graph-theoretic sense. For example, any net of 2-input nand gates can be tested by five patterns if one of its related graphs is 2-colorable and another one is 3-colorable (!). The detailed results and methods used to obtain them are summarized, and in conclusion coloring problems and test construction are commented upon.

The work described in a previous paper, “Efficient Exercising of Switching Elements in Nets of Identical Gates,” is continued. Sections 1, 3, and 4 of the previous paper are prerequisites to the current work. Exercising, or “testing,” the gates of a net is equivalent to performing fault diagnosis in the case in which each fault is detectable. Where F is any set of switching functions, this paper establishes a necessary and sufficient condition on an arbitrary function set G such that all trees composed only of functions from F will accept G ; choosing G as the “testing” functions P ( T, r ) of the previous paper, this is the condition under which all such trees can be tested by r (or fewer) patterns. The case of “stuck-at” faults is then investigated at length. It is shown that: (a) all trees can be tested for stuck-at faults by three patterns, and nearly all by two patterns; (b) for some interesting classes of functions, all nets can be tested by two patterns—in general, many nets can; (c) for any set of functions which are functionally complete and suitably closed under constant inputs, there are nets which require arbitrarily many patterns. The latter result suggests that nets requiring arbitrarily many patterns exist for nearly all interesting choices of functions and of faults. For “input dependence” tests, a result is cited to show that economical testing of nets of nand (nor) gates of mixed sizes is possible. Finally, for the case of exhaustive testing, experience suggests that economical tests exist for most nets composed from functions of F wherever F is a bounded set—i.e. a set of functions for which there is a fixed upper bound on the number of patterns required to test any tree. The (individually) bounded functions are completely characterized; then the bounded sets of symmetric functions are completely characterized. The latter prove to be those sets for which: (a) each function is individually bounded (i.e. not “and,” “or,” or constant); and (b) F contains at most one of the following: (1) “not,” (2) a “nand” function, (3) a “nor” function. Thus bounded sets of functions are the rule, not the exception, and economical testing appears to be generally possible.

The SWAP system consists of an interconnected set of computer programs whose general purpose is to aid in the design and fabrication of electronic equipment. The principal input to the system at this stage is a list of Boolean logical equations, which describe the design of a piece of digital equipment; for example, an airborne computer. Other possible inputs describe the logical, electronic and geometric properties of the circuit modules which are used to build the equipment, the geometric properties of the boards upon which these circuits are to be laid out, the symbols which correspond to the circuit elements, the time intervals over which simulation is observed, the placement of specific modules on the boards, and various options which are available to the program user.The final output of the SWAP system is a complete diagrammed layout of the equipment in the form in which it will be fabricated; the fabrication process is actually controlled indirectly by the computer output. A record of the logical behavior of the equipment during simulation can also be provided as well as a diagram of the final module layout and various listings which can be used to check the input.