A method to calculate necessary assignments in algorithmic test pattern generation

The authors present a novel test pattern generation algorithm which uses the concept of necessary assignments to reduce or eliminate backtracking in automatic test pattern generation. Necessary assignments are those which must be made in order to find a test pattern; without them the search is guaranteed to fail. The algorithm is based on the mathematical concept of images and inverse images of set functions. In order to take advantage of formal concepts developed for Boolean algebras, the algorithm uses a 16-valued algebra. It has been used to generate test patterns for all faults in a variety of benchmark circuits. Experimental results indicate that the algorithm is particularly efficient at redundancy identification, which is often a problem for conventional test pattern generation algorithms. The benefits of a 16-valued system are illustrated through examples of faults which are not properly handled by conventional 5- or 9-valued systems