The authors propose a novel linear-time algorithm for identifying, in a large combinatorial circuit, a large set of faults that are undetectable by a given test vector. Although this so-called X-algorithm does not identify all the undetectable faults, empirical evidence is offered to show that the reduction in the number of remaining faults to be simulated is significant. The algorithm is intended as a simple, fast preprocessing step to be performed after a test vector has been generated, but before the (often lengthy) process of fault simulation begins. The empirical results indicate that the X-algorithm is both useful (indicated by the utility factor) and good (indicated by the effectiveness factor). It provides as much as a 50% reduction in the number of faults that need to be simulated. Moreover, the algorithm seems to identify a large fraction of the undetectable faults. >

The authors develop a formal group-theoretic model, called the Cayley graph model, for designing, analyzing, and improving such networks. They show that this model is universal and demonstrate how interconnection networks can be concisely represented in this model. It is shown that this model enables the authors to design networks based on representations of finite groups. They can then analyze these networks by interpreting the group-theoretic structure graph theoretically, Using these ideas, and motivated by certain well-known combinatorial problems, they develop two classes of networks called star graphs and pancake graphs. These networks are shown to have better performance than previous networks.>

This paper investigates group graphs as a source of interconnection networks. It is shown that while these graphs possess many properties desirable in all interconnection networks, their diversity allows the generation of interconnection networks which may be optimized with regard to a variety of specific parameters. Techniques are described for generating, combining, and analyzing these graphs with respect to their order, diameter, fault tolerance, etc. A theorem is derived which shows that a large important class of group graphs are optimally fault tolerant. A number of examples are included.

Most NP-completeness results for test generation problems involve a reduction to the redundancy problem, which explicitly encodes the satisfiability problem. In this correspondence we investigate the complexity of a more modest problem-that of estimating the size of a test set under the constraint that the circuit is irredundant. We show that even this constrained problem is NP-hard in the strong sense.

This paper describes a method for defining, analyzing, testing, and implementing large digital functions by means of a binary decision diagram. This diagram provides a complete, concise, "implementation-free" description of the digital functions involved. Methods are described for deriving these diagrams and examples are given for a number of basic combinational and sequential devices. Techniques are then outlined for using the diagrams to analyze the functions involved, for test generation, and for obtaining various implementations. It is shown that the diagrams are especially suited for processing by a computer. Finally, methods are described for introducing inversion and for directly "interconnecting" diagrams to define still larger functions. An example of the carry look-ahead adder is included.

This paper describes a logic system specifically designed for fault test generation. The system allows the user to impose a set of initial constraints on the elements of a logic network by indicating those values which an element may (or may not) assume for the test under consideration. He can be as vague or as specific as he wants in imposing these constraints. A set of logic tables is then used to automatically propagate the effects of these constraints throughout the network. As a result of this logic propagtion, the necessary values of the elements in the network become much more precisely (if not completely) defined. The tables also indicate whether or not the generated test (which may include a number of unspecified values) is sufficient to detect the given fault. If several different tests will suffice, the choices remaining are clearly indicated. In the case of a redundant lead (untestable fault), propagation through the tables automatically results in a logical inconsistency.

A method is presented for converting problems in fault diagnosis into ones involving coloring (labeling) the nodes of a graph. It is shown that many concepts and results of graph theory have direct counterparts in fault diagnosis. Specific fault diagnosis problems examined include exercising tests, fanout free networks, test point insertion, sensitized paths, and fault test generation. A number of examples are included.

This paper examines the problem of finding a single universal test set that will test any of a variety of different implementations of a given switching function. It is shown that, for AND/OR networks, universal test sets may be found that detect not only all single faults but all multiple faults as well. The minimality and size of these sets are examined and their derivation for incomplete functions is described.

A rectangular logic array is described that can realize any combinational switching function. Straightforward analysis and synthesis procedures are described and the realizations of a number of special functions are given. These include threshold functions, parity functions, symmetric functions, and universal logic functions. Other properties of the array which are examined include diagnostic procedures, isolating defective cells, bounds on the array size, and possible implementations of the basic cell.

One of the most important tasks of a present day design automation system is the packaging of logic networks. Typically this process follows three steps:

Abstract—Given a set of n input variables, let D(n) denote the smallest integer y such that n2y. It is shown that the complete set of input variables may be inverted using just D(n) inverters and n+D(n) positive-weight threshold gates.

A diagrammatic approach to the problem of synthesizing multilevel logic functions is presented. It has the advantage of giving a visual interpretation to such abstract concepts as fan-in, levels of logic, decomposition, and two-level forms.

The computer organization described here is an extension of a concept of Leondes and Rubinoff [1]. The original machine consisted of a drum store and a single processor capable of sequencing its access from one track (array column) to another at the end of each drum revolution. In this way the system could process one iteration of a Laplace equation in n-drum revolutions, where n is the number of columns of the array.

This paper describes a method for synthesizing a switching function directly from its: ruth table. A switching function is defined as any mapping of a set of binary input combinations onto 0 and 1. Hence, the procedures apply equally well to the don't care cases. The method rests on the concept alogically passive function (LPF). Roughly speaking, an LPF is a truth table which can be realized with only AND and OR gates-no inverters. Techniques are described for 1) making a function logically passive, 2) eliminating rows and columns from the truth table of an LPF, 3) synthesizing an LPF in a two-level irredundant form, 4) expanding LPF's and 5) synthesizing LPF's with 3-input majority gates. The underlying methods are quite straightforward and appear to be particularly well suited for mechanization on a digital computer.