Access Restriction

Author Richards, Donald L.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1973
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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 $\textit{F}$ is any set of switching functions, this paper establishes a necessary and sufficient condition on an arbitrary function set $\textit{G}$ such that all trees composed only of functions from $\textit{F}$ will accept $\textit{G};$ choosing $\textit{G}$ as the “testing” functions $\textit{P}(\textit{T,$ r) of the previous paper, this is the condition under which all such trees can be tested by $\textit{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 $\textit{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 $\textit{F}$ wherever $\textit{F}$ is a $\textit{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) $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1973-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 20
Issue Number 2
Page Count 13
Starting Page 320
Ending Page 332

Open content in new tab

   Open content in new tab
Source: ACM Digital Library