PARTITIONING CIRCUITS FOR IMPROVED TESTABILITY.

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.