On the optimization of heterogeneous MDDs

This paper proposes minimization algorithms for the memory size and the average path length (APL) of heterogeneous multivalued decision diagrams (MDDs). In a heterogeneous MDD, each multivalued variable can take different domains. To represent a binary logic function using a heterogeneous MDD, we partition the binary variables into groups with different numbers of binary variables and treat the groups as multivalued variables. Since memory size and APL of a heterogeneous MDD depend on the partition of binary variables as well as the ordering of binary variables, the memory size and the APL of a heterogeneous MDD can be minimized by considering both orderings and partitions of binary variables. The experimental results show that heterogeneous MDDs can represent logic functions with smaller memory sizes than free binary decision diagrams (FBDDs) and smaller APLs than reduced ordered BDDs (ROBDDs); the APLs of heterogeneous MDDs can be reduced by half of the ROBDDs without increasing memory size; and heterogeneous MDDs have smaller area-time complexities than MDD(k)s.