The problems of identifying several nontrivial classes of Polynomial-Time Testable (PTT) circuits are shown to be NP-complete or harder. First, PTT classes obtained by using circuit decompositions proposed by Fujiwara (1988) and Chakradhar et al. (1990) are considered. Another type of decompositions, based on fanout-reconvergent (f-r) pairs, which also lead to PTT classes are proposed. The problems of obtaining these decompositions, and also some structurally similar general graph decompositions, are shown to be NP-complete or harder. Then, the problems of recognizing PTT classes formed by the Boolean formulae belonging to the weakly positive, weakly negative, bijunctive and affine classes are shown to be NP-complete.>

The shift register realization of sequential circuits is reexamined. Though the shift register realization requires no extra circuits for scan, and shortens test application time, it in general requires many memory elements. This paper presents a method to reduce the number of memory elements in a shift register realization. >

Single output logic circuits composed of AND and EXOR gates are studied. It is shown that for two level single output logic circuits composed of AND and EXOR gates, tests that detect all detectable stuck-at faults can be generated in polynomial time. In this method no extra input variables nor extra circuits are required. This contrasts with the fact that for AND, OR circuits the test generation problem is not polynomial time solvable even for two level circuits. Since AND-EXOR circuits can represent any switching function, this suggests that these circuits might be easier to test than AND, OR circuits.>

The problem of test generation for detecting stuck-at faults in combinational circuits is computationally intractable. Consequently, the identification of classes of circuits that support polynomial-time test generation algorithms is very important from testing and design viewpoints. The authors discuss several classes of polynomially-time testable circuits. First, they consider the existing polynomial classes obtained by using decompositions of the circuits. Another type of decomposition is proposed, based on fanout-reconvergent pairs, which also lead to classes of polynomial-time testable circuits. Then, the authors present the classes of polynomial-time testable circuits that are formed by the Boolean formulae belonging to the classes of weakly positive, weakly negative, bijunctive and affine.>

In this correspondence we analyze the computational complexity of fault detection problems for combinational circuits and propose an approach to design for testability. Although major fault detection problems have been known to be in general NP-complete, they were proven for rather complex circuits. In this correspondence we show that these are still NP-complete even for monotone circuits, and thus for unate circuits. We show that for k-level (k ≥ 3) monotone/unate circuits these problems are still NP-complete, but that these are solvable in polynomial time for 2-level monotone/unate circuits. A class of circuits for which these fault detection problems are solvable in polynomial time is presented. Ripple-carry adders, decoder circuits, linear circuits, etc., belong to this class. A design approach is also presented in which an arbitrary given circuit is changed to such an easily testable circuit by inserting a few additional test-points.

Consider a network which can be represented by an acyclic directed graph such that the links represented by the edges are subject to failure. Under the assumption that at most one link can fail at any time, we want to locate a failed link, if any, by means of certain tests. A test is performed by injecting a signal at a vertex and monitoring it at another vertex and can reveal if there is a failed link on any path between the two vertices. We want to find a minimal set of tests that can uniquely locate any single fault. Since this problem is in general NP-complete, we investigate a special case where the given network has a tree structure. We present an algorithm whose worst case running time can be bounded by a linear function of the input size.

If the addition of a test does not improve the diagdosability of a system the test is called redundant. It is shown that if at least one test is nonredundant, then the previous algorithms to determine the diagnosability [2],[3] can be further improved. It is also shown how and when the diagnosability of a system can be improved by the addition of an extra test.

System diagnosis is investigated along the line of a pioneering work by Preparata et al. and motivated by a recent work of Hakimi and Amin. It is shown that practically all the previous results on the analysis aspect of this problem can be derived from a single theorem in this correspondence.

An algorithm to find the Hamiltonian circuit in a bipath network is developed. Using the Hamiltonian circuit all cutsets of a bipath network are generated from incidence sets in a systematic way without duplication. Also it is shown that the algorithm to find the Hamiltonian circuit can be used to test a graph for bipathness.