Feedback cycle detection across non-scan memory elements

Abstract

All feedback cycles in a circuit network which cross only non-scannable memory elements are detected in linear run time. The method models a circuit network as a directed graph, then attributes network elements so that a single feedback cycle may be found in constant time. In the breadth first version, feedback is detected by traversing at most a constant distance back to the last scannable memory element. In the depth first version, graph nodes are not FINISHED until all predecessors are FINISHED. Feedback is found immediately if a node runs into another node that is NOTFINISHED. This feedback is illegal if both nodes are in a zone defined by the same scannable memory element. The resulting identification and removal of feedback loops crossing only non-scannable memory elements significantly reduces the subsequent complexity of test pattern generation. This ensures a faster, more reliable, and more accurate test process after circuit fabrication.