A COMPLEXITY ANALYSIS OF SEQUENTIAL ATPG

The research reported in this paper has been conducted to identify tho se attributes, of both sequential circuits and structural, sequential automatic test pattern generation algorithms, which can lead to extrem ely long test generation times, The retiming transformation is used to create families of circuits which have the same sequential depth and number and length of cycles, but a significantly different percentage of valid states, It was observed for three different sequential test p attern generators that the increase in complexity of test pattern gene ration Is related to a new circuit attribute, termed density of encodi ng, and not to the sequential depth or number and length of cycles-i.e ., those circuit parameters to which the complexity of test pattern ge neration has traditionally been attributed.