TY - GEN
T1 - PARTITIONING CIRCUITS FOR IMPROVED TESTABILITY.
AU - Bhatt, Sandeep N.
AU - Chung, Fan R.K.
AU - Rosenberg, Arnold L.
PY - 1986
Y1 - 1986
N2 - Exhaustive self-testing of combinational circuitry within the framework of the LSSD design discipline requires that every output node depend on a small number of input nodes. We present efficient algorithms that take an arbitrary block of combinational logic and add to it the smallest number of bits of new LSSD registers necessary to: (1) partition the logic so that no output depends on more than k inputs, and (2) maintain timing within the block (so that all input-to-output paths encounter the same number of register bits). Our partitioning algorithms conform to two different design constraints. We also show that the unconstrained partitioning problem is NP-complete.
AB - Exhaustive self-testing of combinational circuitry within the framework of the LSSD design discipline requires that every output node depend on a small number of input nodes. We present efficient algorithms that take an arbitrary block of combinational logic and add to it the smallest number of bits of new LSSD registers necessary to: (1) partition the logic so that no output depends on more than k inputs, and (2) maintain timing within the block (so that all input-to-output paths encounter the same number of register bits). Our partitioning algorithms conform to two different design constraints. We also show that the unconstrained partitioning problem is NP-complete.
UR - http://www.scopus.com/inward/record.url?scp=0022918735&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022918735&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0022918735
SN - 0262121131
SP - 91
EP - 106
BT - Unknown Host Publication Title
A2 - Leiserson, Charles E.
ER -