An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits
Goel · IEEE Transactions on Computers · 1981
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.
Cited by 1,122 works. doi:10.1109/tc.1981.1675757
Authors
References
- Problem-Solving Methods in Artificial Intelligence
- Integer programming
- Branch-and-Bound Methods: A Survey
- A logic design structure for LSI testability
- Review of "Problem-Solving Methods in Artificial Intelligence by Nils J. Nilsson", McGraw-Hill Pub.
- Diagnosis of Automata Failures: A Calculus and a Method
- An Additive Algorithm for Solving Linear Programs with Zero-One Variables
- Analyzing Errors with the Boolean Difference
- Test Generation and Dynamic Compaction of Tests
- LAMP: Automatic Test Generation for Asynchronous Digital Circuits