Identifying Legal and Illegal States in Synchronous Sequential Circuits Using Test Generation

Article type: Research Article

Authors: Bareiša, Eduardas | Motiejūnas, Kęstutis | Šeinauskas, Rimantas

Affiliations: Department of Software Engineering, Kaunas University of Technology, Studentų 50–406, LT‐3028 Kaunas, Lithuania, e‐mail: [email protected]

Abstract: Identifying legal and illegal states significantly reduces computational complexity of ATPG. A unified framework for identification of the legal and illegal states is presented. Most known methods for identification of the legal and illegal states are interpretable within this framework. New theorems and the resulting procedures for identifying exact collection of legal or illegal states of a circuit are presented. Experimental results demonstrate that exact collection of legal states for some circuits is significantly smaller than collections obtained by backward state search algorithm and by algorithm based on combinational ATPG theorems. The use of the exact collection of legal states allows identifying more undetectable faults. The proposed procedure for identifying of the exact collection of legal states starts from any state of the circuit, builds initially an enlarged collection of legal states and converges rapidly to the exact solution.

Keywords: sequential circuits, legal and illegal states, detectability of faults

Journal: Informatica, vol. 14, no. 2, pp. 135-154, 2003