A distributed self-diagnosis algorithm for VLSI mesh arrays with small clusters of faults is presented. It allows only fault-free cells to make decisions and to propagate diagnosis results. Its time complexity is constant with respect to the number of processors. The diagnosability is proportional to the array size.>

The authors present a built-in self-test and diagnosis scheme for detecting and locating the faulty cells in a tree array. Since the signatures of all cells are generated simultaneously (i.e., parallel testing), the time required for the signature generating stage is constant, independent of the array size. Each cell (processing element) generates pseudorandom test patterns and compresses test responses into a signature. By comparing signatures, the signature for the fault-free processor is found and used to locate faulty processors. For arrays with distributed faults, a tree array is partitioned into subtrees on which the diagnosis algorithm is applied in parallel. The time complexity of the diagnosis algorithm is derived.>

Reconfiguration schemes for replacing faulty cells (processing elements) with spare cells are introduced for massive parallel rectangular mesh array processors with fine-grained cells. The authors introduce the concept of two-level redundancy as an effective way of using redundant units to reduce the complexity of reconfiguration control circuitry, to limit the length of connecting wires after reconfiguration, and to increase the manufacturing yield and the operation reliability. An optimization technique for allocating the redundant cells into both levels is presented. The operational reliability and manufacturing yield of arrays with two-level redundancy are presented. The yield estimation problem is modeled by an occupancy problem in classical combinatorial analysis. Both distributed and clustered defects are taken into consideration in the yield estimation.>

The concepts of grey, white, and black systems are formally introduced and developed into logic testing area, i.e. the area of error detection and fault isolation, to find a direction to establish more efficient test schemes for testing digital systems at a reasonable cost. A probabilistic isolation strategy realized by a heuristic and decision-making algorithm is presented to isolate faults in grey systems efficiently in terms of computation space and time.>

Novel concepts of designs for diagnosability and reliability are defined and developed. A diagnosable design of VLSI system is presented, in which fault isolation is realized by minimal additional hardware instead of traditional software diagnostic procedures such that the computation space and time for fault isolation are saved. The presented fault-tolerant design uses online fault detection and isolation techniques, yields higher reliability with minimized hardware overhead of no more than 125% as opposed to over 200% in classical redundancy fault-tolerant designs. Using this scheme, the ability to isolate intermittent faults is a significant improvement over existing fault isolation methods because faults could be isolated right after they are detected.>

A method is presented for functional testing of microprocessors. First, a control fault model at the RTL (register transfer language) level is developed. Based on this model, the authors establish testing requirements for control faults. They present two test procedures to verify the write and read sequences, and use the write and read sequences to test each instruction in the microprocessor. By utilizing k-out-of-m codes, they use fewer tests to cover more faults, thereby reducing the test generation time.>

Recovery procedures involving time redundancy in the form of instruction retries and program rollbacks have proved to be very effective against transient failures in computer systems. A class of such recovery procedures is presented and analyzed here, and the parameters of each procedure are determined so that the system's operation is optimized. These procedures are then compared in order to select the most appropriate one for given system parameters.

The testing of bridging faults (short circuits) has become increasingly important with the increasing density in VLSI (very large scale integration) chips. Yet very little work has been done in this area. In this correspondence, based on a two-state sequential machine model, we present the conditions for a circuit with feedback bridgings to oscillate and to exhibit stable sequential behavior. It is shown that only two test patterns are sufficient to detect feedback bridging faults between input and output lines of a general combinational network. We derive a simple equation to generate test patterns for detecting feedback bridging faults among internal lines of a general combinational network.

We present a new algorithm for functional test generation of VLSI systems. This algorithm for functional test generation for each testable register-transfer (RT) level fault defined in our established fault model. The technique developed is appropriate for test generation in top-down Computer-Aided Design process. The development of the algorithm is based on two foundations: the RT-level fault model and symbolic execution technique. A well-defined RT-language for the functional representation of a digital system is described. Based on this language, the RT-level fault modeling and fault collapsing analysis are performed. The fault model is established to lay an analytical foundation for the investigation of faulty behavior among RT-level fault types. The RT-level symbolic execution technique is used to derive test patterns during test generation. Major problem areas are defined and appropriate solutions are presented. The whole test generation process is divided into three stages: preprocess, the S-algorithm, and post-process. "Divide and conquer" principle is used throughout the test generation process for systematic problem solving. The S-algorithm is the heart of the overall algorithm. It performs test pattern generation based on the reduced fault model using machine symbolic execution. This test generation algorithm has been implemented in PASCAL on IBM 370/168.

