Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

868 questions

986 answers

1.4k comments

438 users

0 votes

I am solving this 2018.02.14.vrs.solutions.pdf (uni-kl.de) Q2. c where it says to compute the ZDD of the computed BDD. 

I saw numerous questions of the same type but I am unable to reach to the conclusion,

I tried uncompressing the ROBDD by removing the isomorphic rule but it didn't worked.

Q1. Could you please explain how can I uncompress it inorder to compute the ZDD ?

in * TF "Emb. Sys. and Rob." by (2.9k points)

1 Answer

+1 vote
 
Best answer

The key to the construction of a ZDD is the consideration of the satisfying assignments of the formula since the ZDD is a data structure that stores the cubes that occur in a DNF in an efficient way.

We are talking about the formula !p1&!p3|!p0&!p2|!p1&!p2. Looking at its BDD, you can obtain the following DNF from the paths from the root node to the 1-leaf:

    !p1& p2&!p3 | 
    !p1&!p2& p3 | 
    !p1&!p2&!p3 |
    !p0& p1&!p2& p3 |
    !p0& p1&!p2&!p3

This exands to the following disjunction of minterms that shows all satisfying assignments:

     p0&!p1& p2&!p3 |
     p0&!p1&!p2& p3 |
     p0&!p1&!p2&!p3 |
    !p0& p1&!p2& p3 |
    !p0& p1&!p2&!p3 |
    !p0&!p1& p2&!p3 |
    !p0&!p1&!p2& p3 |
    !p0&!p1&!p2&!p3

A ZDD also stores these satisfying assignmets, but it represents them not as a set of minterms, but as a set of set of variables where only the variables are listed that are true. Hence, we have to store the following set of sets of variables

    {{p0,p2},{p0,p3},{p0},{p1,p3},{p1},{p2},{p3},{}}

Now, you start decomposing this set of sets of variables by the variable ordering. For instance, starting with p3, we get

    p3=1: {{p0},{p1},{}}
    p3=0: {{p0,p2},{p0},{p1},{p2},{}}

as shown on the lecture slides, and you have to proceed with the remaining variables p2,p1,p0 to finally obtain the ZDD shown.  

An alternative way to compute the ZDD from the BDD is by the use of function BDD2ZDD shown in the lecture that reintroduces redundant case distinctions that were eliminated in the BDD reduction, and that uses the elimination rule of the ZDDs.

by (139k points)
selected by
Thanks for this explanation.
I really appreciate it.

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
asked Aug 5, 2020 in * TF "Emb. Sys. and Rob." by ssripa (550 points)
Imprint | Privacy Policy
...