Checking integrity during dynamic reordering in decision diagrams

Decision Diagrams (DDs) are the state-of-the-art data structure in VLSI CAD. They are used in many safety critical applications, like verification. Recently a new approach based on recursive checksum computation has been presented that showed how the correctness of the data structures could be verified by on-line and off-line tests. In this paper it is shown that these techniques can also be integrated in DD packages making use of dynamic reordering methods, like variable reordering and reordering based synthesis. The correctness of the data structures can be verified by (nearly) no overhead. Experimental results are presented to demonstrate the efficiency of this approach