Functional testing has become increasingly important due to the advent of VLSI technology. This paper presents a systematic procedure for generating tests for detecting functional faults in digital systems described by the register transfer language. Procedures for testing register decoding, instruction decoding, data transfer, data storage and data manipulation function faults in microprocessors are described step-by-step. Examples are given to illustrate the procedures.

The increasing difficulties in testing large logic networks have generated the need for designing logic networks for testability. Computer algorithms for designing diagnosable metal oxide semiconductor (MOS) networks with and without fan-in, fan-out constraints were described in previous papers by the authors. In this two-part series, we discuss the testing of these designed networks.

Practical solutions have not been obtained from the previous papers addressing the problem of testing intermittent faults in sequential circuits. Existing methods are only suitable for small sequential circuits. This correspondence presents a new technique to design test-experiments for intermittent faults which can conveniently be used for relatively more complex synchronous sequential circuits.

While significant results are available which allow estimation of reliability measure for systems with permanent faults, no generally applicable results are available for intermittent (transient) faults. Methods are presented here which allow reliability evaluation for systems with both intermittent and permanent faults. Two reliability measures, instantaneous and durational reliabilities, are defined and methods to compute them are given. Computed results for the durational reliability for various redundancy schemes are compared.

Due to the advances in the integrated circuit technology, there is an increasing importance in testing bridging (short circuit) failures in digital networks. Unfortunately, very little work has been done in this area. This paper presents the schemes for the detection of feedback bridgings between the inputs and outputs through the observation of oscillation and asynchronous behavior of sequential networks created by bridging faults. The lower and upper bounds on the number of tests for detecting all feedback bridging faults are given. Conditions for the undetectability of input bridgings are given and a method for testing input bridgings is presented. The results are generalized to detect bridging and stuck-at faults in the input and output lines of a multiple-output network. Finally, the complete test sets are given for detecting input, output and feedback bridgings as well as stuck-at faults at the input and output pins of the standard integrated circuit chips including shift registers, counters, decoders, multiplexers, adders/subtracters, multipliers, dividers and RAM.

The study of short circuits between conducting paths (bridging faults) has become increasingly important. Yet very little work has been done in this area. In this paper, conditions for feedback bridging (short circuit) faults to generate oscillation and asynchronous behavior are given for short circuits among input lines and the primary output. The lower and upper bounds on the number of tests for detecting all feedback bridging faults are given. Necessary and sufficient conditions for the undetectability of input bridgings are presented. It is found that any test detecting single bridging fault e will also detect all multiple bridgings containing e. Complete test sets for locating either all input or all feedback bridgings of any multiplicities for networks implementing several classes of functions are given.

This paper deals with a method for designing a digital system which will remain operational in spite of the failure of some of its components. A scheme and its realization are presented for automatically reconfiguring a 5MR (five modular redundancy system or 5-input majority voting system) into a triple modular redundancy (TMR) system under a single or double module failures. The scheme can tolerate a double fault followed by a single fault which can neither be tolerated by a 5MR nor by a hybrid redundancy system with a TMR core. It uses no spare units and the circuit realization is relatively simple. The modular structure of the logic design for the proposed scheme should make the testing of the system easier. The scheme can be used in both binary and multivalued systems.

It is well known that static redundancy techniques are very efficient against intermittent (transient) faults which constitute a large portion of logic faults in digital systems. However, very little theoretical work has been done in evaluating the reliability of modular redundancy systems which are subject to intermittent malfunction occurrences. In this paper we present a statistical model for intermittent faults and use it to analyze the reliability of NMR systems in mixed intermittent and permanent fault environments.

The goal of this research is to provide software fault tolerance in a real time system. As the first step, this paper presents a scheme which generates estimated data to replace the wrong or unexpected input data of a real time system which accepts highly correlated numerical data as input. Such an estimated data allows a program to continue its operation without interruption. Reliability evaluation of this scheme is given to show that the scheme improves software reliability.

