Ordered binary decision diagrams and circuit structure - Extended abstract

Abstract

The relationship between two important means of representing Boolean functions, combinational circuits and ordered binary decison diagrams (OBDDs), is studied. Circuit width is related to OBDD size, and it is shown how register allocation can be used to determine a good variable order for OBDD construction. It is shown that if C has n inputs, m outputs, and width w(C), then there is a variable ordering for which the directed-acyclic-graph-based representation for C has at most n × m × 2w(C) nodes. Since the width of a circuit is closely related to the number of registers required to evaluate the circuit, the result shows that register allocation techniques can be used to compute variable orderings with predicted behavior. The use of these ideas in decomposing a function either for representation as a set of OBDDs or for implementation in a cascode technology is outlined. A characterization is given of a class of multioutput functions which includes addition whose members have particularly small OBDDs.