Equivalent Transformations of Structurally Synthesized BDDs and Applications

In this paper we explore several properties of Structurally Synthesized Binary Decision Diagrams (SSBDD), and based on these properties we propose a method for equivalent transformations of SSBDDs. The main importance of these transformations is in the fact that the mapping between SSBDD nodes and signal paths of the circuit represented by SSBDD remains invariant. The need of transformations of SSBDDs arose from the tasks of converting SSBDDs into Shared SSBDDs (S3BDD), as a more compact form of BDDs. A procedure is proposed for this task. Other application possibilities where the proposed method of graph transformations may be useful are discussed as well. Experiments demonstrate the feasibility of the proposed method and its high scalability.