Fault testing random-pattern-resistant circuits requires that BIST (built-in self-test) techniques generate large numbers of pseudorandom patterns. To shorten these long test lengths, this study describes a cellular automata-based method that efficiently generates weighted pseudorandom BIST patterns. This structure, called a weighted cellular automaton (WCA), uses no external weighting logic. The design algorithm MWCARGO combines generation of the necessary weight sets and design of the WCA. In this study, WCA pattern generators designed by MWCARGO achieved 100 percent coverage of testable stuck-at faults for benchmark circuits with random-pattern-resistant faults. The WCA applies complete tests much faster than existing test-per-scan techniques. At the same time, the hardware overhead of WCA proves to be competitive with that of current test-per-clock schemes.

This paper presents a test per clock BIST technique that uses multiple idler register segments with selective bit-fixing driven by multiple biased pseudorandom pattern generators to provide 100% fault coverage of detectable single stuck-at faults. The technique is particularly effective for random pattern resistant circuits. A BIST architecture that supports this technique, and a design tool (MFBIST) that implements the technique are presented. The amount of hardware overhead is controlled by user-specified parameters and can meet varying design specifications. Results and comparisons with prior techniques are presented for combinational benchmarks and combinational versions of sequential benchmark circuits. To better evaluate hardware overhead, automatic CMOS layouts were performed for the benchmark circuits. The results show that the additional area overhead, relative to that required by pseudorandom test per clock designs, is small.

In this paper we present a new test per clock BIST technique that provides 100% fault coverage of detectable single stuck-at faults for random pattern resistant circuits with low test application time and limited hardware overhead. The technique uses selective bit-fixing plus biased pseudorandom patterns and is referred to as fixed-biased pseudorandom BIST. An automatic design tool (FBIST) specifies the necessary information for implementation of the BIST hardware. The amount of hardware overhead introduced is controlled by user specified parameters and can therefore meet varying design specifications. Since the proposed technique relies on bit-fixing, we present a new scan cell which supports bit-fixing. Results are presented for combinational benchmark circuits and comparisons made with prior techniques with respect to test application time and hardware overhead.

Presents a complete design method for inhomogeneous cellular automata capable of generating BIST patterns with multiple weight sets at a test per clock rate. The method achieves 100% stuck-at fault coverage of detectable faults for almost all combinational benchmark circuits having random pattern resistant faults. The authors also present data showing the overall speed up relative to test per scan methods.>

An incremental ATPG system for combinational circuits, ICAT, is presented. ICAT uses the hypothesis that, if a circuit modification is small, the old tests for the circuit before modification can provide crucial information to speed up generation of new tests for the modified circuit. Four incremental techniques in ICAT maximally utilize information from the old tests with minimal storage requirements. The four incremental techniques are augmented with a fast, effective deterministic test generation algorithm in ICAT. The experimental results from the evaluation of three different classes of modifications to ISCAS circuits show the incremental technique to be efficient and effective.>

The empirical testability difference (ETD) method for selecting flip-flops (FFs) achieved results superior to compared methods at the expense of substantial CPU time. The new reverse empirical testability difference (RETD) approach starts from a fully scanned circuit and, through several iterations, drops these FFs from the scan chain that have the least effect on the overall circuit testability. In order to further enhance processing efficiency. relative sequential observability, a new distance measure between FFs, permits multiple FFs to be dropped from the scan chain in a single iteration. RETD maintains the same desirable fault coverage-hardware overhead characteristics as ETD. We compare RETD results for a subset of ISCAS89 circuits with a cycle breaking and depth reduction-based method. The results indicate that RETD, in general, achieves better fault coverage for given hardware overhead. The overall amount of CPU time required to achieve comparable, fault-coverage targeted solutions is also shorter for RETD.>

Weighted random pattern testing methods produce higher fault coverage with shorter test lengths than random pattern testing methods. Here we present the weighted cellular automaton (WCA), an inhomogeneous cellular automaton that generates weighted random patterns on a test per clock basis. The WCA is a complete automaton that contains no external weighting logic and no multiplexers between flip-flop outputs and the circuit under test that add to critical path delays. Since the structure is based on cellular automata there are no complex routing problems. We also give a design algorithm, WCARGO, that automatically generates WCA from an ordered set of weights.>

