Automatic test generation using quadratic 0-1 programming

We recently proposed an unconventional digital circuit modeling technique and formulated test generation as an energy minimization problem [7]. Although energy minimization is as hard as test generation, the new approach has two advantages. Since the circuit function is mathematically expressed, operations research techniques like linear and non-linear programming can be applied to test generation. The non-causal form of the model makes parallel processing possible. The energy function E, a quadratic 0-1 function, is split into two sub-functions, a homogeneous posiform and an inhomogeneous posiform. The minimum of E is the sum of the minima of the two sub-functions, each having a minimum value of 0. We obtain a minimizing point of the homogeneous posiform, in time complexity that is linear in the number of sub-function terms, and check if the other sub-function becomes 0. When both become 0, we have a test vector. We discuss several easily parallelizable speedup techniques using the transitive closure and other graph properties. Preliminary results on combinational circuits confirm the feasibility of this technique.