Complexity of sequential ATPG

The research reported in this paper was conducted to identify those attributes, of both sequential circuits and structural, sequential automatic test pattern generation (ATPG) algorithms, which can lead to extremely high test generation times. The retiming transformation is used as a mechanism to create two classes of circuits which present varying degrees of complexity for test generation. It was observed for three different sequential test generators that the increase in complexity of testing is not due to those circuit attributes (namely sequential depth and cycles) which have traditionally been associated with such complexity. Evidence is instead provided that another circuit attribute, termed density of encoding, is a key indicator of the complexity of structural, sequential ATPG