Neural network models and optimization methods for digital testing
Srimat Chakradhar · 1991
We consider the problem of finding tests for detecting failures in logic circuits. The test inputs are applied to the logic circuit so that, in the presence of a fault, the circuit produced an observable faulty response at its outputs. Massively parallel computers present a promising paradigm for computer-aided design (CAD) applications but no effective parallel architecture or algorithm for test generation has been found. This dissertation develops radically new circuit models and algorithms for test generation that can exploit massively parallel computers. We propose a new and unconventional modeling technique for digital circuits. The input and output signal states of a logic gate are related through an energy function such that the minimum energy states correspond to the gate's logic function. There are at least two advantages of this new approach. First, since the function of the circuit is expressed as a mathematical expression, several new techniques can be used to solve problems like test generation. Second, the non-causal form of the model allows the use of parallel processing. We present the mathematical basis for our models and discuss their fundamental properties. Based on these unconventional circuit models, the dissertation presents test generation algorithms that can exploit fine-grain parallel computing, relaxation techniques, quadratic 0-1 programming and graph-theoretic techniques. In addition to its practical value, the proposed test generation formulation leads to interesting theoretical contributions. As a further application of the model, we consider the intractability of the test generation problem. Using the neural network models, we present a new class of circuits in which this problem is solvable in polynomial time. This contribution is especially important since it leads to design styles for easily-testable digital circuits. This contribution of the dissertation provides a possible step toward design for testability of the future. Furthermore, we discuss an application of the neural network models to other NP-complete problems. In particular, we present a new class of linear time solvable quadratic 0-1 programming cases. The significance of this result stems from the fact that quadratic 0-1 programming is useful in solving several practical problems like Boolean satisfiability, traveling salesperson, VLSI layout and others.