How to get ZDD from set representation? [2022.09 1d]

Question

In order to get ZDD from FDD we need to:

1. Get a set representation of FDD

2. Write the RMNF

3. Write the minterms of RMNF then replace XOR with OR (or write the truth table)

4. Get a set representation of the min terms

5. Draw ZDD from the set representation

How do I get ZDD from set representation?

Linking relevant question here.

Answer 1

A ZDD stores a set of sets as explained on slides 140-142 of the BDD chapter. The set of minterms {}, {a}, {c}, {a,c}, {a,b,c} is thereby decomposed as follows (using the variable ordering 

    a = 1: {a},{a,c},{a,b,c} --> {},{c},{b,c}
    a = 0: {},{c}

Note: first split the set {{},{a},{c},{a,c},{a,b,c}} into the minterms that contain a, i.e., {a},{a,c},{a,b,c}, and those that do not contain a, i.e., {},{c}, then remove a. 

The procedure is then repeated for all variables until only {} and {{}} occur which are the leaf nodes.