Thumbnail
Access Restriction
Subscribed

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 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 $\textit{F}$ of switching functions and a set of required inputs for each (collectively denoted $\textit{T}),$ a “testing” function is defined for each element of $\textit{F}$ for each positive integer $\textit{r}.$ If the lines of a net can be mapped to the domain of the testing functions $\textit{P}(\textit{T,$ r) so that the gates perform consistent with these functions, we say the net “accepts” $\textit{P}(\textit{T,$ r)—and then $\textit{r}$ patterns are sufficient to test the net for $\textit{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 $\textit{r}$ such that all trees composed solely of the function accept $\textit{P}(\textit{T,$ r) (for various $\textit{T}).$ In most cases, as in the example given, the number of patterns required to test $\textit{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 $\textit{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., $\textit{h}-node$ colored for some particular $\textit{h})$ in the classical graph-theoretic sense. For example, any $\textit{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.
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-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 20
Issue Number 1
Page Count 24
Starting Page 88
Ending Page 111


Open content in new tab

   Open content in new tab
Source: ACM Digital Library