Test generation by Lagrange programming neural network

A neural network approach for test generation of single stuck-at faults in combinational circuits has been proposed by Chakradhar et al. (1991). The network is constructed from the Boolean constraint network of the circuit under test. It is a Hopfield type neural network and its energy function has its global minimal value if the state of the network corresponds to the consistent signal value assignment (solution) of the Boolean constraint network. However this neural network cannot escape from being trapped by local minima which are not the solutions. Nagamatu and Yanaru (1994) proposed a neural network called Lagrange programming neural network with polarized high-order connections (LPPH) for solving the satisfiability problem (SAT). The LPPH is based on first order Lagrangian method. It is proved theoretically that each equilibrium point of the LPPH is a solution of the SAT and vice versa. It is also proved experimentally that the LPPH can find the solution of the SAT efficiently. In this paper, we use the LPPH for solving the SAT of Boolean difference expressions, and investigate the effect of adding clauses which represent the existence of active path from the fault to one of external outputs, and the effect of decay factor of weights of the LPPH