BDD to FDD

Question

Question regarding Exam August 29, 2023 Question no. 1f BDD2FDD.

In this question my equation is without B transition like A is directly going to C. But the given solution have B node and transitions in it. Is it the right solution?
Did it through the algorithm in the slides.

Answer 1

It seems that you are confused with this question; the given decision diagram is a FDD that should be converted to an equivalent BDD, so that you should use the function FDD2BDD instead. But you can also make case distinctions on variables a and b so that you get simple formulas from the given FDD that can then be quickly converted to the BDD as well.

Comments

Isn't that BDD2FDD and FDD2BDD follow the same approach?

My main concern was without B in Final ROBDD is correct?

---

There is a difference in the two functions BDD2FDD and FDD2BDD which is in the final creation of a node that need to respect the elimination rules of BDDs or FDDs, respectively. The node B in the final BDD must be there. Note that BDDs are canonical normal forms, so that there is no alternative solution.

---

function BDD2FDD(b)
if isLeaf(b) return b;
else
F1 := BDD2FDD(high(b));
F0 := BDD2FDD(low(b));
h := Apply(⊕, F1, F0);
return CreateFddNode(label(b), h, F0);


function FDD2BDD(f )
if isLeaf(f ) return f ;
else
B1 := FDD2BDD(high(f ));
B0 := FDD2BDD(low(f ));
h := Apply(⊕, B1, B0);
return CreateBddNode(label(f ), h, B0);


Sorry I couldn't understand the difference between the two algorithm functions.
Could you reference it in the function exactly?

---

Well, the first uses CreateFddNode and the second uses CreateBddNode. These functions need to check whether the corresponding elimination rule applies. See page 116 for CreateBddNode.