Static variable ordering in ZBDDs for path delay fault coverage calculation

Zero-suppressed Binary Decision Diagrams (ZBDDs) are data structures that represent sets efficiently and they have recently been suggested for use in nonenumerative path delay fault (PDF) coverage calculations. Many heuristics have been proposed to order variables (representing primary inputs) in ZBDDs to avoid size explosion; however, in ZBDD-based PDF coverage calculations, the variables represent the nets in a circuit, not the circuit primary inputs. This fact motivates us to investigate new ordering strategies since the number of nets in a circuit is relatively large as compared to the number of primary inputs. Several new static ordering heuristics are proposed based on structural properties of the circuit undergoing PDF coverage calculations and are evaluated. The experimental results show that the new heuristics we propose greatly reduce the size of the ZBDDs.