Identifying sequentially untestable faults using illegal states

Abstract

In this paper, we first present an algorithm (FILL) which efficiently identifies a large subset of the illegal states in a synchronous sequential circuit, without assuming a global reset mechanism. A second algorithm, FUNI, finds sequentially untestable faults whose detection requires some of the illegal states computed by FlLL. Although based on binary decision diagrams (BDDs), FILL is able to process large circuits by using a new functional partitioning procedure. The incremental building of the set of illegal states guarantees that FILL mill always obtain at least a partial solution. FUNI is a direct method that identifies untestable faults without using the exhaustive search involved in automatic test generation (ATG). Experimental results show that FUNI finds a large number of untestable faults up to several orders of magnitude faster than an ATG algorithm that targeted the faults identified by FUNI, Also, many untestable faults identified by FUNI were aborted by the test generator.