A combinatorial approach to X-tolerant compaction circuits

Yuichiro Fujiwara, Charles Colbourn

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Test response compaction for integrated circuits (ICs) with scan-based design-for-testability (DFT) support in the presence of unknown logic values (Xs) is investigated from a combinatorial viewpoint. The theoretical foundations of X-codes, employed in an X-tolerant compaction technique called X-compact, are examined. Through the formulation of a combinatorial model of X-compact, novel design techniques are developed for X-codes to detect a specified maximum number of errors in the presence of a specified maximum number of unknown logic values, while requiring only small fan-out. The special class of X-codes that results leads to an avoidance problem for configurations in combinatorial designs. General design methods and nonconstructive existence theorems to estimate the compaction ratio of an optimal X-compactor are also derived.

Original languageEnglish (US)
Article number5485008
Pages (from-to)3196-3206
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 2010


  • Built-in self-test (BIST)
  • Circuit testing
  • Compaction
  • Configuration
  • Steiner system
  • Superimposed code
  • Test compression
  • X-code
  • X-compact

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'A combinatorial approach to X-tolerant compaction circuits'. Together they form a unique fingerprint.

Cite this