Bdd to fdd conversion

Question

Rule for bdd to zdd 

       1. First we calculate shanon normal form and then we draw the graph for the full minterms of sets.

       2. we will do the elimination rule. First delete all the nodes v whose high(v) = 0. Then redirect all the edges that goes to node V to low(v). 

Please correct me professor if I am wrong..

BDD to FDD Conversion 

 is there any similar rule for fdd too? For bdd first I found the set representation and then we convert it in RMNF. And again I get new set representation. Now from the set representation I am unable to draw FDD. 

For eg. 3sept 2024 q1g. We get the set representation {{a,b},{a,c},{a},{c},{b},{} }. But how to draw the diagram from this. 

Answer 1

BDDs and ZDDs both use the Shannon decomposition, but use different elimination rules. Thus, we can just undo the elimination rule of the BDDs and then apply the elimination rules of the ZDDs to convert a BDD into a ZDD.

For converting BDDs to FDDs, things are more difficult since the two kinds of DDs use different decomposition types. However, you can find the following two recursive algorithsm in the slides:

However, while the algorithms are short, they call very often Apply with the XOR operation which may not be so convenient when trying this manually.