The authors provide tools for exploring the inherent parallelism introduced by design for testability (DFT) and built-in self-test (BIST) techniques in order to reduce test length. Since the potential for parallel test execution is most apparent at the organization level and DFT and BIST hardware is also often added at that level, the organization level is used as a foundation for the work. A broader modeling foundation that encompasses both dimensions, space and time, of test parallelism is introduced. A set of simple schedulability criteria for concurrent issuing of tests is developed. Effective suboptimum heuristic-based algorithms for scheduling tests on general-purpose high-performance VLSI system implementation are presented. The scheduling algorithms have been implemented and performance results are presented.>

The objective of the partial scan method proposed is to obtain maximum fault coverage for the number of scan elements selected. Empirical testability difference (ETD), a measure of the potential improvement in the overall testability of the circuit, is used to successively select storage elements for scan. ETD is calculated by using testability measures based on empirical evaluation of the circuit with the actual test sequence generator. In addition, ETD focuses on the hard-to-detect faults rather than all faults once such faults are known. The method has been extensively tested with ten of the sequential circuits given by F. Brglez et al. (1989) using the FASTEST provided by T. Kelsey and K. Saluja (1989). The results of these tests indicate that ETD yields on average either 27% of the number of uncovered faults for the same number of scan elements or 21% fewer scan elements for the same fault coverage compared to the other methods studied.>

The HPath algorithm for multiple-path sensitization in hierarchical, multilevel descriptions, which is based on semiregular structures within many VLSI circuits, is discussed. The algorithm which has been derived, implemented, and tested is applicable to circuits which can be described as semiregular and pseudocombinational for performance of testing functions related to test pattern generation, design-for-testability, built-in self-test, and diagnosis. HPath sensitizes the target paths, which may consist of multiple bits, one by one through hierarchically described circuits. Depending on the specification of each path, HPath propagates the path block by block in either the forward or backward direction. HPath is, in fact, a control mechanism which determines which path to sensitize and which block to propagate through. The sensitization is actually done by its two major components, GPath and FPath. GPath is an implicit enumeration algorithm which utilizes symbolic manipulation to achieve multiple-path sensitization for gate-level circuits. FPath is a rule-based subsystem which sensitizes multiple paths for functional-level descriptions through a sequence of rule applications. It is shown that GPath is not as efficient as FPath.>

The authors propose a special class of hierarchy, the sensitizable hierarchy, to handle simultaneously both circuit partitioning and test pattern delivery for pseudoexhaustive BIST (built-in self-test). Instead of developing specialized tools for different cases in an unsensitizable hierarchy, they attempt to reconstructure the hierarchy to make it sensitizable. In order to verify the sensitizability of a hierarchy and restructure an unsensitizable hierarchy, the authors study the characteristics of hierarchical circuits and conclude that there are three usable semiregular properties, namely, the separation of data and control signals, the availability of functional units and functional descriptions, and frequent use of array structure. On the basis of these properties, the following are derived: a structure recognition process to identify the implicit array and functional unit structure; a hierarchical, multilevel, multiple-path sensitization algorithm to sensitize paths for test application and response observation; a restructuring process to obtain a sensitizable hierarchy; and a straightforward procedure for pseudoexhaustive BIST for a sensitizable hierarchy. All of these processes and procedures use a common knowledge base and are integrated by use of a frame-based system implemented with Franz Lisp.>

Testing high-performance VLSI systems containing pipelines and multifunctional units is considered. An efficient heuristic-based algorithm is presented for scheduling tests in systems requiring unequal number of tests (UNT) for the test function. Performance results for an experimental implementation of the algorithm are presented.>

The impact of emerging standards on university research and instruction is addressed. Initially, impact on research, specifically research in testing, is dealt with followed by a discussion of the potential impact on instruction. Before treating each of these areas separately, the current impact of standards on research and instruction in the hardware design area in general are briefly reviewed. Two categories, general standards that affect a significant portion of all designs, and special standards that affect only the design of specific subsystems, are briefly reviewed. These are illustrated by the various standards that have an impact on courses in computer engineering at the University of Wisconsin.>

