FDD to ZDD

Question

Hi, 

I have doubt regarding FDD to ZDD translation. I got set representation of ZDD from FDD. but not sure how can i draw the tree from the tree, I have tried to solve that but not sure whether it's correct or not. 

 FDD = { {a,b,c}; {b}; {} } 

ZDD = { {a,b,c}; {a,c}; {c}; {a}; {}}

Is it the proper way to decompose? Could you please guide me?

Answer 1

I am not sure what you mean with "I got set representation of ZDD from FDD.", what you need to do is to read the following:

1. get the set representation of the FDD
2. determine the RMF of the set representation
3. convert the RMF to DNF (expand the cubes of the DNF to midterms)
4. convert the DNF to a set representation of the ZDD
5. write down the ZDD from the set representation of step 4

Comments

what i have done is ,
FDD is {{a,b,c}; {b}; {}} , i replaced that by
abc xor (a xor 1)(b)(c xor 1) xor (a xor 1)(b xor 1) (c xor 1) after solving this, i got
 { {a,b,c}; {a,c}; {c}; {a}; {}} . Which is the solution , does that work?

---

Yes, that looks fine to me!

The formula that you have is in RMF

a&b&c xor b xor true

which would be fully expanded to

a&b&c xor b xor true
= a&b&c xor !b
= a&b&c  or !b
= a&b&c  or !a&!b or  a&!b
= a&b&c  or !a&!b&!c or  a&!b&!c or !a&!b&c or  a&!b&c

which is represented by the sets

{{a,b,c},{},{a},{c},{a,c}}

---

Thank you professor. I understood it