Automatic test pattern generation (ATPG) for sequential circuitsinvolves making decisions in the state and combinational search spacesdefined by a sequential circuit. The search spaces are exponential inthe memory elements and primary inputs, respectively, making exhaustivesearch impractical. Since the circuit topology does not change, ATPGsearch for different faults may share identical decision spaces.However, existing sequential circuit ATPG algorithms are not capable ofrecognizing identical search decision spaces. Consequently, they reenterpreviously-explored decision spaces. We propose a dynamic learningalgorithm that identifies previously-explored decision spaces duringreverse-time sequential circuit test generation based on decompositionequivalences. This algorithm runs two and 3.3 times faster than GENTESTand HITEC, respectively, on the 1989 ISCAS benchmarks, compresses 24% ofthe learned information and identifies 85% of all previously-exploreddecision spaces by state covering. We provide theorems with proofs,examples and results
展开▼