（计算机软件与理论专业论文）Altgt算法在BDD变量最优排序方法中的应用.pdf

兰魁夫学硕| ? 学能论文摘要 摘要 二叉判定图( b d d ) 是表示布尔函数的有效工具，被广泛的应用到逻辑综 合，布尔电路的模拟和测试等领域。一个有效和简化的b d d 将极大的提高模型检 验所能验汪的系统规模以及验证和测试的生成效率。但在现在常用的方法中，变 量顺序的选择是影响布尔函数的b d d 的结构和大小的一个非常重要的因素。目前 b d d 的变量排序的基本方法大致可以分为三剩：启发式变量排序、动态变量排序、 最优变量排序。其中以最优变量排序法的结果最好，但一般来说，时间复杂度也 比较高。本文在f r i e d m a n 等人提出的一种寻找最优变量序的算法的基础上将广 泛应用于人工智能的a + 搜索算法引入到最优变量排序方法中，提出了一种寻找 变量最优排序的新方法。该算法利用人工智能中的a 算法。把寻求变量的最优 排序闯题转变成了在状态空矗j 中寻找最优路径的问题，山于a 算法保证在每次 扩展时选取状态空问最优的状态去生成其子状态，直到达到其目标状态，所以大 部分的状念空间在搜索的过程中被删除了。同时在该算法引入了暂缓插入条件和 提前结束条件，使得该算法的状态空间得到了更进一步的缩减。因此这种办法比 起f r i e d m a n 的最优变量排序算法在处理器的处理时问上和存储器的空间需求上 都有很大的改善。 【关键字】b d d ；最优变量排序；a + 搜索算法；状态空间：估价函数； 兰娴久学硕七学位论文摘要 a b s t r a c t i o n b d di sa ne f f i c i e n tr e p r e s e n t a ti o nt o o lo fb o o l e a nf u n c t i o n s ，a n d i ti sw i d e l ya p p li e di nl o g i cs y n t h e s i s ，s i m u l a t i o na n dt e s t i n go fb o o l e a n c i r c u i t s ，e t c a ne f f i c i e n ta n dr e d u c t i o no fb d dc a r le n l a r g et h es y s t e m s c a l ew h i c hi sc h e c k e db yt h em o d e lc h e c k i n gs y s t e m ，a n di m p r o v et h e c h e c k i n ga n dt e s t i n ge f f i c i e n c y b u tt h ek e yf a c t ，w h i c hr e f l e c t st h e d a t as t r u c t u r ea n ds i z eo fab d dr e l a t e dt oag i v e nb o o l e a nf u n c t i o n ， i st h eo r d e ro ft h ev a r i a b l e s n o w ，t h e r ea r et h r e ek i n d so fb d dv a r i a b l e o r d e r i n gm e t h o d s ：h e u r i s t i cv a r i a b l eo r d e r i n gm e t h o d ，d y n a m i t i cv a r i a b l e o r d e r i n gm e t h o da n dt h eo p t i m a lv a r i a b l eo r d e r i n gm e t h o d t h e r e f o r e ，t h e r e s u l to ft h eo p t i m a lv a r i a b l eo r d e r i n gm e t h o di sb e s to fa l l ，b u ti t s t i m ec o m p l e x i t yu s u a l l yi sh i g h e r i no u rp a p e r ，w eb r i n gt h ew i d e l yu s e d s e a r c h i n ga l g o r i t h mi n i 一一a a l g o r i t h mi n t ot h eo p t i m a lv a r i a b l e o r d e r i n gg i v e nb yf r i e d m a n 2 1 ，a n dp u tf o r w a r dan e wm e t h o dt og e tt h e o p t i m a lv a r i a b l eo r d e r t h i sa l g o r i t h mt u r n st h ep r o b l e mo fs e a r c h i n gt h e o p t i m a lv a r i a b l eo r d e r i n gt ot h ep r o b l e mo fs e a r c h i n gt h eo p t i m a lp a t h i nt h es t a t e ss p a c e s t h ea l g o r it h ma + h o l d st h er u l eo l 。s e l e c tt h eb e s t s t a t et oc r e a t et h es u b s t a t ee v e r yt i m ei te x p a n d su n t i li tg e t st h eg o a l s t a t e s ol a r g eo fs t a t e si nt h es t a t es p a c ei sd e l e t e d a n di no u r a l g o r i t h m ，w ei n t r o d u c el a t e ri n s e r t i o na n de a r l yt e r m i n a t i o nr u l e st o c u ts h o r tm o r es t a t es p a c e s c o m p a r e dw i t ht h ea l g o r i t h mo ff r i e d m a n ，t h i s a l g o r i t h mh a sm o r ei m p r o v e m e n ti nt h em a n a g e m e n tt i m eo fc p u a n dt h en e e d o fs t o r a g e k e y w o r d s ：b d d ，o p t i m a l v a r i a b l e o r d e r i n g ，s e a r c h i n g a l g o r i t h m ，s t a t es p a c e s ，c o s tf u n c t i o n 兰蚋人学硬：l ：学秘论文卢明 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研究所 取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数据、观点等， 均已明确注明出处。除文中已经注明弓o - j 的内容外，不包含任何其他个人或集体 已经发表或撰写过的科研成果。对本文的研究成果做出重要贡献的个人和集体， 均己在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：主叠牡h 兰蛳人学颀t 。f , 2 论殳声明 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大学。 本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向国家 有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阅：本人授权 兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用任何复制手段保存和汇编本学位论文。本人离校后发表、使用学位论文或与该 论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：啦导师签名：茎! 萋f i 期：越丛翌 兰州人学坝i 学位论史，算法庄b d d 变姑最优排j f 算法中的f _ 第一章绪沧 1 1 问题的提出及研究的意义 1 9 8 6 年，e r b r y a n t 提出了用二叉判定图b d d i , 2 l ( b i n a r y d e c i s i o n d i a g r a m ) 来表示和尔函数，和其他表示法棚比，b d d 所用的存储空m 较少，因此，研究 人员将b d d 引入到了模型检验中，使得模型检验所能验证的系统规模得到了很 大的提高。同时人们发现变量的顺序刘于个巾尔函数的b d d 的大小有着非常 重要的影响，例如一个表示加法器的b d d 在某些变量的排序下其结点的个数为 d ( 拧) ，而在某些变量的顺序下其结点的个数为0 ( 2 “2 ) 。因此，一个好的变量序 不仅能够使表示布尔函数的b d d 的结点的个数显著减少，而且还能极大的提高 验证和测试的生成效率。所以如何确定变量最优顺序的问题就成为b d d 理论中 的一个重要问题。 1 2 国内外研究的现状 近些年来，国内外的研究者对b d i ) 的变量排序问题进行了大量深入的研究。 目前的方法大致上分为三种类型。第一类是启发式排序方法l 巩圳j ，这类方法主 要是根据电路本身所提供的各种启发式信息以及先验知识来指导变量排序。如果 所采用的启发信息或先验知识对某个电路比较合适，可能产生一个满意的变量顺 序，减少b d d 的结点数。第二类足动态变t l + l l + j i ，这类办法足以一个原始的变 量顺序为基础，在构造b d d 的过程中，通过动态地调整变量的顺序，并观察b d d 体积的大小，从而找到一个较好的变量顺序。这类方法一般不能得到变量的最优 序，产生的b d d 的大小通常是最优变量排序的b d d 的大小两倍甚至以上。第三类 方法是最优变量排序1 9 一o l ，这类方法得到的结果是最好的，但是一般情况下这种 方法的时问复杂度较高。另外，还有遗传算法排序方法i ：这种方法通过模仿臼 兰州人学坝i 学佗论文_ + 算法在b d d 变姑最优排序算法中的席j h 然界的生物进化通过选择父体、交叉、变异来寻求最优解的。种方法。目前大部 分的b d d 软件包都采用了动态变量排序方法。 1 3 本文的研究成果 基于这个出发点，本文在前人研究的基础之上，将广泛应用于人工智能的， 搜索算法i 。2 j 弓i a 到最优变量排序方法中，提出了一种寻找变量最优排序的新算 法。利用爿+ 搜索算法能够把搜索过程中的大部分状态空间予以删除，以更小的 时间和空间代价得到变量的最优排序。 1 4 本文的组织结构 本文按照下面的顺序组织全文： 第一章是本文的绪论部分。主要介绍问题的提出，国内外当前研究的状况， 以及本文的研究成果。 第二章是b d d 的基础知识，主要给出了b d i ) 的基本概念以及变量的顺序对于 b d d 结构和大小的影响。 第三章是变量排序的方法，主要介绍了启发式变量排序方法、动态交换变量 排序方法和f r i e d m a n 等人提出的最优变量排序方法1 9 1 的理论知识和算法。 第四章足，搜索算法在最优变量排序i i 的应用，详细介纲了，搜索算法， ，搜索算法在最优变量排序中的应用，并且给出了算法描述和算法分析。 第五章是结柬语，是对本文的简要总结。 兰州人学碳i 学位论文a + 算法在b d d 变毓最优排序算法中的麻川 第二章b d d 的基础知识 模型检验虽然足自动化的方法，但是山于受到处理器速度和存储器容量的限 制，所能验证的系统规模较小，影响了它在实际应用中的使用。1 9 8 6 年，e b r y a n t 提出t i t | - x n 定图b d d ( b i n a r yd e c i s i o nd i a g r a m ) 米表示斫j 尔函数，与其他 表示布尔函数的方法如真值表，立方法相比，b d d 所用的存储空间较少，因此 极大的提高了模型检验所能验证的系统规模，使模型检验技术更广泛的应用到了 实际的工业设计中。本部分主要介绍b d d 的基础知识。 2 1 布尔函数与二叉判定树 布尔函数是由变量和定义在其上的逻辑算子构成的，是表示逻辑关系的重要 工具。本文中用符号“+ ，表示“或运算，用符号“u ”表示“与”遗算，用符 号“一表示“非”运算，用符号“o ”表示“异或”运算，用符号“o ”表示 “同或”运算即“o ”的补，用符号“”表示布尔和、用符号“兀”布尔积， 这些运算都是布尔函数运算。例如：设，和g 是定义在某变量集合上的布尔函数， 则 = 码是该集合上的一个布尔函数，如果对所有变量的一组赋值；，厅( ；) = l 当且仅当八；) = l 并且g ( ；) = 1 。另外在本文中对所有变量的赋值均为l 或者为o 的常函数分别用l 和o 表示。 定义2 1 ( 限定变量) ”3 ：如采有布尔函数，( ，x 2 ，矗) 并且有 o ，1 ) ， 那么把变量赋值为女所得到的，的结果称为f 在变量t 处的限定，我们记作 ，l 。，变量称为限定变量， _ 厂k 扣( 一，x 2 ，矗) = ，( x l ，t l ，k ，+ l ，) 定义2 2 ( 香农展开) ：一个n 变量的函数，在变量t 处可表示为： f ；i 矿i x , o + 一日厂i 。+ t 兰州人学仔i | 学位论史 算法往b d d 变量虽优排序算法中的府j h 称上武为幽数f - & - 变r x , 处的香农服jj ：，把变量t 称为函数厂的分解变量， 称，k 。为关于葺的负伴因子，称，i 。为关于晌诈伴因子。利用香农展丌可 以把布尔函数展开为一些简单函数的和。见图2 1 。从图中可以看到，根结点对 应原函数厂，矗予结点表示函数，l 。ot 有子结点表示函数，i 。+ 。 i 。+ _ o厂l - 围2 1 ，在葺处的展开 更进一步，利用香农公式对一个前i 尔公式进行递归展开，当，i 。和，k 。 等于常函数1 或0 时，可以用l 或者0 标记该结点，递归过程中止，这样最终形成一 棵二叉树，我们把这样的一棵二叉树称为该布尔公式对应的二叉判定树。因此， 任何一个布尔公式的递归香农展- 歼都对应着一个二叉判定树。我们把标记为0 或l 的结点称为终结点，其余的结点称为非终结点。用二叉判定树表示一个布尔函数 时，所需的存储空间随着变量数目玎呈指数增加，即结点数为2 ”。一1 ，并不比真 值表优越多少。图2 2 给出了i g l 数f = x , d x 2 + x 3 - l r 4 的二叉判定树，结点数目为3 l 。 凹2 2 函数，= i f k 2 + b 的二义划定树 兰州人肇i 哦l ：学 证沦义，算法作b d d 变城最化摊序锋法中的心川 2 2 二叉判定图( b d d ) 实际一l i 。从陶2 2 巾我们可以看到：一叉判定树巾的些结点足重复表示的， 比如图2 2 中最底下一层上的0 、l 结点，将这些标记相同的结点合并后并不改变 所表示的撕j 尔函数而此时树就变成了佟i ，这利- 用于存储前i 尔函数的图的数据结 构就被称为二叉判定图( b d d ) 。定义如下： 定义2 3 ( 二叉判定图b d d ) 1 4 1 ：b d d 是- - 个有限个结点的有向无环图g = ， 其中v 是g 中所有结点的集合，e 是g 中所有边的集合。v 中的结点分为端结点( 用 方框表示) 和非端结点( 用园框表示) 。每个端结点h 用o 或l 标识，无射出边 每个非端结点心用变量v 砸k ) 标识，并且有两条射出边：一条指向右子结点 f ( ) 的t h e n 一边( 用实线表示，表示v a v ( v 2 被赋值1 ) ，另一条指向左子结点，d ( 匕) 的e l s e 一边( 丌1 虚线衣示，表示v a t ( v , ，) 被赋值0 ) 。 图2 3 是布尔函数f = 吨+ 而吼的b d d 表示，与图2 2 所采用的二叉判定树 相比，只用了8 个结点。从图中可以看出，从b d d 根结点到一个终结点的一条迹就 对应着变量的一组赋值，由该分支的端结点所标识的值就是变量在这组赋值下所 对应的函数值。 i 笙| 2 3 布尔函数f = 五十屯吼的b d d 表示 i | e v e ll l e v e l2 l e v e l3 l e v e l4 兰州人学颂i ：学位i 它义 + 算法住b d d 变甜最优排序算法中的廊川 定义2 4 ( o b d d ：有序二叉判定图) 1 2 1 ：一个b d dg = ，如果在变量集合 上满足全序关系 ，并且满足下述条件：对任意非端结点“e v ，如果v v 是u 的 左子结点或者右子结点，且v 也是二怍端结点，那么必有v a f ( u ) v a r ( v ) 。 注意图2 ，3 的二叉判定图，处于同一层所有的结点都是楣同的变量( 例如在 1 + 1 2 3 中l e v e l3 层上所有的结点都是x 4 ) 。也就是说，对于一个二叉判定图如果 它的所有从根结点到终端结点的路径上各变量按同一顺序出现，那么这样的二叉 判定图我们称为有序的二叉判定图( o d b b ) 。图2 3 就是稚尔函数f = 五十屯吼 在变量顺序为x 3 屯 下的o b d d 表示。 定义2 5 ( r o b d d ：简化的o b d d ) 1 2 1 ：如果一个o d b b 满足下面的两个条件，那么 我们称它是简化了的o d b b ，即r o b d d 。对于任意的“、v v ，若“v ，则 f u n c ( u ) f u n c ( v ) 。 该条件保证了结点的唯一性，即不存在这样的两个不同的结点，它们具有同 样的变量名和左右子结点。 图2 3 就是卸尔函数厂= 工m ：+ 屯吼的l l o b l ) d 表示，以后的讨论中如果b 叻未 特别说明均指r o b d d ，从上面的讨论中我们可以得到下面的定理 定理2 1 ：给定一个椰尔幽数，订唯一f f j i , t o t + t ) o 与之对应。 另外我们还能得到下面的结论： i 嘶个巾尔函数的b d d 表示匙州构的当儿仪当两个函数足等价的。 2 一卟斫均；函数足可满足的n 仅当它的i i d i ) 表示的有个终结点为l 。 3 一个布尔函数是永真的的当f l 仪当它的b d d 表示只有一个为1 的终结点。 4 如果一个前i 尔函数不含变最x ，则它的b d d 表示不含v a r ( u ) = x 的结点“。 6 兰州人。坝i 学位论义a + 算法九b d d 变蛙蛀优排序算法。i 的应j 2 3 构建b d d 的方法 i - 节的论述我l j 1 j = n 道任何一个靠尔函数都可以采用b d d 的形式加以表述， 它的最大特点就是减少了结点的数目，便于存储。本节主要讨论通过给定的布尔 函数构建b d d 的两种方法。 2 3 1 二叉判定树的b d d 构造过程 对于一个布尔函数先构建其相应的二叉判定树，通过三条变换规则将其变换 为表示同一函数的b d d 。下面通过一个例予说明如何把一个函数厂= x i f k 3 + 屯m ， 表示为相应的二叉判定图。 步骤一：构建布尔函数f = x t k 3 + x 2 在变量顺序_ x 2 而下的二叉判定 树，如图2 4 所示。 步骤二( 变换规则一) ：删除重复的端结点而只保留其一，如图2 5 ( a ) 所示。 步骤三( 变换规则二) ：对：啦终结点“、p ，如果有以下三式成立： a ) v a r ( u ) = v a r ( v )b ) h i ( u ) = h i ( v )c ) t o ( u ) = l o ( v ) 则删除其一，并将删除结点的所有入边指向保留结点，如图2 5 ( b ) 所示。 步骤四( 变换规则三) ：对非终结点“，如果有h i ( u ) = l o ( u ) ，则删除结点u 并将“的所有入边指向l o ( u ) ，如图2 5 ( c ) 所示 兰州人学硕i ：学位论殳 a + 锋法住b d d 变鲑最优排序算法中的戍川 幽2 4 函数f = 五出，+ 屯在变量顺序而 t g n bi t e ( f ，丘，o ) 4ff， 5 fg f 【好 i t e ( f ，0 ，g ) 6ggg 7 x o r ( f ，g ) fog i t e ( f ，d ，g ) 8 兰州人学坝i 学位论立 + 算法在b d d 变蛙殿优排序算法中的麻川 编号 布尔远算下集表达j 弋等价形式 8 o r ( f ，g )f + g i t e ( f ，1 ，g ) 9 ，d 拧( ，g )f 斗g i t e ( f ，0 。0 ) l o x n o t ( f ，g )fogi t e ( f ，g ，石) 1 1 n o t ( g )g i t e ( g ，0 ，1 ) 1 2f g f + gi t e ( f 。l 。d ) 1 3 t 、，o r ( f )fi t e ( f ，0 ，1 ) 1 4g 墨f ，+ g i t e ( f ，g ，1 ) 1 5 n a n d ( f ，g )脚i t o ( f ，石，1 ) 1 61l i ( 续表) 定义2 7 ( 顶层变量) ：1 3 1 一个函数f 的顶层变量就是指与这个函数根结点 相关联的变量。 根据香农展丌式可以递归的计算一个函数的真值下面的递归公式用来计算 用b d d 表示的f ，g ，日的i t e ( f ，g ，h ) 的值。假定p 是逻辑函数f , g ，h 的顶层变量， 并且令z = i t e ( f ，g ，h ) ，那么就有： z = 泫。+ v - - z f = v ( f g + f h ) ，+ v ( f g + f h ) f = v ( e g r + e e ) + f ( c g ，+ n o = i t e ( v ，i r e ( f , ，q 。q ) ，i r e ( f , ，g ，珥) ) = ( h 触( e ，玩，鼠) ，u e ( f ，g ，h i ) 递归终i i ：的条件魁：i t e ( ! ，f ，g ) = i t e ( o ，g ，f ) ：i t e ( f ，l ，o ) = f ；i t e ( f ，g ，g ) = g 。 举例说明如下：令f = a + b ，g = 册，h = 6 + d ；i t e ( f ，g ，日) = a c + 万劢。在给 定变避序为：甜 b f j 的情况下，嘶j 尔函数f ，g ，hp 2 及i t e ( f ，g ，h ) 的b d d 表示如图2 6 所示。下面是讹的计算过程： 兰州人学硕l ：学位论文，算法住b d d 变量最优排序算法中的应圳 i t e ( f ，g ，h ) = ( 口，i t e ( f ，g 。，h o ) ，j 招( e ，皖，h i ) ) = ( 口，i t e ( 1 ，c ，h ) ，i t e ( b ，0 ，h ) ) = ( a , c ，( 6 i l e ( b b ，o b ，风) i t e ( 岛，坼) ) ) = ( 口，c ，( 6 ，i t e ( 1 ，o ，1 ) ，i t e ( o ，0 ，d ) ) ) = ( 口，c ，( 6 ，0 ，d ) ) h 爰帆刚 茂豫 l 0 l 0100d 图2 6 函数f ，g ，胃币l z = i t e ( f ，g ，日) 的b d d 表示 从1 - 而的分析和举例我f f n - l 以看到，给定函数f ，g ，h 的b d d 表述f ，g ，h ， 选择变量y 为f ，g ，h 中结点序最大翥，加算子能有效地使用递归进行运算得到 函数z = i t e ( f ，g ，) 的b d d 表示。山于妇算子直接对b d d 进行运算，并且能够实 现所有的一元和二元逻辑运算，因此，加迭代公式成为当前b d d 运算包( 例如 b u d d y 、c u d d 等) 的核心，下面给出核心i t e 算法的流程： i t e ( f ，g ，) ( 矿( 满足结束条件) r e t u r n 结果： v = m a x ( f 寸i n d e x ，g 寸i n d e x ，1 1 呻i n d e x ) ； t = i t e ( f e ，g ，h e ) ； e = i t e ( 昂，g e ，坼) ； f ( t e ) r e t u r nr ； r = f i n d a d d n o d e t a b l e ( v ，t ，e ) ； r e t u r n 置： ) 1 0 兰州人学坝i j 学位l 仑义锌法拒b d d 变龄履优t 1 i ：序算法中的应川 在实际应用巾构建电路的b d d 时，首先读入电路的描述信息，确定变量 的顺序，从第一个输入变量开始构建b o o 。在构建过程中，递归的调用妇算法流 程，进行深度优先搜索，然后逐级返回。如此循环，直到最后一个输入变量。下 面给出了个通过妇算子构建图2 7 所示的简单组合电路的b d d 的过程。 阔2 7 组合电路的b d d 构造 根据图2 7 ，经过i t e 算予运算构造函数k 的b d d 的过程如下： h = i t e ( f ，g ，0 ) 2 ( 玉，抛( ，鼠，o ) ，妇( 厶，如，o ) ) = ( 而，g ，0 ) j = i t e ( i ，0 ，1 ) = ( 而i t e ( i , 3 ，0 ，1 ) ，i t e ( i j 。，o 1 ) ) = ( 而，0 ，1 ) k = i t e ( h ，1 ，_ ，) 2 ( 葺，i t e t h , , ，l ， ) ，加( ，1 ，厶) ) 。“，i t e ( g ，】，- ，) ，i r e ( o , ! ，) ) 2 ( 而，( x 2 ，i t e ( g , ，1 ，厶) , i t e ( g z 2 ，1 ，厶) ) ，) = ( x i ) ( x 2 ，i t e ( ! ，l ，_ ，) ，i t e ( o ，1 ，埘，) = ( x l ，( x 2 ，1 ，_ ，) ，j ) 兰州人学彤学位论史+ 葬法赴b d d 变域昂优排序算法中的戍川 2 4 变量顺序的影响 尽管b d d 是表示稚尔函数的非常有效的方法，能够在很大程度上减少存储的 结点数。但是表示一个布尔函数的b d d 的结构和大小依赖于变量的顺序，变量顺 序不同，结点数= f _ _ 微人的差别。冈2 81 f i i l 了钿尔函数= x n f l r 2 + x 3 吼的在两种 变量顺序下的b d d 表示。( a ) 的变量顺序为x 3 而，其非终端结点数为 4 个。( b ) 的变量顺序为屯 而( x 4 ) i 鳘i2 8 函数f = 工i 啦+ 墨哦在不同变龄顺序下的b d d 为了便于本文以后的论述，做如下定义： 定义2 8 ：对于一个1 1 变量的稚尔函数厂( ，x 29 69 ) ，它的n 个变量的任 意一个排序记作万，即如果函数的个变量置是某一个变量排序万中的第k 个 变量，记作x ( k ) = i ( i 是变量t 的下标，为了简便期问。在以后的论述中我们用 变量的下标来代脊变鬃) 。例如对图2 8 ( a ) 所示的变帚顺序丌= ( 3 ，4 ，l ，2 ) ， 则丌( 1 ) = 3 ，疗( 3 ) = l 。 定义2 9 ：对于1 个枷尔函数f ( x 。，x 2 ，) ，在给定一个变量排序玎下的 兰州人学坝i ：学位沦文d + 算法在b d d 变鲑最优摊序算法中的应川 函数厂的b d d 表示我们记作b d d ( f ，厅) ，例如，对于图2 8 ( a ) 所示的函数，的 b d d 我们记作b d d ( x i 凸电+ x 3 k 4 ，( 3 4 ，l ，2 ) ) ，图2 8 ( b ) 所示的函数厂的b d d 我们记作b d d ( 五汝2 + 屯d r 4 ，( 3 ，1 ，4 ，2 ) 卜 更进一步，对于图2 8 所示的函数= 工，+ 屯d t 4 的情况，我们可以推广 到更加一般的情况： a t b t + 岛+ + 丸 对于上式如果变量的排序是q 6 l a n 吒，那么得到的b d d 有2 n 个非端结 点，他们对应着2 n 个变量的顺序，而对变量的顺序q 6 i i + 1 、c o n t i n u e ； p u tt h en o d ei nt h ep r o e e s s i n g l i s t ； f o re a c hn o d ei nt h ep r o e e s s i n g l i s t g e l ，f o i ，e o ，曩ic o f a c t o r s ； c r e a t e o r f i n d e a n df ： c r e a t ean e wda n dp u ta f o r w a r d i n gp o i n t e ri na ； a p p e n dt h el i s to f f o r w a r d e dn o d e sf o ri n d e xi ； j 1 6 兰州人学域i j 学位论史 a + 算法住b d d 变姑最优排序算法中的应j i p e r f o r ms o m eb o o k k e e p i n g ； ) e n ds w a p 3 2 启发式变量排序方法 这利方法二1 三要是根据电路木= f ： 所提供的各种启发式信息以及先验知识来指 导变量排序。如果所采用的启发信息或先验知识对某个电路比较合适，可能产生 一个满意的变量顺序，减少b d d 的结点数。目前，对于一些肩发式变量排序的方 法大致可分为以下两类： 1 ) 以标准门的b d d 为基础。从原始输入到输山，通过逻辑拼接，有效地 完成电路的b d d 构造。在这种情况下，电路结构特征对整个输出b d d 的构造有重 要的影响，因此在b d d 构造过程中一般使用相应的规则来指导b d d 的获取，以减 少b d d 的结点数。 2 ) 直接计算原始输人端对输出端的影响，根据其影响的大小排定变量顺 序。一般采用的方法是，首先对输出端赋一个值，然后按照一定的方法，计算出 每一个输人变量的值，把赋值最高的输人变量排在变量顺序的前面，并从电路中 删除，然后对r i _ l 路中余下的变量循环进行同样的处理，直到确定所有变量的顺序。 面对各利一各样的组合电路，要想找到一个合适的启发信息和先验知识是一件 十分困难的事情。目前的各种启发信息和先验知泌仅仅是针对一些基本的或特殊 的电路，因此下而仪对一些先验知嘭 做一个简啦的论述。 规则一：对于无公共输入的电路，如果是与( 与非) 门拼接，则以到达终端结 点取l 值的路径少的b i ) d 为基本门放在上面较好。如果是或( 或非) 门拼接，则以 到达终端结点取o 值的路径少的b d d 为基本门放在上面较好。 例如图3 3 ( a ) 中的电路对两根引线6 和7 的b d d ( 图3 3 ( b ) ，图3 3 ( e ) ) 根据6 和7 的不同次序，所获得的引线8 的b d d 结点数相同，但路径数、路径长 1 7 兰州人学埘i j 学位沦t f 【： a + 锋法住b d d 变越蛙优排序算法中的应j 度有所差异( 测试速度提高) 。剥引线6 的b d d 作为基本门放在上面( 图3 3 ( d ) ) 和引线7 的b d d 放在上面( 图3 3 ( e ) ) 作一比较，两者的差异见表3 1 ，显然引线 7 的b d d 放在一l 二面优越。同样，考虑幽3 3 ( r 1 ) l l 输出引线的与门改为或门，而其 它不变，则弓l 线6 和引线7 的b d i ) 分j j i j 作为) 点本门放和卜而所得剑的引线8 的 b d d 见表3 2 。由此可见，引线6 的b d d 作为基本门放在上面较好。 5 刚3 3 ( b )( c ) 兰州人毕倒。学”涂虻，i 许认订：b d d 变带最优惜j f 算法巾的应川 农3 ：j ! i f j 的| j 1 ) i 】比较 农3 2 或f j 的b d d 比较 类，艘j j l 线6 扯i -引线7n i 上 结点数55 路径条数 j 06 i 路托k 坡 ：1 62 0 平均k 度 3 63 3 类j 弘q i 线6 札一i -日l 线7 在上 结点数55 _ i ! i 径条数69 k 坡 2 03 2 平均1 支度 3 33 6 捌则二：对j ：重汇聚的输入线，在i j i ) d 的构造时应首先考虑。 规则三：在构造b d d 时为了获得i n 路i i | i i j 引线的值，应考虑在终端结点处构 造丢失的变量分支。 规则四：对_ 丁待拼接的b d d ，如果输入b d d 来自电路不同的层应首先考虑 层数相对小的输入b d d 并把它作为基本b d d ，而层数大的输入b d d 作为副本。 规贝j j i l i ：对多输：l i 电路为达到结点的兆亭，应使输“l j 亭的变量保持不变 的次序并尽可能地放在靠近终端结点的位置。 山于篇幅关系，对于这些预处朋! l 乜路的启发式信息和先验知识不再一一列 举。但是如果在构建组合电路的b d d 时能够有效的利用这些知识。不仅能够使 b d d 的结点数大量减少，降低对存储空问的需求，而且还可以极大的提高测试的 效率。因此在特定的f 乜路中，合p e 运用荐种扁发式信息有着非常重要的意义。 3 3 最优变量排序法 这利方法足利门j 确定的算法米得到变艟的最优排序，从2 4 的讨睑我们知道 变量的顺序对i d d 的大小影响很大，因此寻找一种快速的变量最优排序的算法一 直是人们研究的重点。对于最优排序算法，在i 6 1 巾已经提到过一种，但这种算 法找到最优变量序的时间复杂度为o ( n1 2 ”) 。为此，在 9 9 0 年，f r i e d m a n 等人 提出了一利一新的找到最优变量序的算法一i ，浚算法将原来算法的时删复杂度降低 兰州人半碗i j 学位沦殳，算法在b d d 变量最优排序算法中的应川 为了o ( n 2 3 ”) 。那么，在变量个数为5 - 8 之闻时算法【9 1 的运行时问将远远小于 算法【1 6 1 的运行时问。 下面我们给出f r i e d m a n 最优变量排序算法的一个描述。首先，我们将说明 算法中使用到的符号表示： 如果f 表示一个建立在变x i ，x 2 ，矗之上的布尔函数，那么： 1 ) 该算法中的变量顺序是我们在定义2 3 中定义的变量序的逆序。 2 ) 如果6 i ，b 2 ，6 ，( o ，1 ) ，并且f ，f 2 ，f ，表示了( 1 ，2 ，打) 中不同的数字，则 ，i 。”2 ( 厂0 小，一k 畸 3 ) 如果， l ，2 ，刀) 。那么，定义n u ) 为建立在 l ，2 ，打) 上的序的集合。 并且该集合中每一个序满足前l 川个元素构成了集合，。即： h ( ) = 协：7 1 - 是集合 1 ，2 ，h ) 上的序并且 石【l 】，r 2 l ，万【i 州) = n 4 ) 如果，y l ，2 , - - - , 行) ，并且提集合 l ，2 ，以上的序，那么e o s t , ( f , 石) 表 示函数，在变量序疗下的b d d ( 电为b d d ( f ，露) ) 中，变量v 对应地结点的个数。 这样以来，要找到最优b d d 表示，即是要找到绐点个数最少的b d d 表示。 这个问题就可以转化为找到一个变量序丌，使得在该序下：。c o s i ，( 厂，石) 最小。 该算法主要依据以下两个定理： 定理3 1 1 9 1 ：如果，互 l ，2 ，”) ，且女= 仆v ，。那么存在一个常量c ，使 得对于任意的，兀( ，) ，都有：如果万( ) = v 贝l | c o s t ，( ，丌) = c 。 定理3 2 【9 1 ：位于前k 层变量所对应的结点数仅依赖于这k 个变量的顺序， 而与另外n k 变量无关。 算法9 1 的描述如下： f o rk 卜lt ond o f o re a c hk - e l e m e n t s u b s e t ， l ，2 ，h ) 兰州人学坝i 。学位论文a 算法在b d d 变量最优排序算法中的廊川 c o m p u t ey f l ，t a b l e fa n dm i n c o s t f | b e g i n m a i n c o s t ，卜o o ； f o re a c hv id o b e g i n ，e v a l u t ec o s ，w i t he a c hp a i r ( v ，万，- ) + ， i d ( t o ，i ) 卜n f ，f o r e a c h p a i r t o ，t 1 ) c o u n t 卜m i n c o s t ，一l ， l e ti i i z ，一i d e n o t e t h ee l e m e n t s o f i ，h 一i f o r e a e hi e ( o ，l “d o b e g i n ，0 + - t a b l e t ( ， ( = 6 l ，一之丸一 ，= o ) f l + _ t a b l e ，一 ，i ( = 6 i ，k = 丸i ，= i ) l ft o = f t h e nt e m p t a b l e x , = 6 i ，。= 丸 七_ e l s eb e g i n 疆i d 【l n ，t l ) = n i lt h e nb e g i n t h ep a i r ( t o ，) i sn e w * 耐( ，0 ，i ) = c o u n t ； e n d t e m p t a b l e x , , = 屯，。= 钆一 扣i d ( t o ，t 1 ) 日q d e n d * f o r e a c hg - ， 2 l 兰州人学颂i 哔位论立 a + 算法任b d d 变始最优排序算法中的戍川 i fc o u n l m i n c o “，t h e nb e g i n m i n c o s l 一c o u n l e n d 产f o re a c hv * e n d 产f o r e a c h1 + ， r e t u r n l ，2 ，川 e n d 丌，卜( v ，石h ，) ； t ab l e ，_ t e m p t a b l e 从上边的算法描述中。我们可以看到，对于变量集中的任何一个予集 i l ，2 ，n ) ( 其巾子集，的势定义为k = i ，i ) ，我们按照其势逐渐增长的方式依 次去计算每一个j 的下列三个值： 1 ) 埘n c 0 万兀( ，) 下，所有z c o s t ，( f ，石) 的最小值。初始状态下， 2 ) 乃兀( ，) 中对应于m i n c o s t ，的变量序。根据定理3 2 ，对于在变量序中 有，r 【f 】= 珥【j 】( 1 f k ) 的每一个变量序z 都满足： c o s l ，( 玎) = m i n c o s t f 惟， 初始状态下，我们设置= ( ) ，没有任何的变量。那么，我们的问题就进 一步转化为找到这么一个可以得到禽有 伽( h “。1 个非终结结点的b d d 的变 量序，。i 。 3 ) t a b l e ，一个将 0 ，l r 。映射为b d d ( f , ，万) 中的终结结点( t r u e 或 f a l s e ) 或，中的结点的真值表。 i 于b d d ( f , 万) 中关于，的结点有m i n c o s 6 个 加上两个终结结点，所以真值表中的取值就有m i n c o s t t + 2 个。 为了区分每一个表示，中的变量的内部结点，我们用一个介于1 到m i n c o s t 兰州人学坝i = j 1 位论殳 ，i 算法枉b d d 变堪最优l i n t y 算法中的戍川 之问的数值米表示每一个内部结点。那么，真值表中的映射关系可以表示为：对 于不属于，的变量的任何一组取值i = ( 6 i ，6 2 ，既一。) ，其结果部可以映射为 b d d ( ，厂，丌) 中表示函数f l h 。一。：h 。的结点。 衲始状态，岍r ，为空。设t