2
$\begingroup$

I am trying to figure out difference between fully- and quasi-reduced BDDs. I have read a lot of material but still it is not very clear. As I am trying to figure out the quasi reduced version for union between two BDDs. The algorithm for union between two fully-reduced BDDs is

bdd Union(bdd p, bdd q) 
   //fully-reduced version
   local bdd r;
1  if p=0 or q=1 then return q;
2  if q=0 or p=1 then return p;
3  if p=q then return p;
4  if Cachecontainsentry⟨UnionCODE,{p,q}:r⟩ then return r;
5  if p.lvl = q.lvl then
6    r ← UniqueTableInsert(p.lvl, Union(p[0], q[0]), Union(p[1], q[1]));
7  else if p.lvl > q.lvl then
8    r ← UniqueTableInsert(p.lvl, Union(p[0], q), Union(p[1], q));
9  else since p.lvl < q.lvl then
10   r ← UniqueTableInsert(q.lvl, Union(p, q[0]), Union(p, q[1]));
11 enter⟨UnionCODE,{p,q}:r⟩inCache;
12 return r;

I have read the paper Binary decision diagrams in theory and practice by Rolf Drechsler, Detlef Sieling for basics of BDD, and Data Representation and Efficient Solution: A Decision Diagram Approach by Gianfranco Ciardo for quasi-reduced and fully reduced definitions. Then I read more papers with more or less same description of quasi- and fully-reduced BDDs. In the former paper I mentioned the authors talk about reduced BDDs, I am not clear whether these BDDs are fully reduced. Quasi-reduced BDDs has no variable skipping so how come they are reduced when they have redundant nodes. I am pretty confused between BDD, quasi-reduced BDD and fully-reduced BDD. Yes, I am trying to find the difference between union algorithm for quasi-reduced and fully-reduced, for this I need to look at the quasi-reduced version of union algorithm.

I figured out an algorithm for union of two quasi reduced BDDs p and q resulting in r.

bdd Union(bdd p, bdd q) 
  local bdd r;
1 if p=0 or q=1 then return q;
2 if q=0 or p=1 then return p;
3 if p=q then return p;
4 if Cachecontainsentry⟨UnionCODE,{p,q}:r⟩ then return r;
  //p.lvl = q.lvl in case of quasi reduced BDDs
5 r ← UniqueTableInsert(p.lvl, Union(p[0], q[0]), Union(p[1], q[1]));
6 enter⟨UnionCODE,{p,q}:r⟩ in Cache;
7 return r;

Since there is no variable skipping, p.lvl is always equal to q.lvl. I have a question about this algorithm.

If I want to implement Xor or Xnor for quasi-reduced BDDs, can it be done the same way as union or should I implement the expression pq' + p'q where q' = !q.

$\endgroup$
  • 1
    $\begingroup$ What sources have you read? Where have you looked for information? Have you found definitions of fully reduced and quasi reduced? Are you able to understand the defns? Have you tried a few examples by hand? I encourage you to edit your question to show us the work you've already done; it will help us give you a better answer. (We do expect you to try to solve the problem on your own first before asking.) Also, please clarify what you are looking for. Are you asking for an algorithm to take the union of two quasi-reduced BDDs? What's wrong with fully reducing both and then unioning them? $\endgroup$ – D.W. Aug 7 '13 at 4:56
  • 1
    $\begingroup$ What is the question here? If you want to figure out the difference between reduced and quasi-reduced BDDs, please state the respective definitions and we can explain. But in the second half of your post, you pose another question entirely! $\endgroup$ – Raphael Aug 13 '13 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.