TECHNIQUES FOR REDUCING THE NUMBER OF DECISIONS AND BACKTRACKS IN COMBINATIONAL TEST-GENERATION

Combinational test pattern generation (TPG) is basically a search in a finite state space. In general, the search is performed in a branch-a nd-bound fashion. The branch-and-bound search builds a decision tree u sing two basic operations: decision making and backtracking. The size of the decision tree, and hence the efficiency of the branch-and-bound search, is directly dependent on the number of decisions made. This p aper proposes a set of novel techniques for reducing the number of dec isions and the size of the decision space. These techniques work direc tly on the maximum number of potential ways of justifying a given logi cal assignment. This maximum number is reduced by exploiting the prope rties of prime-and-irredundant covers. These same properties are also used to reduce the number of backtracks by implying a maximum number o f necessary assignments. The reduction of the number of decisions and the identification of a maximum of necessary assignments make the prop osed TPG method highly efficient as demonstrated by experimental resul ts. This paper also proposes a novel combination of prime-and-irredund ant cover extraction and transitive closure computation for a more eff icient TPG process.