Optimal space compaction of test responses
Krishnendu Chakrabarty, Brian T. Murray, John P. Hayes · 2002
Many built-in self-testing (BIST) schemes compress the test responses from a k-output circuit to q signature streams, where q/spl Lt/k, a process termed space compaction. The effectiveness of a compaction method can be measured by its compaction ratio c=k/q. However, 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 designing zero-aliasing space compaction circuits with maximum compaction ratio c/sub max/. We introduce a graph representation of test responses to study the space compaction process and relate space compactor design to a graph coloring problem. For a given circuit tender test, a given fault model, and a given test set, we determine q/sub min/, which yields c/sub max/=k/q/sub min/. This provides a fundamental bound on the cost of signature based BIST. We develop a systematic design procedure for the synthesis of space compaction circuits and apply it to a number of ISCAS-85 benchmark circuits.