Title :
Solving the path sensitization problem in linear time
Author :
Altenbernd, P. ; Strathaus, J.
Author_Institution :
Paderborn Univ., Germany
Abstract :
Presents a new algorithm which computes in linear time with respect to the size of the circuit if a given path is sensitizable or not. The algorithm is based on a set of sensitizing conditions. Besides handling feedback loops, the algorithm works hierarchically, and considers the delay of each circuit element (dynamic sensitization). The trade-off made to gain a linear runtime behavior is discussed. The algorithm is implemented as a component of an interactive timing verifier
Keywords :
circuit analysis computing; computational complexity; delays; digital circuits; feedback; interactive systems; circuit element delay; circuit size; dynamic sensitization; feedback loops; hierarchical algorithm; interactive timing verifier; linear runtime behavior; linear time complexity; path sensitization problem; sensitizing conditions; timing errors; Algorithm design and analysis; Application specific integrated circuits; Ear; Feedback loop; Gain; Liver; Propagation delay; Runtime; Testing; Timing;
Conference_Titel :
Design Automation, 1992. Proceedings., [3rd] European Conference on
Conference_Location :
Brussels
Print_ISBN :
0-8186-2645-3
DOI :
10.1109/EDAC.1992.205959
