bdd实现方法及改进方法的研究

《bdd实现方法及改进方法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、兰州大学硕士学位论文BDD实现方法及改进方法的研究姓名：张旭申请学位级别：硕士专业：计算机软件与理论指导教师：李廉20050601兰确久学硪li。≥。N-论文摘要计算机辅助设计(CAD)的很多应用领域，如组合逻辑验证、超大规模集成IU路h'l+㈣(AuIJoiillttjc’resthLLet’ii(；uⅢj『’ntion)、符吁处川!、硬什的形式化验证等都要求能够有效的表示和处理逻辑函数。在许多经典的表示方法中，如真值表、赢=，『泄；等，仃意n元雨数都需要2“个元素束衷示，所需空间随着变量个数呈指数增长，因此很不

2、适用。80年代中翊，Bryant提出了一种有效的表示和处理逻辑函数的方法——用二叉判定罔作为布尔表达式在计算机内部的表示方法，极大的减少了存储布尔公式所需婴的空州。本文对现有的比较成熟的两种BDD包——buddy和CUDD巾的BDD的构造算法进行了分析和改进。文rhI在介绍了关于BDD的基本知识及BDD的基本运算后，给出了BDD包中构造BDD的算法，并分析了该算法存在的问题及相应的改进技术。在此基础上，针对BDD包中构造BDD算法的问题，提出了自己的改进算法：首先是引入了公理系统，将原有的布尔函数进行等价变形，转化

3、与之等价的析取范式，从而布构造的过程巾可以将原来的自顶而下赋值，再自下而上的计算构造BDD结点的过程改进为一个自上而下直接赋值、计算、构造BDD的结点的过程，并在计算的过程中对布尔函数进行了化简，直接消除了无关变量和对应的冗余计算，同时也减少了冗余结点查重的计算量；其次，针对构造过程中存在的大量的重复计算，在构造算法中引入了一个数据结构——计算表，记录计算过程和与之对应的结点。当相同的计算过程出现时，无需再次计算，只要返回对应地结点即可。这样，可以避免大量的重复计算过程，提高了构造算法的执行效率。关键词：二叉判定图

4、；简化的有序二叉判定图；唯一表：计算表；析取范式；重复汁算：冗余结点兰州又。≯硕士。学位论史摘要AbstractEfficientrepresentationandmanipulationofBooleanfunctionsisimportantformanyapplicationfieldsofcomputeraideddesign(CAD)，suchaslogicsynthesischecking，VSILATPGsignaldisposal，hardwaremodelchecking，andSOon．Butt

5、omanyclassicdatastructuresuchastruthtable、binarydecisiontree，anyn-tuplefunctionneed2“elementtorepresent，theneedofstoragearisesexponentiallywiththenumberofvariable．So，thesearenotapplicable．Bryantbroughtoutanefficientmethodto。representandmanipulateBooleanfunctio

6、nin1986一一useBinaryDecisionDiagram，adirectacyclicgraph，astherepresentationofBooleanfunctionincomputer．ThismethodcandramaticallyreducetheneedofstoragewhensavingaBooleanfuaction．ThispapergiveabriefintroductionofBDDatfirst，thenmainlyintroducetheconstruct】methodsof

7、BDDinthefamiliarmatureBDDpackage——buddyandCUDD—analyzetheproblemsintheconstructingalgorithmandrelatedimprovementmethods．Atlast，Igiveanadvancedalgorithm【toconstructaBDD．Therearetwoimprovementsinmyalgorithm：first,theoldalgorithmismadeofatop—downprocessandadown·t

8、opprocess．Inthetop-downprocess，itgiveeveryvariableitsvalue，theninthedown-topprocessitcomputeandconstructtheBDDnodes．Wechangethetwoprocessestoonlyonetop-downprocesstOdothesamethreet