Computational analysis of counter-based schemes for VLSI test pattern generation

The use of a binary counter as a mechanism for VLSI built-in test pattern generation is examined. Four different schemes are studied which are defined as partitioning problems on the rows of a binary matrix T. The goal in all problems is to minimize the maximum distance between the values of the binary patterns of any two rows of T, so that they can be generated by a counter in the minimum number of cycles. Although all schemes are NP-hard, an approximation algorithm is presented for the first scheme which guarantees solutions within 2·p from the optimal, where p is the prescribed number of partitions. The remaining problems are shown to be NP-complete even to be approximated within twice the optimal.