TY - JOUR
T1 - On the ZBDD-based nonenumerative path delay fault coverage calculation
AU - Kocan, Fatih
AU - Gunes, Mehmet H.
PY - 2005/7
Y1 - 2005/7
N2 - We devise one exact and one pessimistic path delay fault (PDF) grading algorithms for combinational circuits. The first algorithm, an extension to the basic grading algorithm of Padmanaban, Michael, and Tragoudas (2003), does not store all of the detected PDFs during the course of grading, and, as a further improvement, it utilizes compressed representation of PDFs. These two techniques yield a space-and-time efficient algorithm. To enable grading of circuits with exponential number of paths, a circuit is first partitioned into a set of subcircuits. The second algorithm efficiently calculates the coverage of partitioned circuits. The former algorithm results in 50%-70% reduction in space and a speedup from 1.6 to 2.48 in ISCAS85 benchmarks. The time complexity of the latter algorithm is O(N2) subset operations per test vector where N is the number of nets in the circuit.
AB - We devise one exact and one pessimistic path delay fault (PDF) grading algorithms for combinational circuits. The first algorithm, an extension to the basic grading algorithm of Padmanaban, Michael, and Tragoudas (2003), does not store all of the detected PDFs during the course of grading, and, as a further improvement, it utilizes compressed representation of PDFs. These two techniques yield a space-and-time efficient algorithm. To enable grading of circuits with exponential number of paths, a circuit is first partitioned into a set of subcircuits. The second algorithm efficiently calculates the coverage of partitioned circuits. The former algorithm results in 50%-70% reduction in space and a speedup from 1.6 to 2.48 in ISCAS85 benchmarks. The time complexity of the latter algorithm is O(N2) subset operations per test vector where N is the number of nets in the circuit.
KW - Fault grading
KW - Path delay fault (PDF)
KW - Simulation
UR - http://www.scopus.com/inward/record.url?scp=22544488377&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=22544488377&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2005.850851
DO - 10.1109/TCAD.2005.850851
M3 - Article
AN - SCOPUS:22544488377
SN - 0278-0070
VL - 24
SP - 1137
EP - 1143
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 7
ER -