A novel minimization method for sentential decision diagrams

Abstract Sentential Decision Diagrams (SDDs) are a generalization of Binary Decision Diagrams (BDDs) that allow decisions based on “sentences” of variables, rather than only individual variables. SDDs are ordered based on a binary tree of variables (a vtree) which can represent their more complex structure. Like BDDs, the order of an SDD significantly impacts its size. We present two novel SDD minimization methods based on Rudell’s sifting algorithm and a symmetric sifting algorithm, both of which are BDD minimization methods. To evaluate the performance of our proposed techniques, we compile the combinational benchmarks from the LGSynth’91 benchmark set and dynamically minimize each circuit with our proposed techniques and two variations of the current state-of-the-art method. Our methods show an average improvement ratio of 20.2 % in SDD size compared with the current state-of-the-art technique. For larger circuits (≥50 inputs), the improvement ratio increases to 39.2 %.