An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits

TLDR

PODEM is a new test generation algorithm for combinational logic circuits. PODEM employs an implicit enumeration strategy, using heuristics to efficiently search all primary input patterns and guarantees a test if one exists, analogous to solving 0‑1 integer programming problems. PODEM proves to be highly efficient and simpler than the D‑algorithm for ECAT circuits, outperforming DALG across the general spectrum of 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 DALG 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.