ZERO-ALIASING SPACE COMPACTION USING LINEAR COMPACTORS WITH BOUNDED OVERHEAD

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.