Novel Reduction Methods for Decision Diagrams

Abstract

We propose a novel method of reduction for binary-based decision diagrams (DD) exploiting the similarities between Boolean functions. Conventional methods are able to remove redundant parts of DD that adhere to (or represent) identical structures. The proposed approach tries to take advantage of not only identical but also equivalent parts of a diagram, which produce identical results after a change in variable ordering. Basic types of DD, like Binary DD (BDD) or Functional DD (FDD) do not allow for the reduction of equivalent parts of a diagram as the notation of change in ordering would be lost. Therefore, we propose a new type of decision diagram able to incorporate different orders of variables and thus allowing the reduction of equivalent DD parts– Multi-Variable Decision Diagram (MVDD). The only remaining obstacle is the determination of equivalency, for which we also propose a new heuristic. The paper also presents reduction of Kronecker Functional DD (KFDD) and MVDD with regard to multiple parameters, where the optimization process relies heavily on evolutionary algorithms and Residual Variable (RV). The average added value of MVDD to the reduction of diagram size was 26.13% when compared to BDD and 12.27% when compared to KFDD while preserving similar values of power consumption and average path length in the diagram.

Keywords

• MVDD
• KFDD
• decision diagrams
• residual variable