The Complexity of Fault Detection Problems for Combinational Logic Circuits
- 1 June 1982
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-31 (6), 555-560
- https://doi.org/10.1109/tc.1982.1676041
Abstract
In this correspondence we analyze the computational complexity of fault detection problems for combinational circuits and propose an approach to design for testability. Although major fault detection problems have been known to be in general NP-complete, they were proven for rather complex circuits. In this correspondence we show that these are still NP-complete even for monotone circuits, and thus for unate circuits. We show that for k-level (k ≥ 3) monotone/unate circuits these problems are still NP-complete, but that these are solvable in polynomial time for 2-level monotone/unate circuits. A class of circuits for which these fault detection problems are solvable in polynomial time is presented. Ripple-carry adders, decoder circuits, linear circuits, etc., belong to this class. A design approach is also presented in which an arbitrary given circuit is changed to such an easily testable circuit by inserting a few additional test-points.Keywords
This publication has 18 references indexed in Scilit:
- A Design of Programmable Logic Arrays with Universal TestsIEEE Transactions on Computers, 1981
- On Closedness and Test Complexity of Logic CircuitsIEEE Transactions on Computers, 1981
- Testing Logic Networks and Designing for TestabilityComputer, 1979
- Diagnosis of Faults in Linear Tree NetworksIEEE Transactions on Computers, 1977
- Polynomially Complete Fault Detection ProblemsIEEE Transactions on Computers, 1975
- Complete Test Sets for Logic FunctionsIEEE Transactions on Computers, 1973
- Universal Test Sets for Logic NetworksIEEE Transactions on Computers, 1973
- Derivation of Minimal Test Sets for Monotonic Logic CircuitsIEEE Transactions on Computers, 1973
- Generation of Fault Tests for Linear Logic NetworksIEEE Transactions on Computers, 1972
- Derivation of Minimum Test Sets for Unate Logical CircuitsIEEE Transactions on Computers, 1971