Abstract
Exhaustive self-testing of combinational circuitry within the framework of the level-sensitive scan design (LSSD) discipline requires that every output node depend on a small number of input nodes. We present here 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 bits of register). Our partitioning algorithms conform to two different design constraints. We also show that the unconstrained partitioning problem is NP-complete.
Original language | English |
---|---|
Pages (from-to) | 37-48 |
Number of pages | 12 |
Journal | Algorithmica (New York) |
Volume | 6 |
Issue number | 1-6 |
DOIs | |
State | Published - Jun 1991 |
Keywords
- Circuit testing
- Dynamic programming
- LSSD
- NP-completeness
- Partitioning