# Sequential Test Pattern Generation: Using Implicit STG Traversal Techniques to Generate Tests and Identify Redundancies in Sequential Circuits

### C. Wawrukiewicz, A. Saldanha, Robert K. Brayton and Alberto L. Sangiovanni-Vincentelli

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/ERL M94/4

1994

The implicit STG traversal techniques developed recently in the verification community can also be used to generate tests and identify redundancies in sequential circuits. A Sequential ATPG system which uses these techniques has been implemented in 515. This system uses two different ATPG algorithms. The first is Ghosh's 3-step test generation procedure, modified to use implicit STG traversal techniques. This 3-step algorithm is fast, but is not guaranteed to produce a test for a fault. The second ATPG algorithm builds the product of the good and faulty circuit, and then implicitly traverses this product machine, just as in implicit circuit verification. If this traversal proves the good and faulty circuits equivalent, then the fault is redundant; otherwise the differentiating sequence is a test for a fault. This second algorithm is guaranteed to produce a test for a fault or else prove the fault redundant, but is more expensive than the first algorithm. Results of applying the 515 ATPG algorithms to the ISCAS `89 benchmark circuits are presented, and these results are compared to those of STEED and VERITAS. Algorithms for generating small test sets and for performing redundancy removal based upon the same algorithms used in general ATPG--are also presented, along with the results of applying them to the ISCA5 circuits. Finally, suggestions for handling larger circuits--circuits which cannot be tested by any existing ATPG algorithm-- are presented.

BibTeX citation:

@techreport{Wawrukiewicz:M94/4, Author = {Wawrukiewicz, C. and Saldanha, A. and Brayton, Robert K. and Sangiovanni-Vincentelli, Alberto L.}, Title = {Sequential Test Pattern Generation: Using Implicit STG Traversal Techniques to Generate Tests and Identify Redundancies in Sequential Circuits}, Institution = {EECS Department, University of California, Berkeley}, Year = {1994}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/2493.html}, Number = {UCB/ERL M94/4}, Abstract = {The implicit STG traversal techniques developed recently in the verification community can also be used to generate tests and identify redundancies in sequential circuits. A Sequential ATPG system which uses these techniques has been implemented in 515. This system uses two different ATPG algorithms. The first is Ghosh's 3-step test generation procedure, modified to use implicit STG traversal techniques. This 3-step algorithm is fast, but is not guaranteed to produce a test for a fault. The second ATPG algorithm builds the product of the good and faulty circuit, and then implicitly traverses this product machine, just as in implicit circuit verification. If this traversal proves the good and faulty circuits equivalent, then the fault is redundant; otherwise the differentiating sequence is a test for a fault. This second algorithm is guaranteed to produce a test for a fault or else prove the fault redundant, but is more expensive than the first algorithm. Results of applying the 515 ATPG algorithms to the ISCAS `89 benchmark circuits are presented, and these results are compared to those of STEED and VERITAS. Algorithms for generating small test sets and for performing redundancy removal based upon the same algorithms used in general ATPG--are also presented, along with the results of applying them to the ISCA5 circuits. Finally, suggestions for handling larger circuits--circuits which cannot be tested by any existing ATPG algorithm-- are presented.} }

EndNote citation:

%0 Report %A Wawrukiewicz, C. %A Saldanha, A. %A Brayton, Robert K. %A Sangiovanni-Vincentelli, Alberto L. %T Sequential Test Pattern Generation: Using Implicit STG Traversal Techniques to Generate Tests and Identify Redundancies in Sequential Circuits %I EECS Department, University of California, Berkeley %D 1994 %@ UCB/ERL M94/4 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/2493.html %F Wawrukiewicz:M94/4