Partitioning circuits for improved testability

Sandeep N. Bhatt, Fan R.K. Chung, Arnold L. Rosenberg

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 languageEnglish
Pages (from-to)37-48
Number of pages12
JournalAlgorithmica (New York)
Volume6
Issue number1-6
DOIs
StatePublished - Jun 1991

Keywords

  • Circuit testing
  • Dynamic programming
  • LSSD
  • NP-completeness
  • Partitioning

Fingerprint

Dive into the research topics of 'Partitioning circuits for improved testability'. Together they form a unique fingerprint.

Cite this