The reliability of a fault-tolerant circuit may be drastically impaired by the presence of maskable faults that never affect its functionality. Design for testability (DFT) techniques have to be applied to make maskable faults detectable. During the testing phase, traditional DFT schemes inhibit fault masking and/or activate additional observation/control paths through the circuit. Such schemes, however, do not enable on-line testing and cannot be applied to multilevel fault-tolerant circuits, where fault-masking is repeatedly performed inside the circuit. We propose a new approach to the design of testable fault-tolerant CMOS circuits that overcomes both limitations. Our approach is based on the use of I/sub DDQ/-checkable voters (ICVs) that enable a complete test of maskable faults of any multiplicity during normal operations.

Symbolic methods are often considered the state-of-the-art technique for validating digital circuits.Due to their complexity and unpredictable run-time behavior, however, their potential is currently limited to small-to-medium circuits.Logic simulation privileges capacity, it is nicely scalable, flexible, and it has a predictable run-time behavior.For this reason, it is the common choice for validating large circuits.Simulation, however, typically visits only a small fraction of the state space: The discovery of bugs heavily relies on the expertise of the designer of the test stimuli.In this paper we consider a symbolic simulation approach to the validation problem.Our objective is to trade-off between formal and numerical methods in order to simulate a circuit with a "very large number" of input combinations and sequences in parallel.We demonstrate larger capacity with respect to symbolic techniques and better efficiency with respect to cycle-based simulation.We show that it is possible to symbolically simulate very large trace sets in parallel (over 100 symbolic inputs) for the largest ISCAS benchmark circuits, using 96Mbytes of memory.

We present an algorithm for extracting a disjunctive decomposition from the BDD representation of F. The output of the algorithm is a multiple-level netlist exposing the hierarchical decomposition structure of the function. The algorithm has theoretical quadratic complexity in the size of the input BDD. Experimentally, we were able to decompose most synthesis benchmarks in less than one second of CPU time, and to report on the decomposability of several complex ISCAS combinational benchmarks. We found the final netlist to be often close to the output of more complex dedicated optimization tools.

