AN IMPLICIT ENUMERATION ALGORITHM TO GENERATE TESTS FOR COMBINATIONAL LOGIC CIRCUITS

Abstract

The D-Algorithm (DALG) is shown to be ineffective for the class of combinational logic circuits that is used to implement Error Correction and Translation (ECAT) functions. PODEM (Path-Oriented Decision Making) is a new test generation algorithm for combinational logic circuits. PODEM uses an implicit enumeration approach analogous to that used for solving 0- 1 integer programming problems. It is shown that PODEM is very efficient for ECAT circuits and is significantly more efficient than DALC over the general spectrum of combinational logic circuits. A distinctive feature of PODEM is its simplicity when compared to the D-Algorithm. PODEM is a complete algorithm in that it will generate a test if one exists. Heuristics are used to achieve an efficient implicit search of the space of all possible primary input patterns until either a test is found or the space is exhausted.