FDD2BDD algorithm

Question

Hi,

I have a doubt regarding BDD2FDD algorithm ,

I have done with FDD2BDD algorithm by +ve davio with apply algorithm

FDD2BDD((-ve)) XOR root & ( Apply(xor, BDD2FDD(-ve),BDD2FDD(+ve))) using this recursive method.

But I'm not sure how to do FDD2BDD vice versa. Could you please help on this?

Answer 1

For BDD2FDD, you recursively compute the FDDs of the cofactors. Then, you compute the xor of these FDDs which is (of course) a computation that takes the two FDDs of the recursive calls and computes a FDD as their xor operation. This Apply function works as the one for BDDs, i.e., recursively traverses the FDDs and moves the maximal node upwards.

For FDD2BDD, you recursively compute the BDDs of the sub functions high(f) and low(f). Then, you compute the xor of these BDDs which is (of course) a computation that takes the two BDDs computed by the recursive calls and computes a BDD as their xor operation. You just use the Apply algorithm for the latter.

So, what is the question?

Comments

I have posted it here : https://q2a.cs.uni-kl.de/3846/fdd2bdd-algorithm