TY - GEN
T1 - Computational complexity of test-point insertions and decompositions
AU - Rao, N. S.V.
AU - Toida, S.
N1 - Publisher Copyright:
© 1991 IEEE.
PY - 1992
Y1 - 1992
N2 - We consider two basic computational problems that arise in the areas of pseudo-exhaustive testing, design of polynomial-time testable classes, test-point insertion, and CrossCheck, m the contcxt of test generation and design for testability of combinational circuits. The first problem is to decompose a circuit into subcircuits such that the number of inputs to each sub- circuit is bounded by K; we show that this problem is NP-complete. This result establishes that the detection (minimization) problems associated with three polynomial-time testable classcs and the method of pseudo-exhaustive testing are all NP-complete (hard). We then present simple approximation algorithms for solving these problems. The second prvblem deals with placing k test points on a circuit so as to facilitate the observability and/or controllability; this problem is also shown to be NP-hard. This problem arises in the methods of CrossCheck and segment-cell placement.
AB - We consider two basic computational problems that arise in the areas of pseudo-exhaustive testing, design of polynomial-time testable classes, test-point insertion, and CrossCheck, m the contcxt of test generation and design for testability of combinational circuits. The first problem is to decompose a circuit into subcircuits such that the number of inputs to each sub- circuit is bounded by K; we show that this problem is NP-complete. This result establishes that the detection (minimization) problems associated with three polynomial-time testable classcs and the method of pseudo-exhaustive testing are all NP-complete (hard). We then present simple approximation algorithms for solving these problems. The second prvblem deals with placing k test points on a circuit so as to facilitate the observability and/or controllability; this problem is also shown to be NP-hard. This problem arises in the methods of CrossCheck and segment-cell placement.
UR - http://www.scopus.com/inward/record.url?scp=85066904793&partnerID=8YFLogxK
U2 - 10.1109/ICVD.1992.658053
DO - 10.1109/ICVD.1992.658053
M3 - Conference contribution
AN - SCOPUS:85066904793
T3 - Proceedings of the IEEE International Conference on VLSI Design
SP - 233
EP - 238
BT - Proceedings - VLSI Design 1992
PB - IEEE Computer Society
T2 - 5th International Conference on VLSI Design, ICVD 1992
Y2 - 4 January 1992 through 7 January 1992
ER -