binary-decision-diagramcudd

CUDD sum of products Boolean expression


I would like to create BDD for the following Boolean function:

F = (A'B'C'D') OR (A'B C) OR (C' D') OR (A)

I managed to create only F = (A'B'C'D') with the following code but how to add other product terms to the existing BDD?

 int main (int argc, char *argv[])
{
    char filename[30];
    DdManager *gbm; /* Global BDD manager. */
    gbm = Cudd_Init(0,0,CUDD_UNIQUE_SLOTS,CUDD_CACHE_SLOTS,0); /* Initialize a new BDD manager. */
    DdNode *bdd, *var, *tmp_neg, *tmp;
    int i;
    bdd = Cudd_ReadOne(gbm); /*Returns the logic one constant of the manager*/
    Cudd_Ref(bdd); /*Increases the reference count of a node*/

    for (i = 3; i >= 0; i--) {
        var = Cudd_bddIthVar(gbm,i); /*Create a new BDD variable*/
        tmp_neg = Cudd_Not(var); /*Perform NOT boolean operation*/
        tmp = Cudd_bddAnd(gbm, tmp_neg, bdd); /*Perform AND boolean operation*/
        Cudd_Ref(tmp);
        Cudd_RecursiveDeref(gbm,bdd);
        bdd = tmp;
    }

    bdd = Cudd_BddToAdd(gbm, bdd); 
    print_dd (gbm, bdd, 2,4);   
    sprintf(filename, "./bdd/graph.dot"); 
    write_dd(gbm, bdd, filename);  
    Cudd_Quit(gbm);
    return 0;
}

Solution

  • Build every conjunction independently so that you get conj0 to conj3 make sure to only negate the correct literals. I'm not particularly versed in C and don't have a development environment setup right now so you will need to make some corrections.

    I will use the following mapping

    A <=> BDD(0)
    B <=> BDD(1)
    C <=> BDD(2)
    D <=> BDD(3)
    

    Build conj0 the way you do it now in your for loop. Make sure conj0 = bdd afterwards.

    For conj1 which will encode (A' B C) use

    bdd = Cudd_IthVar(gbm, 0);
    bdd = Cudd_Not(bdd);
    tmp = Cudd_And(gbm, bdd, Cudd_IthVar(gbm, 1));
    Cudd_Ref(tmp);
    Cudd_Deref(gbm, bdd);
    bdd = tmp;
    tmp = Cudd_And(gbm, bdd, Cudd_IthVar(gbm, 2));
    Cudd_Ref(tmp);
    Cudd_Deref(gbm, bdd);
    bdd = tmp;
    conj1 = bdd;
    

    Do the same for conj2 and conj3.

    After you've got all the conjunctions build build the top level disjunction by using Cudd_bddOr(). Also make sure that you get the Cudd_Ref() and Cudd_Deref() right otherwise you'll leak memory.