Many built-in self-testing (BIST) schemes compress the test responses
from a k-output circuit to q signature streams, where q << k, a proces
s termed space compaction. The effectiveness of such a compaction meth
od can be measured by its compaction ratio c = k/q. A high compaction
ratio can introduce aliasing, which occurs when a faulty test response
maps to the fault-free signature. We investigate the problem of desig
ning zero-aliasing space compaction circuits with maximum compaction r
atio c(max). We introduce a graph representation of test responses to
study the space compaction process and relate space compactor design t
o a graph coloring problem. Given a circuit under test, a fault model,
and a test set, we determine q(min), which yields c(max) = k/q(min).
This provides a fundamental bound on the cost of signature-based BIST.
We show that q(min) less than or equal to 2 for all the ISCAS 85 benc
hmark circuits. We develop a systematic design procedure for the synth
esis of space compaction circuits and apply it to a number of ISCAS 85
circuits. Finally, we describe multistep compaction, which allows zer
o aliasing to be achieved with any q, even when q(min) > 1.