A powerful suboptimum heuristic for scheduling tests on general-purpose high-performance VLSI system implementations is presented. A simple model that represents a system and its organization, at any level, by a labeled resource allocation graph between test functions and test and system resources was introduced. The resource allocation graph was utilized to produce a scheduling model and a simple schedulability condition. An algorithm based on mechanisms for generating optimum schedules was presented. The algorithm performs a preliminary greedy scan for valid scheduling cycles. The partial scan seeds an iterative improvement procedure which utilizes a controlled incremental departure from local optima to schedule functions that require an equal number of tests. Methods to utilize the algorithm for a general number of tests per function were also outlined. The implementation of an experimental version of the algorithm showed good performance.>

Concurrent off-phase built-in self-test is described, which permits the operation of built-in self-test hardware designed for offline testing concurrently with normal system operations. It takes advantage of the logic dormancy characteristic of designs which use two-phase clocking. This method provides online detection for permanent faults and can be used in conjunction with a time-redundant concurrent test method to detect transient and intermittent as well as permanent faults. Also, the method provides guaranteed self-test for self-checking circuits. Concurrent off-phase BIST requires duplication of storage elements but otherwise makes use of BIST hardware used for noncurrent, offline testing. Also, there may be an associated time penalty which, for the given example of CMOS technology with a symmetric phase clock period of 50 ns, is estimated to be an 11.6% increase in the clock period.>

The test scheduling problem for equal length and unequal length tests for VLSI circuits using built-in self-test (BIST) has been modeled. A hierarchical model for VLSI circuit testing is introduced. The test resource sharing model from C. Kime and K. Saluja (1982) is employed to exploit the potential parallelism. Based on this model, very efficient suboptimum algorithms are proposed for defining test schedules for both the equal length test and unequal length test cases. For the unequal length test case, three different scheduling disciplines are defined, and scheduling algorithms are given for two of the three cases. Data on algorithm performance are presented. The issue of the control of the test schedule is also addressed, and a number of structures are proposed for implementation of control.>

A method is presented for testing digital circuits during normal operation. The resources used to perform online testing are those which are inserted to alleviate the offline testing problem. The offline testing resources are modified so that during system operation they can also observe the normal inputs and outputs of a combinational circuit under test. The normal inputs to the circuit under test are with test vectors in its test set. When a normal input matches a test vector, the circuit output for such an input is typically compressed into a developing signature. When all of the test vectors in the test set have appeared as normal inputs, the signature is read and verified. With this method, the length of time required for all of the test vectors to appear, possibly in some order, among the normal inputs to the circuit under test is of considerable importance.>

Diagnosis of an entire system when known faults are present and diagnosis of particular faults in the system when known faults are present are two diagnosis problems that are relevant to computer systems that are reconfigurable and employ distributed control. These problems are formalized, and a diagnostic model based on a model of Russell and Kime is used to analyze the ability of a system to diagnose all faults and particular faults in the system when some known faults are present.

An abstract model applicable to the use of both diagnostic programs and hardware diagnostic aids in digital systems is presented. The model is capable of dealing with replaceable units having a variety of complexity and is shown in a mathematically rigorous fashion to encompass existing models for diagnosis. A three-level structure for representing faults and a two-level structure for representing tests are employed. Faults, multiple faults, tests, and test results are represented by sets. Relationships between these entities are represented by binary relations and functions.

This paper is concerned with the diagnosis of faulty parts in digital systems, including both the detection and location of such parts. The system model presented in this paper considers two levels: the part level at which detectability and diagnosability are defined, and the fault level at which testing is performed and at which functional units or portions thereof are defined. Parameters are defined and used in determining conditions for t-part detectability, t-part diagnosability without repair, and t-part diagnosability with repair. Several examples are presented with the development of the model and derivation of results. These examples illustrate the advantages and limitations of this model.

A module-level testing approach for combinational networks which employs hardware modification and a simplified test generation procedure is described. The approach is based on a directed graph model for the network derived at the module level. The objectives of the approach are to deal with testing directly at the module level, to use cataloged tests for the modules in the network environment, and to generate a fault detection test set with "good" fault location capability. Networks which consist of single-output modules are treated initially and then the results are extended to networks which consist of multiple-output modules. Hardware modification and test generation procedures are illustrated.

