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 g eneration is examined. Four different schemes an 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 tile bin ary patterns of any two rows of T, so that they can be generated by a count er in the minimum number of cycles, Although all schemes are NP-hard, an ap proximation algorithm is presented for the first scheme which guarantees so lutions within 2.p from the optimal, where p is the prescribed number of pa rtitions. The remaining problems are shown to be NP-complete even to be app roximated within twice the optimal. (C) 2001 Elsevier Science B.V. an right s reserved.