BDD minimization by truth table permutations

Abstract

Bern, Meinel and Slobodova (see Proceedings of 32nd Design Automation Conference, p. 408-13, June 1995) have recently proposed a novel technique called cube transformations to minimize the size of binary decision diagrams. Given a Boolean function, they try to find a domain transformation such that the function after the transformation has a smaller BDD. It has been shown that well-chosen transformations enable us to represent compactly the hidden-weight-bit functions, which are known to have exponential-sized BDDs for any variable ordering. Although their results are promising, no heuristics for picking good transformations are provided in the paper by Bern et al., i.e. they carefully chose a particular transformation for each function by investigating the characteristic of the function. In this paper, we present a set of heuristic algorithms which construct effective transformations starting from given BDDs. Preliminary experimental results showed that this technique gives us a minimization ability which cannot be captured by dynamic reordering.