A method for reducing the search space in test pattern generation

This paper introduces the new concept of an implying node by which an efficient decision point can be selected. The implying node is a signal line whose value implies the values of the primary inputs. This means that a decision on the implying node is equivalent to several decisions on the primary inputs. As a result, a decision on the implying node is able to induce more implications. This effect causes significant reduction of the search space in test generation. The process of finding the implying node can be combined with the conventional backtrace process. Additionally, a D frontier intercept check is introduced to find necessary assignments for fault propagation. The technique can identify some necessary assignments that the dynamic learning of SOCRATES fails to find. Experimental results using ISCAS benchmark circuits show the efficiency of the proposed method