ECE 667

Binary Decision Diagrams

CUDD - a Decision Diagram package from University of Colorado

CUDD is a BDD package you can use to implement your own BDD-based program.

CUDD can be found at the following link: http://vlsi.colorado.edu/~fabio/ .

Use the following link for Windows based VIS system and other useful programs.

Windows tools . (courtesy of Alan Mishchenko)

Useful BDD Utility Tools

Here is a set of useful, stand-alone tools to build and display BDDs for Boolean functions. You can download executable codes, compiled for Linux, directly from the links below. (To access the BDD datastructure and do something useful with it, you have to use the CUDD package, preferrably from the VIS environment.)

Most of the academic tools represent the designs in BLIF format (BLIF = Berkeley Logic Interchange Format). The easiest way to create a file in blif format is to first write it in a simple equation format, eqn. Here is a simple example of a file in eqn and blif formats.
You can then generate a blif file using SIS or ABC programs as follows:

sis> read_eq file.eqn
sis> write_blif file.blif

abc 01> read_eqn file.eqn
abc 02> write_blif file.blif

Once the circuit is given in blif format, use the following command to create a drawing of its BDD:

blif2bdd [-order order_file] file.blif

Option -order allows you to impose a variable order, specified in the file order_file (list the variables in the desired order, separated by spaces or lines). Alternatively, the program blif2bdd will prompt you to choose a method for variable ordering. Sifting and window sifting are probably the best to minimize the size of the resulting BDD.

The blif2bdd creates two files in the dot format:

file.blif.dot.add (regular 2-terminal BDD), and
file.blif.dot (1-terminal BDD with complement edges).

You probably want to use the traditional, 2-terminal BDD.

OPTIONAL: To show the structure of a circuit (file.blif) as a Boolean network, use the following command:

blif2dot file.blif

Finally, you can create a PS file to view the network or the BDD for your circuit using the dotps program (you need to download the executable dot program for the dotps to work):

dotps file.dot (it will create file.dot.ps)

Now you can display the resulting PS file using gv, or convert PS to PDF (ps2pdf) and use Adobe Acrobat reader to view the PDF file.