A zero-suppressed decision diagram (ZSDD or ZDD) is a particular kind of binary decision diagram (BDD) with fixed variable ordering. This data structure provides a canonically compact representation of sets, particularly suitable for certain combinatorial problems. Recall the Ordered Binary Decision Diagram (OBDD) reduction strategy, i.e. a node is replaced with one of its children if both out-edges point to the same node. In contrast, a node in a ZDD is replaced with its negative child if its positive edge points to the terminal node 0. This provides an alternative strong normal form, with improved compression of sparse sets. It is based on a reduction rule devised by Shin-ichi Minato in 1993.
Background In a binary decision diagram, a Boolean function can be represented as a rooted, directed, acyclic graph, which consists of several decision nodes and terminal nodes. In 1993, Shin-ichi Minato from Japan modified Randal Bryant's BDDs for solving combinatorial problems. His "Zero-Suppressed" BDDs aim to represent and manipulate sparse sets of bit vectors. If the data for a problem are represented as bit vectors of length n, then any subset of the vectors can be represented by the Boolean function over n variables yielding 1 when the vector corresponding to the variable assignment is in the set. According to Bryant, it is possible to use forms of logic functions to express problems involving sum-of-products. These functions of n binary variables can be represented as sets of "cubes", each denoted by an letter string of length n containing symbols 0, 1, and -. For instance, the function f ( x 1 , x 2 , x 3 ) = ( x ¯ 1 ∧ x 2 ) ∨ ( x ¯ 2 ⊕ x 3 ) {\displaystyle f(x_{1},x_{2},x_{3})=({\bar {x}}_{1}\land x_{2})\lor ({\bar {x}}_{2}\oplus x_{3})} can be illustrated by the set { 01 − , − 11 , − 00 } {\displaystyle \{01-,-11,-00\}} . To evaluate f ( 1 , 1 , 0 ) {\displaystyle f(1,1,0)} it is necessary to see if 110 matches any member of the set where - means "Don't care". Since 110 matches none of the entries the set f ( 1 , 1 , 0 ) = 0 {\displaystyle f(1,1,0)=0} . The symbols 1, 0, and – can be denoted the using bit patterns 10, 01, and 00 respectively. This way one can represent the above set with bit vectors in the form of { 011000 , 001010 , 000101 } {\displaystyle \{011000,001010,000101\}} . Notice that the set of bit vectors is sparse, in that the number of vectors is fewer than 2n, which is the maximum number of bit vectors, and the set contains many elements equal to zero. In this case, a node can be omitted if setting the node variable to 1 causes the function to yield 0. This is seen in the condition that a 1 at some bit position implies that the vector is not in the set. For sparse sets, this condition is common, and hence many node eliminations are possible. Minato has proved that ZDDs are especially suitable for combinatorial problems, such as the classical problems in two-level logic minimization, knight's tour problem, fault simulation, timing analysis, the N-queens problem, as well as weak division. By using ZDDs, one can reduce the size of the representation of a set of n-bit vectors in OBDDs by at most a factor of n. In practice, the optimization is statistically significant.
Definitions We define a Zero-Suppressed Decision Diagram (ZDD) to be any directed acyclic graph such that:
A terminal node is either: The special ⊤ node which represents the unit family { ∅ } {\displaystyle \{\emptyset \}} (i.e., a singleton set), or The special ⊥ node which represents the empty family ∅ {\displaystyle \emptyset } . Each nonterminal node satisfies the following conditions: There is exactly one node with zero in-degree—the root node. The root node is either terminal or labelled by the smallest integer in the diagram. If two nodes have the same label, then their LO or HI edges point to different nodes. In other words, there are no redundant nodes. We call Z an unreduced ZDD, if a HI edge points to a ⊥ node or condition 4 fails to hold. In computer programs, Boolean functions can be expressed in bits, so the ⊤ node and ⊥ node can be represented by 1 and 0. From the definition above, we can represent combination sets efficiently by applying two rules to the BDDs:
Eliminate all the nodes whose 1-edge points to the 0-terminal node (Figure 1). Then connect the edge to the other subgraph directly. Share all equivalent sub-graphs the same as for original BDDs. If the number and the order of input variables are fixed, a zero-suppressed BDD represents a Boolean function uniquely (as proved in Figure 2, it is possible to use a BDD to represent a Boolean binary tree).
Representing a family of sets Let F be a ZDD. Let v be its root node. Then:
If v = ⊥ , then there can be no other nodes, and F represents Ø, the empty family. If v = ⊤, then there can be no other nodes, and F represents the family containing just the empty set { Ø }. We call this a unit family, and denote it by . If v has two children. Let v0 be the LO node, and v1 be the HI node. Let Fi be the family represented by the ZDD rooted at vi, which can be shown by proof of induction. Then F represents the family
… excerpt ends here. Continue reading the full article.
