This paper presents new results for diagnosing (detection and location) multistage interconnection networks (MINs) in the presence of multiple faults. Initially, it is proved that the lower bound in the number of tests for multiple fault diagnosis (independent of the assumed fault model for the MIN) is 2/spl times/log/sub 2/N, where N is the number of inputs/outputs of the network. A new fault model is introduced; this fault model is applicable to interconnection networks implemented using CMOS technology. The characterization for diagnosing stuck-open faults is presented.

This paper presents new algorithms for yield enhancement of redundant memories. These algorithms are based on the technique of spare cutting for a redundant memory chip in which repair is implemented by row/column deletion. Different approaches are proposed: some of these approaches are based on a fully exhaustive process, while others try to heuristically reduce the computational overhead involved in determining the repair-solution.

This paper presents new results and graph algorithms for the automatic testing of protocols using “unique input/output” (UIO) sequences. UIO sequences can be efficiently employed in checking conformance of protocols to their specifications by using transition testing. The optimization of the test sequence is based on finding the rural Chinese postman tour, of the state transition diagram of a finite state machine (FSM). The process of conformance test generation using a touring algorithm is valid provided that certain connectivity properties of the graph are present. This implies that a weakly connected graph must be constructed. It is possible that this connectivity condition may not be met when multiple UIO sequences are used even if the reset capability and/or the self-loop properties are present. The “weakly connected graph problem” consists of finding an edge-induced subgraph of the FSM which is still weakly connected when multiple UIO sequences are used. The “multiple UIO tour minimization problem” addresses the assignment of edges to UIO sequences for minimizing the degree of the directed UIO graph. This process may not also minimize the length of the tour. The above two problems, left open in previous papers, are solved in this paper. It is proved that by appropriately changing the original assignment graph and using network flow techniques with a new UIO generation process referred to as chaining, efficient solutions can be provided. The theoretical approaches behind the solution to these problems are fully characterized.

This paper presents a new structural approach for test generation and diagnosis of interconnects (such as wiring networks). The proposed technique is based on computational geometry by considering the physical adjacencies of the nets in the layout. This information is used by a sweeping line technique for generating the test vectors. A realistic fault model in which nets can be bridged only if they are physically adjacent, is proposed. The proposed approach generates a set of initial local vectors for testing all the nets at the inputs. A different set of local vectors is then, generated by sweeping the layout at every point where two nets may intersect. The set of local vectors is generally sparse. So, a compaction algorithm is proposed for generating the final set. The proposed approach has an execution time of O((p+k) log p) for generating the local tests, where p is the maximum number of segments in the nets and k is the number of possible intersection points. It is proved that the problem of generating the minimum number of test vectors by compaction is NP-complete, but simulation results show that the proposed heuristic criteria are very efficient for a practical application. The extension of the proposed approach to other fault models and to other routing schemes (as applicable to PCB and VLSI) is presented.

This paper presents a new approach for finding the Unique Input/Output (UIO) sequences of the states in of a finite state machine (FSM). The proposed approach utilizes a different data structure for organizing the search tree. This reduces the amount of time and memory space required for finding the UIO sequences of all states of a FSM. Simulation results on sample benchmark FSMs from MCNC and commercially available protocols are provided.>

Various new classes of unique input/output (UIO) sequences for verification and validation (conformance testing) of protocols modeled as finite state machines (FSMs) are presented. The proposed sequences are referred to as adaptive because test sequence generation is not a mere concatenation of test subsequences for all edges of the FSM, but rather subsequences are concatenated using appropriate conditions in the UIO sequence for length minimization and no degradation of fault coverage.>

The fault coverage of testing protocols using unique input/output (UIO) sequences is analyzed. UIO sequences can be efficiently employed in checking the conformance specifications of protocols by using transition testing. The test sequence is found using the rural Chinese postman tour algorithm. A comprehensive fault model is developed, and analytical expressions are given for the fault coverage. The conditions for undetectability are analyzed, and a new algorithm is proposed. Simulation results and illustrative examples are presented. Overhead issues are discussed, and significant improvements are shown for achieving 100% fault coverage. The major advantage of the proposed approach is that it provides the theoretical basis for fault coverage evaluation of protocol testing using UIO sequences.>

Automatic generation of conformance test sequences for communication protocols by means of unique input/output (UIO) sequences is addressed. It is shown that if multiple minimum-length UIO sequences are computed for each state of the finite-state-machine (FSM) specification, then the length of the resulting test sequence is significantly reduced without an appreciable increase in the time needed to compute the sequence. An algorithm for assignment of the multiple UIO sequences is given. This algorithm, which is based on network flow, is polynomial in the number of states and transitions of the FSM and is effective in reducing the overall length of the test sequence.>

Two approaches for the repair of large random access memory (RAM) devices in which redundant rows and columns are added as spares are presented. These devices, referred to as redundant RAMs, are repaired to achieve acceptable yield at manufacturing and production times. The first approach, the faulty line covering technique, is a refinement of the fault-driven approach. This approach finds the optimal repair solution within a smaller number of iterations than the fault-driven algorithm. The second approach exploits a heuristic criterion in the generation of the repair solution. This heuristic criterion permits a fast repair. The criterion is based on the calculation of efficient coefficients for the rows and columns of the memory. Simulation results are presented. Comparison of the proposed heuristic approaches with the fully exhaustive approach shows that repair can be accomplished in most cases. A considerable reduction in processing and complexity (number of records generated in the repair process for finding the optimal repair solution) is accomplished.>

The authors present the basic structure of a testable and repairable programmable logic array (PLA) and the design modifications which are required for a full diagnosis and yield enhancement. The testing process is fully analyzed, and the conditions for diagnosis are presented. It is proved that identification in the presence of multiple (crosspoint, stuck-at, and bridging) faults is possible with high coverage. The criteria which permit diagnosis are based on a hierarchical organization of the testing process; significant improvements over previous redundant structures can be achieved. This results in a compact structure with a homogeneous layout which has been evaluated with respect to area overhead for VLSI implementation. Simulation results for benchmark devices are presented. These suggest that an efficient repair of VLSI PLAs for yield enhancement can be achieved.>