Metal-oxide-semiconductor (MOS) logic elements offer advantages over bipolar logic elements, such as smaller size, complexity, and power consumption, as well as more flexibility and versatility. Since MOS is playing a major role in large-scale integration (LSI), synthesis of MOS networks with a large number of variables is very important.

A continuous-parameter Markov model for intermittent faults in digital systems is presented. This continuous model is more realistic than discrete-parameter models previously presented by other authors. The results obtained using the proposed model can be reduced to those obtained from the previous models, by using appropriate approximations.

This paper examines the problem of detecting single stuck-type faults in multivalued combinational circuits. The algebra employed is the generalized ternary algebra developed by Vranesic, Lee, and Smith. Many of the concepts already developed for fault detection in binary circuits generalized easily to the multivalued case. The special properties of multivalued circuits for this algebra simplifies fault detection. Specifically, this paper introduces the concept of a partially enabled gate, K-paths in combinational circuits and a new notation for multivalued fault detection. In addition, a modified form of the D-algorithm is developed for fault detection in multivalued circuits as well as a δ algorithm for the simplification of multivalued test sets.

This paper deals with the problem of identifying multiple stuck-type hardware failures in combinational switching networks. Our work is an extension of that of Poage, and Bossen and Hong, and we employ the cause-effect equation for representing faulty circuit behavior. We introduce the concept of solving simultaneous equations over check point variables. These check point solutions are studied in detail. From the solutions one can calculate the function realized by a faulty circuit. We outline an on-line testing procedure for constructing a test set for identifying a specific fault in a circuit to within an equivalence class. This procedure eliminates the need for precalculating a fault dictionary, which, in many instances, can be quite advantageous. We also outline how to apply these techniques to the following problems: 1) identifying redundancy; 2) determining the set of faults not detected by an arbitrary test set; and 3) constructing a complete fault dictionary.

Problems of testing switching networks have been with us since the first computer was built and have become more difficult as the technology moved from discrete components to integrated circuits. Consequently, there has been an increasing interest in this area. This book covers methods of deriving efficient tests for different classes of switching circuits.

A systematic approach to the location of a single failure in a combinational logic network is presented. The method utilizes only the required tests and needs no fault table. The structure of the logic network is taken into consideration when selecting the tests to be applied. For tree networks, we start from the gate that generates a primary output and sequentially trace back through the stages of the network according to a fixed set of rules. At each stage we either locate the fault or determine the direction of the trace.

A cubical representation for multivalued switching functions, which is very convenient for digital computer processing, is presented. A p-valued switching function of n variables is represented by an array of cubes. Each cube is composed of a logical co-efficient and n coordinates with each coordinate represented by p bits. A set of operators for multivalued logic design (such as sharp, union, etc.) for manipulating arrays of cubes is defined and used for minimizing multivalued switching functions. The idea of ``compound literals'' is introduced, which yields a realization with less hardware than the existing methods. Algorithms for finding all prime implicants, essential prime implicants, and a near-minimum cover for multivalued switching functions are presented that are suitable for both computer and hand execution. These algorithms have been programmed in Fortran.

The relationship between multivalued switching algebra and Boolean algebra is presented by introducing different definitions for the complements of multivalued variables. For every definition introduced, the paper points out which Boolean algebra theorems are valid for multivalued cases, which are invalid, and gives proofs to substantiate the claim. It is shown that DeMorgan's theorem holds for all four definitions of complement given in this paper. One definition allows us to map the multivalued variables into binary variables. Under this definition, all axioms and theorems of Boolean algebra are satisfied and can be used for minimization of any multivalued switching function f. Illustrative examples for minimizing f and its complement f are given.

A straightforward efficient computer algorithm for synthesizing multiple-output NAND (NOR) switching networks is presented which takes practical fan-in and fan-out limitations of logic gates into account. The algorithm is highly iterative and hence is very suitable for realizing large-size switching functions by a digital computer. The algorithm has been programmed in Fortran and a great deal of statistical data has been obtained to demonstrate its efficiency in terms of gate count as well as computing time. It is also efficient for hand execution