# FDD2BDD algorithm doubt

I want to convert this FDD2BDD, i have done this using by FDD by set->RMNF->SNF to get BDD. That worked perfectly.

This one I'm bit confused . Not sure why all the nodes got reduced.  I took the FDD (answer ) then try to find the BDD for this(question) .

I was following the step, but node C is 0 for me. Which means , I cant find node C in the BDD, it reduced to 0.  Could you please help on this?

edited

+1 vote

The algorithm always takes the cofactors, regardless which variable is their root. So, in that case, you just have the leaf node 0.
by (166k points)
selected by
So ..what I have done is correct?

FDD2BDD(n6) = Fdd2Bdd(n4) xor  Fdd2Bdd(n3) split by a
FDD2BDD(n4) = 0 xor  1 split by b
FDD2BDD(n3) = 0 xor  Fdd2Bdd(n2) split by b
FDD2BDD(n2) = 1 xor  1 split by c

If I draw here, both -ve and +ve cofactors of c , are 1. Thats not correct in the given question.
No, it is not correct, since you also got the wrong BDD. The correct computation is as follows:

FDD2BDD(n6)
= a ? FDD2BDD(n4)⊕FDD2BDD(n3) : FDD2BDD(n4)
= a ? FDD2BDD(n4)⊕FDD2BDD(n3) : FDD2BDD(n4)
= a ? (b ? 1 : 0)⊕(b ? (c ? 0 : 1) : 0) : (b ? 1 : 0)
= a ? (b ? 1⊕(c ? 0 : 1) : 0⊕0) : (b ? 1 : 0)
= a ? (b ? (c ? 1⊕0 : 1⊕1) : 0⊕0) : (b ? 1 : 0)
= a ? (b ? (c ? 1 : 0) : 0) : (b ? 1 : 0)

FDD2BDD(n4)
= b ? FDD2BDD(0)⊕FDD2BDD(1) : FDD2BDD(0)
= b ? 0⊕1 : 0
= b ? 1 : 0

FDD2BDD(n3)
= b ? FDD2BDD(0)⊕FDD2BDD(n2) : FDD2BDD(0)
= b ? 0⊕(c ? 0 : 1) : 0
= b ? (c ? 0 : 1) : 0

FDD2BDD(n2)
= c ? FDD2BDD(1)⊕FDD2BDD(1) : FDD2BDD(1)
= c ? 1⊕1 : 1
= c ? 0 : 1
Thanks for the suggestion . I did computed the +ve cofactor directly, like negative. Now it's perfect. For BDD2FDD we are computing -ve and xor of -ve and +ve. Now we need to revert those steps. Thanks for the clarification.