An Effective Test Generation Algorithm for Combinational Circuits

In this paper,an analysis of backtrack behavior in PODEM(the test generation algorithmfor combinational circuits presented by P.Goel)is given.It is pointed out that there are stillmany unnecessary backtracks in PODEM on some occasions.A new test generation algorithmnamed IPODEM is therefore proposed in this paper.IPODEM is an improvement over PODEMwith emphasis on backtrack of decision tree.A new backtrack approach is developed in thisalgorithm.It is shown that only O(j)of backtrack consumption is needed in IPODEMcompared with O(2~j)in PODEM on certain occasions.Experiments pointed out that theseoccasions appear in not small proportion.Several other techniques are applied in IPODEM toaccelerate test generation process in other aspects.Experimental results demonstrated thatIPODEM is faster than PODEM for both hard-testing and easy-testing single stuck fault,andthat the former has higher test coverage than the latter.