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

Citation
D. Kagaris et S. Tragoudas, Computational analysis of counter-based schemes for VLSI test pattern generation, DISCR APP M, 110(2-3), 2001, pp. 227-250
Citations number
11
Categorie Soggetti
Engineering Mathematics
Volume
110
Issue
2-3
Year of publication
2001
Pages
227 - 250
Database
ISI
SICI code
Abstract
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.