A new measure of system diagnosis, t/s diagnosability, originally proposed by Friedman, is used to study the diagnosability of digital systems. This new measure incorporates the concept of possible replacement of fault-free units in system repair, whereas the previous measures have only considered the replacement of faulty units. Two categories of the new measure, one-step t/s diagnosability and sequential t/s diagnosability, are investigated. Two canonical classes of systems, single loop systems and DδAsystems (⌊t/2⌋ < A ≤ t), are examined based on these two categories of diagnosability. For each system class, the necessary and sufficient condition for one-step ts diagnosability is obtained and related to some previous results on t-fault diagnosability; also, an efficient one-step t/s repair procedure is presented. For both these system classes, optimal one-step t/s diagnosable system designs, which minimize the number of units and test links, are considered. Several sequential diagnosis strategies are presented for each system class. For all these diagnosis strategies optimal system designs are also considered. Finally, all the diagnosis strategies are compared and the tradeoff between the number of units replaced and the number of test iterations performed is discussed.

In this paper, we consider the problem of determining if a given set of simple combinational functions, called logic primitives, can be used to realize any arbitrarily complex combinational function. The complex combinational function is realized by suitably interconnecting the primitives, and in most cases several copies of the primitives. Such a set of primitives is said to be complete in some sense. Two important types of logical completeness that have been previously studied are: 1) strong completeness where the circuit inputs are the uncomplemented variables x1,x2,···,xn, and 2) weak completeness where the circuit inputs are 0,1,x1,x2,···,xn. In this paper, we discuss two new types of logical completeness: strong c-completeness with inputs x1, x̄1, x2, x̄2,···,xn, x̄n and weak c-completeness with inputs 1, 0, x1, x̄1, x2, x̄2,···, xn, x̄n, and we derive necessary and sufficient conditions for a set of primitives to be strong c-complete or weak c-complete. We also discuss the relations between the above four types of completeness. Finally, we consider two more types, complement completeness and dual completeness, which may have applications to some recent technologies.