[8] | 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> |
---|
| 2 | |
---|
| 3 | <!--Converted with LaTeX2HTML 2K.1beta (1.47) |
---|
| 4 | original version by: Nikos Drakos, CBLU, University of Leeds |
---|
| 5 | * revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan |
---|
| 6 | * with significant contributions from: |
---|
| 7 | Jens Lippmann, Marek Rouchal, Martin Wilck and others --> |
---|
| 8 | <HTML> |
---|
| 9 | <HEAD> |
---|
| 10 | <TITLE>Introduction</TITLE> |
---|
| 11 | <META NAME="description" CONTENT="Introduction"> |
---|
| 12 | <META NAME="keywords" CONTENT="cuddIntro"> |
---|
| 13 | <META NAME="resource-type" CONTENT="document"> |
---|
| 14 | <META NAME="distribution" CONTENT="global"> |
---|
| 15 | |
---|
| 16 | <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"> |
---|
| 17 | <META NAME="Generator" CONTENT="LaTeX2HTML v2K.1beta"> |
---|
| 18 | <META HTTP-EQUIV="Content-Style-Type" CONTENT="text/css"> |
---|
| 19 | |
---|
| 20 | <LINK REL="STYLESHEET" HREF="cuddIntro.css"> |
---|
| 21 | |
---|
| 22 | <LINK REL="next" HREF="node2.html"> |
---|
| 23 | <LINK REL="previous" HREF="cuddIntro.html"> |
---|
| 24 | <LINK REL="up" HREF="cuddIntro.html"> |
---|
| 25 | <LINK REL="next" HREF="node2.html"> |
---|
| 26 | </HEAD> |
---|
| 27 | |
---|
| 28 | <BODY > |
---|
| 29 | <!--Navigation Panel--> |
---|
| 30 | <A NAME="tex2html246" |
---|
| 31 | HREF="node2.html"> |
---|
| 32 | <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next" |
---|
| 33 | SRC="icons/next.png"></A> |
---|
| 34 | <A NAME="tex2html242" |
---|
| 35 | HREF="cuddIntro.html"> |
---|
| 36 | <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up" |
---|
| 37 | SRC="icons/up.png"></A> |
---|
| 38 | <A NAME="tex2html236" |
---|
| 39 | HREF="cuddIntro.html"> |
---|
| 40 | <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous" |
---|
| 41 | SRC="icons/prev.png"></A> |
---|
| 42 | <A NAME="tex2html244" |
---|
| 43 | HREF="node8.html"> |
---|
| 44 | <IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index" |
---|
| 45 | SRC="icons/index.png"></A> |
---|
| 46 | <BR> |
---|
| 47 | <B> Next:</B> <A NAME="tex2html247" |
---|
| 48 | HREF="node2.html">How to Get CUDD</A> |
---|
| 49 | <B> Up:</B> <A NAME="tex2html243" |
---|
| 50 | HREF="cuddIntro.html">CUDD: CU Decision Diagram</A> |
---|
| 51 | <B> Previous:</B> <A NAME="tex2html237" |
---|
| 52 | HREF="cuddIntro.html">CUDD: CU Decision Diagram</A> |
---|
| 53 |   <B> <A NAME="tex2html245" |
---|
| 54 | HREF="node8.html">Index</A></B> |
---|
| 55 | <BR> |
---|
| 56 | <BR> |
---|
| 57 | <!--End of Navigation Panel--> |
---|
| 58 | |
---|
| 59 | <H1><A NAME="SECTION00010000000000000000"></A> |
---|
| 60 | <A NAME="sec:intro"></A> |
---|
| 61 | <BR> |
---|
| 62 | Introduction |
---|
| 63 | </H1> |
---|
| 64 | |
---|
| 65 | <P> |
---|
| 66 | The CUDD package provides functions to manipulate Binary Decision |
---|
| 67 | Diagrams<A NAME="13"></A> (BDDs) [<A |
---|
| 68 | HREF="node7.html#BDD">5</A>,<A |
---|
| 69 | HREF="node7.html#BBR">3</A>], |
---|
| 70 | Algebraic Decision Diagrams<A NAME="15"></A> (ADDs) |
---|
| 71 | [<A |
---|
| 72 | HREF="node7.html#Bahar93">1</A>], and Zero-suppressed Binary Decision |
---|
| 73 | Diagrams<A NAME="17"></A> (ZDDs) |
---|
| 74 | [<A |
---|
| 75 | HREF="node7.html#Minato93">12</A>]. BDDs are used to represent |
---|
| 76 | switching<A NAME="19"></A> functions; ADDs are used to |
---|
| 77 | represent function from <IMG |
---|
| 78 | WIDTH="58" HEIGHT="37" ALIGN="MIDDLE" BORDER="0" |
---|
| 79 | SRC="img3.png" |
---|
| 80 | ALT="$\{0,1\}^n$"> to an arbitrary set. ZDDs |
---|
| 81 | represent switching<A NAME="20"></A> functions like BDDs; |
---|
| 82 | however, they are much more efficient than BDDs when the functions to |
---|
| 83 | be represented are characteristic<A NAME="21"></A> |
---|
| 84 | functions of cube<A NAME="22"></A> sets, or in general, when the |
---|
| 85 | ON-set<A NAME="23"></A> of the function to be represented is |
---|
| 86 | very sparse. They are inferior to BDDs in other cases. |
---|
| 87 | |
---|
| 88 | <P> |
---|
| 89 | The package provides a large set of operations on BDDs, ADDs, and |
---|
| 90 | ZDDs, functions to convert BDDs into ADDs or ZDDs and vice versa, and |
---|
| 91 | a large assortment of variable reordering<A NAME="24"></A> methods. |
---|
| 92 | |
---|
| 93 | <P> |
---|
| 94 | The CUDD package can be used in three ways: |
---|
| 95 | |
---|
| 96 | <UL> |
---|
| 97 | <LI>As a black box<A NAME="26"></A>. In this case, the application |
---|
| 98 | program that needs to manipulate decision diagrams only uses the |
---|
| 99 | exported functions of the package. The rich set of functions |
---|
| 100 | included in the CUDD package allows many applications to be written |
---|
| 101 | in this way. Section <A HREF="node3.html#sec:user">3</A> describes how to use the |
---|
| 102 | exported functions of the package. An application written in terms |
---|
| 103 | of the exported functions of the package needs not concern itself |
---|
| 104 | with the details of variable reordering<A NAME="28"></A>, which may |
---|
| 105 | take place behind the scenes. |
---|
| 106 | Click <A NAME="tex2html1" |
---|
| 107 | HREF="cuddExtAbs.html">here</A> |
---|
| 108 | for a list of the |
---|
| 109 | exported functions. |
---|
| 110 | </LI> |
---|
| 111 | <LI>As a clear box<A NAME="31"></A>. When writing a sophisticated |
---|
| 112 | application based on decision diagrams, efficiency often dictates |
---|
| 113 | that some functions be implemented as direct recursive manipulation |
---|
| 114 | of the diagrams, instead of being written in terms of existing |
---|
| 115 | primitive functions. Section <A HREF="node4.html#sec:prog">4</A> explains how to add new |
---|
| 116 | functions to the CUDD package. It also details how to write a |
---|
| 117 | recursive function that can be interrupted by |
---|
| 118 | dynamic<A NAME="33"></A> variable reordering. |
---|
| 119 | Click <A NAME="tex2html2" |
---|
| 120 | HREF="cuddAllAbs.html">here</A> |
---|
| 121 | for a list of the |
---|
| 122 | exported and internal functions. |
---|
| 123 | </LI> |
---|
| 124 | <LI>Through an interface. Object-oriented languages like C++ and |
---|
| 125 | Perl5 can free the programmer from the burden of memory management. |
---|
| 126 | A C++ interface is included in the distribution of CUDD. It |
---|
| 127 | automatically frees decision diagrams that are no longer used by the |
---|
| 128 | application and overloads operators. Almost all the functionality |
---|
| 129 | provided by the CUDD exported functions is available through the C++ |
---|
| 130 | interface, which is especially recommended for fast prototyping. |
---|
| 131 | Section <A HREF="node5.html#sec:cpp">5</A> explains how to use the interface. A Perl5 |
---|
| 132 | interface also exists and is ditributed separately. (See |
---|
| 133 | Section <A HREF="node2.html#sec:getFriends">2.2</A>.) Some applications define their own |
---|
| 134 | interfaces. See for example Section <A HREF="node3.html#sec:sis-vis">3.17</A>. |
---|
| 135 | </LI> |
---|
| 136 | </UL> |
---|
| 137 | In the following, the reader is supposed to be familiar with the basic |
---|
| 138 | ideas about decision diagrams, as found, for instance, in [<A |
---|
| 139 | HREF="node7.html#BBR">3</A>]. |
---|
| 140 | |
---|
| 141 | <P> |
---|
| 142 | <HR> |
---|
| 143 | <!--Navigation Panel--> |
---|
| 144 | <A NAME="tex2html246" |
---|
| 145 | HREF="node2.html"> |
---|
| 146 | <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next" |
---|
| 147 | SRC="icons/next.png"></A> |
---|
| 148 | <A NAME="tex2html242" |
---|
| 149 | HREF="cuddIntro.html"> |
---|
| 150 | <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up" |
---|
| 151 | SRC="icons/up.png"></A> |
---|
| 152 | <A NAME="tex2html236" |
---|
| 153 | HREF="cuddIntro.html"> |
---|
| 154 | <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous" |
---|
| 155 | SRC="icons/prev.png"></A> |
---|
| 156 | <A NAME="tex2html244" |
---|
| 157 | HREF="node8.html"> |
---|
| 158 | <IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index" |
---|
| 159 | SRC="icons/index.png"></A> |
---|
| 160 | <BR> |
---|
| 161 | <B> Next:</B> <A NAME="tex2html247" |
---|
| 162 | HREF="node2.html">How to Get CUDD</A> |
---|
| 163 | <B> Up:</B> <A NAME="tex2html243" |
---|
| 164 | HREF="cuddIntro.html">CUDD: CU Decision Diagram</A> |
---|
| 165 | <B> Previous:</B> <A NAME="tex2html237" |
---|
| 166 | HREF="cuddIntro.html">CUDD: CU Decision Diagram</A> |
---|
| 167 |   <B> <A NAME="tex2html245" |
---|
| 168 | HREF="node8.html">Index</A></B> |
---|
| 169 | <!--End of Navigation Panel--> |
---|
| 170 | <ADDRESS> |
---|
| 171 | Fabio Somenzi |
---|
| 172 | 2005-05-17 |
---|
| 173 | </ADDRESS> |
---|
| 174 | </BODY> |
---|
| 175 | </HTML> |
---|