K. Chakrabarty, ZERO-ALIASING SPACE COMPACTION USING LINEAR COMPACTORS WITH BOUNDED OVERHEAD, IEEE transactions on computer-aided design of integrated circuits and systems, 17(5), 1998, pp. 452-457
Space compaction is employed in built-in self-testing schemes to compr
ess the test responses from a k-output circuit to q signature streams,
where q much less than k. The effectiveness of a compaction method is
measured by its compaction ratio k/q and the amount of hardware requi
red to implement the compaction circuit. However, a high compaction ra
tio can require a very large compactor as well as introduce aliasing,
which occurs when a faulty test response maps to the fault-free signat
ure. We investigate the problem of designing linear, zero-aliasing spa
ce compactors that provide a high compaction ratio and introduce bound
ed hardware overhead. We develop a graph model for the space-compactio
n process and relate space-compactor design to the graph coloring prob
lem, This technique can also be used to reduce the width of multiple-i
nput signature registers that are used for response compaction. We app
ly our design method to the ISCAS 85 benchmark circuits and present ex
perimental data on the compaction ratio achieved for these circuits.