FAULT-TOLERANT computing has been defined as "the ability to execute specified algorithms correctly regardless of hardware failures, total system flaws, or program fallacies" [1]. To the extent that a system falls short of meeting the requirements of this definition, it can be labeled a partially fault-tolerant system [2]. Thus the definition of fault-tolerant computing provides a standard against which to measure all systems having a degree of fault tolerance. In particular, one can classify systems according to: 1), the amount of manual intervention required in performing three basic functions, and 2) the class of faults covered by three basic functions involved in fault tolerance: system validation, fault diagnosis, and fault masking or recovery. The word "fault" here is used to inclusively describe "failures, flaws, and fallacies" in the original definition. The first function is involved in the design and production of the system hardware and software, while the last two functions are embodied in the system itself. Likewise, the first function is directed to handling faults arising from design and production errors, whereas the last two functions are aimed at faults due to random hardware failures.

In the above paper1, the partial Boolean difference is defined and an algorithm for deriving complete minimal test input sequences for single-fault detection is given. In this correspondence, it is shown that the presentation of the algorithm is inadequate with respect to the need for multiple path sensitization. It is further shown that the computational procedure used in footnote 1 does not guarantee minimality of the test set and does not permit the extension to fault location as claimed in the paper.

Diagnosability without fault repair of a digital system containing at most t faults is considered. A system-level diagnostic model defined in an earlier paper [1] is employed. The model is to an extent independent of the means used to implement diagnostic procedures, i.e., whether the tests are accomplished via hardware, software, or combinations thereof. Two parameters, the masking and exposure indices, are defined. Conjoined with the previously defined closure index, the parameters fundamentally characterize the capability for executing valid tests in a multiple-fault environment. Necessary and sufficient conditions for a system to be t-fault diagnosable without repair are derived in terms of these parameters. Examples are presented to illustrate the application of the model for systems close to those encountered in actual practice.

Determination of the detectability and diagnosability of a digital system containing at most t faulty system components is considered. The model employed is to an extent independent of the means used to implement diagnostic procedures, i.e., whether the tests are accomplished via hardware, software, or combinations thereof. A parameter, called the closure index, is defined which characterizes the capability for executing valid tests in the presence of faults. The closure index can be thought of as the size of the smallest potentially undetectable multiple-fault in the system as modeled. On the basis of this parameter, results are presented which permit the determination of t-fault detectability and t-fault diagnosability with repair for the system. Examples are presented to illustrate the application of the model for systems close to those encountered in actual practice.

The set covering problem is considered and an efficient procedure for finding an irredundant cover is presented. For an m × n cover table, the execution time of the procedure is, in the worst case, proportional to mn . Methods are suggested for obtaining alternate irredundant covers based on an initially obtained irredundant cover. The basic cost-independent algorithm is heuristically extended to consider costs so that a reduced-cost irredundant cover can be obtained. A summary of some computational experience is presented, which indicates that the procedure is fast and applicable to large problems.

The definition of the generalized fault table [1] is expanded to cover a representation employing more than one fault q cube per fault pattern. On the basis of this expanded definition and simple concepts from a cover algebra, a new procedure is developed for finding first- and second-order diagnostic resolutions.

The problem of fault detection and diagnosis of irredundant multiple-output combinational networks is discussed from a purely structural viewpoint, i.e., with the functions of the network components essentially ignored. Two structural models for a network are given in the form of labeled directed graphs. Graph theoretic concepts are introduced, and theorems are developed which give necessary conditions and sufficient conditions for the detectability of faults at particular primary outputs based solely on the structure of the network. Procedures are then presented for obtaining the structural diagnostic resolution for both line and logic module faults. Finally, an application, test point placement for increased network maintainability, is considered.

A model for the representation of diagnostic test-fault relationships is presented which provides increased flexibility over previous models and is adaptable to handling large-scale integrated systems. Several forms of the model are given and methods for transforming from one form to another are presented. Procedures are given for assessing the diagnostic capability of the test set and theorems are presented which give necessary and sufficient conditions in terms of the model for diagnosability with and without fault repair. Finally, the model is compared to a number of existing models to demonstrate its flexibility.