Title :
A Topological Search Algorithm for ATPG
Author :
Kirkland, Tom ; Mercer, M. Ray
Author_Institution :
MCC, Dr. Austin, TX
Abstract :
The automatic generation of tests for combinational digital circuits is examined from the standpoint of a guided search through a search space. The limitations of this process, namely the size of the search space and the overall strategy, are identified and methods are presented to reduce the size of the search space as well as produce a more optimal ordering of node assignments. A new algorithm is proposed that uses the smaller search space and the improved ordering for node assignments based on a topological analysis of the circuit. Results are presented indicating that this new algorithm, termed TOPological Search (TOPS), is faster than existing algorithms and also rapidly identifies many redundant faults without search.
Keywords :
Algorithm design and analysis; Automatic test pattern generation; Automatic testing; Circuit analysis; Circuit faults; Circuit testing; Digital circuits; Fault diagnosis; Permission; Search problems;
Conference_Titel :
Design Automation, 1987. 24th Conference on
Print_ISBN :
0-8186-0781-5
DOI :
10.1109/DAC.1987.203289