An Efficient Algorithm for Calculating Boolean Difference

In this paper we have proposed a method of computing Boolean difference by means of transition operators. This method considerably simplifies the computational complexity. Particularly, when the method is used in the test generation of digital circuits, the Boolean difference can be calculated iteratively from the outputs of gates to their inputs level by level, no matter whether there are reconvergent fanout lines or not. When there are m different paths from a given fault line to the primary output of the circuit, using traditional Boolean difference methods, the result formula will contain 2m?1 product terms, whereas using the method presented in this paper, the result formula will contain onlym product terms. On the other hand, the m product terms are connected by “OR” operators, therefore it is very convenient to generate partial test patterns. We also introduce a method in which partial test patterns along a given path can be generated. The method discussed in this paper have been used in the test generation of the PCBs of several computers and the results were quite satisfactory.