NDLI: Efficient Exercising of Switching Elements in Nets of Identical Gates

Content Provider	ACM Digital Library
Author	Richards, Donald L.
Copyright Year	1973
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.
Starting Page	88
Ending Page	111
Page Count	24
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/321738.321746
Journal	Journal of the ACM (JACM)
Volume Number	20
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1973-01-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient Exercising of Switching Elements in Combinatorial Nets

Efficient simulation of finite automata by neural nets

Maintained Activity in Neural Nets

Arithmetical Analysis of Digital Computing Nets

Realization of Events by Logical Nets

Analysis of Nets by Numerical Methods

Efficient Planarity Testing

Turing Machines, Finite Automata and Neural Nets

Properties of Conflict-Free and Persistent Petri Nets

Efficient Exercising of Switching Elements in Nets of Identical Gates

Similar Documents

Efficient Exercising of Switching Elements in Combinatorial Nets

Efficient simulation of finite automata by neural nets

Maintained Activity in Neural Nets

Arithmetical Analysis of Digital Computing Nets

Realization of Events by Logical Nets

Analysis of Nets by Numerical Methods

Efficient Planarity Testing

Turing Machines, Finite Automata and Neural Nets

Properties of Conflict-Free and Persistent Petri Nets

Efficient Exercising of Switching Elements in Nets of Identical Gates