Efficient Exercising of Switching Elements in Combinatorial Nets

ABSTRACT

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.

REFERENCES

• 1: Donald L. Richards, Efficient Exercising of Switching Elements in Nets of Identical Gates, Journal of the ACM (JACM), v.20 n.1, p.88-111, Jan. 1973 [doi>10.1145/321738.321746]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis

General Terms:
Performance, Reliability, Theory, Verification