  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.