Nondeterministic finite-state machines (NFSM's) are a powerful tool for specifying the desired behavior of a sequential system along with its degrees of freedom. Moreover, nondeterministic machines arise naturally when considering the optimization problem of interacting synchronous circuits or deterministic finite-state machines. Yet, NFSM's have been considered only recently in the literature. In this paper, we present algorithms for synthesizing a minimum state implementation of a specification NFSM. The algorithm is a generalization of the classical method for incompletely specified machines, with several modifications. We also introduce the notion of equivalence between compatibility classes and a novel formulation of the closure problem to eliminate unnecessary classes and implications, so as to speed up substantially the search of the optimum solution. A novel BDD-based implementation technique is also presented, which avoids the explicit representation of the transition relation of the original NFSM.

In this paper we introduce a nondeterministic counterpart to Reduced, Ordered Binary Decision Diagrams for the representation and manipulation of logic functions. ROBDDs are conceptually related to deterministic finite automata (DFA), accepting the language formed by the minterms of a function. This analogy suggests the use of nondeterministic devices as language recognizers. Unlike ROBDDs, the diagrams introduced in this paper allow multiple outgoing edges with the same label. By suitably restricting the degree of nondeterminism, we still obtain a canonical form for logic functions. Using PADs, we are able to reduce the memory occupation with respect to traditional ROBDDs for several benchmark functions. Moreover the analysis of the PAD graphs allowed us to sometimes identify new and better variable ordering for several benchmark circuits.

The Multi-Level Decomposition Diagrams (MLDDs) of this paper are a canonical representation of Boolean functions expliciting disjoint-support decompositions. MLDDs allow the reduction of memory occupation with respect to traditional ROBDDs by decomposing logic functions recursively into simpler-and more sharable-blocks. The representation is less sensitive to variable ordering, and because of this property, analysis of the MLDD graphs allows at times the identification of better variable orderings. The identification of more terminal cases by Boolean algebra techniques makes it possible to compensate the additional-small-CPU time required to identify the disjoint-support decomposition. We expect the properties of MLDDs to be useful in several contexts, most notably logic synthesis, technology mapping, and sequential hardware verification.

Current approaches to self test consist of adding hardware to the already synthesized circuits to transform them into autonomous finite state machines. If the circuit's own function is used for test generation and or data compression, then the fault coverage and aliasing properties have to be obtained by simulation. In this paper, we give a function-level specification for the self-test problem. In the self-test mode, all primary inputs and outputs are latched. The circuit behaves as an autonomous finite-state machine, which executes an Euler walk of all states. Thus, each state is visited exactly once, with all states forming a closed path in the state transition graph of the test machine. This function is embedded in the high-level description of the given finite state machine. The self-test hardware thus undergoes the same optimization process as the machine hardware, with a chance of better area/timing optimization. Up to 100% fault coverage against all single/multiple faults can be achieved if the appropriate synthesis/optimization tools are used. On completion of self-test the signature, consisting of the states of all flip-flops, is shown to have an aliasing probability 2/sup -m/ when the circuit has m flip-flops and the fault corrupts a single state-transition.

We introduce a framework for synthesis of behavioral models in which design information is represented using an automaton model. This model offers the advantage of supporting different constraints (e.g., timing, resource, synchronization, etc.) with a uniform formalism. The set of all feasible execution traces (schedules) is constructed and traversed using efficient BDD-based implicit state-traversal techniques. As an application example of this formalism, we present a novel scheduling/control-generation algorithm under environmental constraints where both the design and constraints are represented using automata. We present an algorithm that generates a minimum-latency schedule and a control unit representation. This approach is able to exploit degrees of freedom among interacting components of a multimodule system during scheduling, and is well suited for system-level design, where component encapsulation and interfacing are important.

In this paper we present a new approach to the design of circuits with special properties with regards to internal faults, such as self-checking and fault-tolerant circuits. The approach is based on introducing a minimal amount of redundancy during a multilevel logic optimization process. In this process, we take advantage of the degrees of freedom associated with internal don't care conditions, in order to minimize the amount of redundancy needed to achieve the desired fault-handling capabilities. Experimental results on several benchmark circuits are presented. They compare very favourably with traditional implementations based on topological augmentation rules.

This paper presents new algorithms for evaluating the reliability of fault-tolerant combinational logic circuits. In order to model the effects of multiple faults on circuit functionality, we use fault indicators as control variables. We use BDD-based symbolic simulation to avoid the explicit enumeration of faults. We present experimental results on fault-tolerant implementations of several mcnc benchmark circuits. They show that undetectable multiple faults have a large impact on the reliability of fault-tolerant circuits.

This paper presents a set of new techniques for the optimization of multiple-level combinational Boolean networks. We describe first a technique based upon the selection of appropriate multiple-output subnetworks (consisting of so-called compatible gates) whose local functions can be optimized simultaneously. We then generalize the method to optimize larger and more arbitrary subsets of gates, called unate subsets. Because simultaneous optimization of local functions can take place, our methods are more powerful and general than Boolean optimization methods using don't cares, where only single-gate optimization can be performed. In addition, our methods represent a more efficient alternative to Boolean relations-based optimization procedures because the problem can be modeled by a unate covering problem instead of the more difficult binate covering problem. The method is implemented in program ACHILLES and compares favorably to SIS.>

In this paper we present a method for modeling don't cares at high-level in a form that can be used by sequential logic synthesis. Behavior is specified by a set of concurrent, interacting processes. Each process is described formally by its set of execution traces and represented by an /spl omega/-automaton. This type of specification is formally precise and allows the inclusion of don't cares by allowing multiple execution traces for a given input. Moreover, it allows us to cast the synthesis problem into a language containment problem, and to provide a formal description of these don't cares. We have developed a prototype synthesis system based on this framework, targeting the synthesis of the control portion of a circuit. Starting from a hardware description language Hardware, a specification is expressed in terms of a set of interconnected /spl omega/-automata. We demonstrate the feasibility of the approach by showing the possibility of traversing the state space of the specification automata.>

Abstract- Thts paper prmenta a set of new teelmiques for the nptimtzattmr of multiple-level combtnattorud Boolean networks. Such teehntquea are breed on a temporary tmnsfonnatlon of the networ& tnto an internally unste one. We descrtbe tirat a teebnique baaed upon the seleetion of appropriate multiple-output subnetwo~s (consisting of s~c.slled comprztible gates) whose local functions can be opthntzed sttmdtaneoualy. We then generalize the method to larger subsets of tmate gates. Beeauae shntdtaneoua opttmizatton of local functions ean take place, our methods are more powerful and general than Boolean optimization methods using don t cares, where only single-gate opti. ndzatton am be performed. In addttton, our methods rvpmaent a more efficient alternative to Boolean rvlations-b=d opttndzation procedures beeauae the problem can be mndeled by a mate covertng problem tnstead of the more difficult binate eoverhtg problem. The method ts implemented in program achilks and compares favorably to ~S. 1

A unified framework for the specification and computation of don't care conditions for combinational and synchronous multiple-level digital circuits is presented. Circuits are characterized in terms of graphs, logic functions and don't care conditions induced by the external and internal interconnections. The replacement of a gate in a synchronous logic network is modeled by a perturbation of the corresponding logic function, and it is shown that the don't care conditions for the gate optimization represent the bound on this perturbation. Algorithms to compute such don't care conditions in both the combinational and synchronous case are presented. The implementation of the algorithms and the experimental results are discussed.>

The authors present two methods for computing the fault detection probabilities in combinational networks. The methods provide a deeper insight into the effects of signal correlations caused by multiple fan-out reconvergencies and can be used in testability analysis to predict the fault coverage of pseudorandom patterns. The performances of these algorithms have been tested on significant benchmarks and compare favorably with those of previous procedures.>

The authors present a theoretical investigation of the aliasing error probability (AEP) in signature analysis testing by means of linear finite state machines (LFSMs). The equations of the resulting Markov chain model of the LFSM are solved to determine an exact expression of the AEP as a function of the main LFSM features and of the relevant parameters of the testing environment. This expression is used to prove criteria for the synthesis of LFSMs with minimum asymptotic and transient AEP. A fundamental lower bound on the AEP is presented, which represents the performance limit of any LFSM with respect to aliasing minimization. It is shown that the AEP in machines realizing counters mod 2/sup k/-1 is the closest to such a bound, in particular periodically reaching it.>

The authors present a novel technique to study the detection of non-stuck-at faults in CMOS circuits. Gate-level models of CMOS faults not yet adequately covered in the literature are developed. Suitable models for transistor stuck-open and stuck-on, gate-drain shorts, and bridgings are implemented in a fault simulator. Results obtained with typical circuits are presented and discussed to analyze the influence of circuit architecture and type of test vector (deterministic or pseudorandom) on the coverage of non-stuck-at faults. The following general conclusions are drawn from these results: (1) shorts between transistor gate and drain are adequately detected by stuck-at oriented test patterns, and, hence, they do not represent a significant problem in IC testing: (2) the coverage of transistors stuck-open is significantly dependent on the test pattern generation method used; (3) the detectability of bridgings depends strongly on the circuit topology; and (4) the indirect coverage of transistors stuck-on is inadequate, essentially because a large number of them are undetectable.>

An algorithm is presented that computes exact or approximate observability don't care (ODC) sets for a multiple-level combinatorial network. The proposed algorithms are efficient because they use only local information. A method for deriving the equivalence classes of a Boolean relation from the ODC sets is then proposed. Experimental results on computing ODC sets are reported.>

An investigation of the properties of multiple input shift registers for signature analysis is presented. The assumption of independent errors at the register inputs has been used to model the register behavior as a Markov process whose equations have been solved to obtain the exact dependence of aliasing probabilities as a function of test length, input error probabilities, and feedback structure. Some unique featured of maximum-length registers are proven. Accurate simplified expressions of aliasing probability are derived for use as tools in the evaluation of the coverage.>

Two methods for the calculation of fault detection probabilities in combinational networks are presented. These methods provide a better accuracy than existing algorithms and a deeper insight into the effects of first order correlations to multiple fan-out reconvergencies. These techniques have been applied to standard benchmarks as well as to a few commercial circuits and have shown to provide a significant improvement compared with existing methods with minimal drawbacks in terms of required computing resources.>

Novel design-for-testability schemes are suggested to improve the detectability of transistor stuck-on faults, bridgings, and gate oxide shorts in CMOS digital circuits, with limited extra hardware and minimum degradation of circuit performance. One of the techniques makes analog faults detectable by observing the circuit outputs just as for stuck-ats. Also described is a technique in which the gates are modified with the insertion of n-channel FETs whose drains are the input of a ratioed NOR testing logic realized with n-channel drivers and a single resistive p-channel pull-up device.>

Exact expressions for the aliasing error probability in multiple-input shift register for signature analysis testing are derived and used to obtain criteria for the optimal synthesis of signature registers. The register behavior is modeled under the assumption of statistical independence of error vectors from the circuit under test (CUT). A general solution to the resulting Markov chain is presented on the basis of an original coding theory technique that clarifies the effect of the major register features, as well as of the correlations among the CUT output bits. It is then possible to analyze in detail the most important design issues, such as the choice of the feedback polynomial and of the register optimal structure.>

The Markov chain model of linear feedback shift-registers (LFSRs) for signature analysis testing is analytically solved to obtain the exact expression of the aliasing error probability as a function of test length, error probability, and the structure of the feedback network. The dependence on feedback configuration is explored in depth, and it is proven that maximum-length LFSRs have the best performances with respect to aliasing, regardless of the particular structure of their feedback network. Simplified expressions of aliasing probability are also derived for use as practical tools to design LFSRs for IC signature analysis testing, and a heuristic criterion is given for the identification of peaks in aliasing probability.>

The authors present an accurate model of aliasing probability in signature analysis testing, based on the assumption of independent error bits, that makes it possible to treat the statistical behavior of the register as a Markov process. A proof is given that minimum-hardware registers realizing maximal counting sequences represent optimal choices for aliasing minimization. Exact as well as simplified expressions of aliasing probability have been derived, and a criterion for the identification of maximal aliasing conditions is presented to be used as a tool for the choice of optimal test length.>