Zero-aliasing space compaction using linear compactors with bounded overhead

Space compaction is employed in built-in self-testing schemes to compress the test responses from a k-output circuit to q signature streams, where q≪k. The effectiveness of a compaction method is measured by its compaction ratio k/q and the amount of hardware required to implement the compaction circuit. However, a high compaction ratio can require a very large compactor as well as introduce aliasing, which occurs when a faulty test response maps to the fault-free signature. We investigate the problem of designing linear, zero-aliasing space compactors that provide a high compaction ratio and introduce bounded hardware overhead. We develop a graph model for the space-compaction process and relate space-compactor design to the graph coloring problem. This technique can also be used to reduce the width of multiple-input signature registers that are used for response compaction. We apply our design method to the ISCAS 85 benchmark circuits and present experimental data on the compaction ratio achieved for these circuits.