（电路与系统专业论文）bdd及其在电路故障检测与可靠度中的应用研究.pdf

辅师范大学硕士学位论文 ￥5 9 477 2 b d d 及其在电路故障检测与可靠度中的应用研究 摘要 二元判决图b d d ( b i n a r yd e c i s i o nd i a g r a m ) 是逻辑布尔函数的一 种高效表示方法，在计算机科学以及数字电路与系统等领域中有广泛的 应用。本文首先介绍了b d d 的原理与相关结论，说明了变量编序对于 b d d 规模( 节点数和路径深度) 大小的影响。在此基础上，提出了在 b d d 的建模中一种简单、易行的编序算法，该算法不涉及其他领域的概 念，容易理解。 其次，对b d d 包的建立进行了讨论，并以现在较为流行的i t e ( i f t h e n e l s e ) 算法为依据，用c + + 语言进行了b d d 的构建。能完成对 任意基于c d l 语言描述的组合逻辑电路或布尔函数，实现其b d d 表示 并通过对b d d 的操作实现对相应组合电路或布尔函数的操作。 最后，研究了基于b d d 的组合电路的故障检测方法和基于b d d 的 网络可靠度的计算方法等两方面的应用。b d d 应用于数字电路的固定型 故障检测，建立的故障节点的检测b d d 可以比较方便地得出电路故障的 测试矢量，相比传统的测试算法，避免了庞大的反向回溯过程。关于网 络可靠度，在已有结果的基础上，提出了一种利用二元判决图计算网络 可靠度的方法，该方法将网络的最小路集用二元判决图来表示，并得到 最小路集的不交和，最后获得网络的可靠度。该方法所用的二元判决图 的规模较小，并且可以计算出在不同故障率条件下、不同时间长度下的 网络可靠度。 关键词：二元判决图；b d d ；i t e 算法；故障检测；网络可靠度 束经侔_ 肴、导哪葡氨 匆全文公布 华南师范大学硕士学位论文 r e s e a r c ho nb d da n di t sa p p l i c a t i o n st oc i r c u i t st e s t g e n e r a t i o na n d r e l i a b i l i t y a b s t r a c t b d d ( b i n a r y d e c i s i o nd i a g r a m ) i st h es t a t e - o f - t h e a r td a t as t r u c t u r ei n l o g i cf u n c t i o n i ti sw i d e l yu s e di nt h ef i e l d so fc o m p u t e r s c i e n c ea n dd i g i t a l c i r c u i ta n ds y s t e m f i r s t ，t h i sp a p e ri n t r o d u c e st h ep r i n c i p l ea n dc o r r e l a t i v e c o n c l u s i o n so fb d d ，a n di l l u m i n a t e st h ei m p o r t a n to fv a r i a b l eo r d e r i n gt oa b d d as i m p l ea n de a s yu s i n gv a r i a b l e o r d e r i n ga l g o r i t h mi sp r e s e n t e d ， w h i c hd o e s n ti n v o l v ei nt h ek n o w l e d g eo fo t h e rf i e l d s s e c o n d ，t h i sp a p e ra l s od i s c u s s e st h ec o n s t r u c t i o no fb d d a c c o r d i n g t ot h ep o p u l a ri t e ( i f t h e n e l s e ) a l g o r i t h m ，w ec o n s t r u c tt h eb d d b y c + + p r o g r a m i tc a ng i v eb d dp r e s e n t a t i o no f b o o l e a nf u n c t i o no ra r b i t r a r y c o m b i n a t i o nl o g i cc i r c u i t sw h i c ha r ep r e s e n t e db yc d l ，a n dc a nr e a l i z e d i f f e r e n to p e r a t i o no fb o o l e a nf u n c t i o nb yt h eo p e r m i o nt ob d d f i n a l l y ，w es t u d yt w oa p p l i c a t i o n so fb d d t h ef i r s t o n ei st h ef a u l t d e t e c to fc o m b i n a t i o n a ll o g i cc i r c u i t s ，t h et e s tv e c t o rs e to ft h ec i r c u i tc a n b eo b t a i n e dt h r o u g h c o n s t r u c t i n ga t e s tb d d c o m p a r e dw i t ht h et r a d i t i o n a l a l g o r i t h m s ，t h i sm e t h o da v o i d se n o r m o u sb a c k t r a c k i n gp r o c e s s t h es e c o n d a p p l i c a t i o n i st h en e t w o r k r e l i a b i l i t y b a s e do n b d d r e l i a b i l i t y i sa n i m p o r t a n tp a r a m e t e r i n e v a l u a t i n g t h e p e r f o r m a n c eo fac o m m u n i c a t i o n n e t w o r k an e w a l g o r i t h mo fc o m p u t i n gn e t w o r k sr e l i a b i l i t yb yu s i n gb i n a r y d e c i s i o nd i a g r a m s ( b d d ) i s p r e s e n t e di nt h i sp a p e r t h ea l g o r i t h mc a ng e ta m u c hs i m p l e rb d d d i a g r a mt h a nt h eo t h e ra l g o r i t h m s ，a n dc a nr e d u c et h e c o m p l e x i t yo f t h ec o m p u t a t i o n e f f i c i e n t l y k e y w o r d s ：b i n a r y d e c i s i o n d i a g r a m ；b d d ；i t ea l g o r i t h m ；f a u l t d e t e c t i o n ；n e t w o r k sr e l i a b i l i t y 华南师范大学硕士学位论文 第一章绪论 本章说明了本文的研究目的、理论和实际意义，以及每章的主要内 容。论述和总结了目前国内外关于b d d 的研究状况，并展望了以后的研 究方向。 1 1 研究目的与意义 b d d 1 ，2 1 是计算机科学和数字系统设计的基础。它作为简洁的布尔函 数描述被广泛的应用于集成电路计算机辅助设计的验证、测试、逻辑综 合【3 4 5 】等领域。对于不同形式的布尔函数，只要其真值表相同，那么实 际上它们是完全等价的逻辑函数。结合图论的知识，可以为之建立一种 图的表示形式，因为这种图的取值只有0 和1 两种，所以也把这种图称 为二元判决图( b d d ) 。在实际应用中，数字控制系统、计算机辅助设计 ( c a d ) ，计算机辅s j n 试( c a t ) 、人工智能( a i ) 以及可编程控制器等领域 的许多问题都可以表示成一系列关于布尔函数的运算，这些运算有赖于 布尔函数的符号表示和算法的有效性，所以都可以用b d d 的方法进行研 究。 对于一个逻辑函数来说，要对它进行操作，首要的是产生一个有效 的表达方式，在这个基础上才有可能对它进行研究。因此，首先是对逻 辑函数表示式的研究，在这个过程中产生了很多算法，其中包括基于真 值表、卡诺图以及积之和的范式等经典方法，但这些方法都存在一个缺 点，即对于每个具有n 个变量的函数来说，都有2 4 个或是更多的表达式。 这些方法有如下的缺点： ( 1 ) 某些常用函数仍然都是以指数规模来表示的。如奇偶校验函数就 是最坏的例子。 ( 2 ) 对于某些函数，在一般情况下的表示式可能是可接受的形式，但 对它进行一个简单的运算，如求反运算，就可能产生一个指数规 模的表示式。 第1 页 华南师范大学硕士学位论文 ( 3 ) 这些表示式都不是范式形式，即：对于一个给定的函数可以有许 多不同的表示形式。 由于这些原因，大多数处理布尔函数运算的程序都有不稳定的性质， 它们先以一个可接受的步距正常运行，后来会突然跑出所执行的程序之 外，要么不能在给定的时间获得所需要的运算结果。 b d d 在人们寻找大型数字系统的有效分析、测试和计算方法中，由 于其固有的优越性能而日益受到重视。就最近几年国外发表的文章来看， 为了解决数字系统设计、测试、仿真、容错和设计校验1 6 7 ，8 1 等问题中布 尔运算的算法的复杂度剧增问题，人们越来越重视b d d 方法。综合来说， b d d 具有如下的优点( 9 】： ( 1 ) 直观，明了，便于逻辑电路的分析。 ( 2 ) 能反映数字电路的逻辑描述的细节，这点对电路的分析和测试非 常重要。 ( 3 ) 便于计算机的存储，编写的程序比布尔代数方法编写的程序更 短。 ( 4 ) 便于使用人工智能的方法，启发式进行求解空间搜索。 ( 5 ) 不管是硬件还是软件实现，都能获得比布尔代数算法更高的执行 速度。 ( 6 ) 可应用并行图论算法，迸一步提高运算速度。 b d d 由于可以应用于不同的场合( 数字系统) ，所以它有广阔的前景。 b d d 的一个重要应用是数字系统的故障检测与诊断。不管是组合逻辑系 统，还是时序系统，虽然至今都有一些成熟的理论和实用方法来测试， 但是他们的计算工作量和测试的开销都是很大的。尤其是现在系统的规 模越来越大，测试的矛盾也日益尖锐。 而b d d 作为一种简洁的布尔函数表示形式，运用到系统的故障检测 中，可以得到较小的规模和运行时间。 1 2 国内外研究状况 第2 页 华南师范大学硕士学位论文 从1 9 7 8 年，s b a k e r s 明确的提出了b d d 1 0 的概念之后，关于b d d 的研究就越来越受到人们的重视。之后，l e e 又引入了o b d d 的概念 ( o r d e r e db i n a r yd e c i s i o nd i a g r a m ) 。 到1 9 8 6 年，b r y a n t 提出了具有重要意义的r o b d d 1 l 的描述( r e d u c e d o b d d ) ，r o b d d 的特点就是结合了传统的技术( 如限定因子、香农展开、 函数相关满足集合等概念) 来研究b d d 中同构图和冗余节点的消去。但 是r o b d d 不是万能的，它的重要的缺点在于对于一些函数的表示仍然 存在指数复杂度的问题。 1 9 9 0 年，b r a c e 、r u d e l l 和b r y a n t 等基于有效的i t e l l l 】概念，提出 了独立于变量编序的b d d 操作，它的主要算法是有多根节点函数同时表 示和递归的i t e 操作。同样是在1 9 9 0 年，m i n a t o 提出了共享b d d ( s b d d ) i ”】的理论，其主要目标是压缩b d d 的空间，s b d d 的特点是利 用特定属性边标记并联结与其相关的几个操作，为节省存储空间对各同 类子图只保留一个，并存入其它子图与保留子图的差异。1 9 9 2 年，j a i n 等人在r o b d d 的基础上引入了多个变量的索引，提出了i b d d ( i n d e x e d b d d ) ! ”】，从而扩展了r o b d d 的表示范围。i b d d 的特点是节点的分层， 每一层节点以r o b d d 的形式表示，不同的层可有不同变量编序方法。 i b d d 的表达式是多项式的复杂度。1 9 9 3 年，l a i 等人则提出了一种层次 结构描述的边值e v b d d ( e d g e v a l u eb d d ) t 4 1 ，e v b d d 可在高级的功能 级上来描述变量的编序，并为层次化的功能验证、测试提供有效的工具。 1 9 9 8 年，g u n t h e r 和d r e c h s l e r 又提出了线性变换 1 4 , i s l 的算法，它不是变 换整个b d d ，而只是把输入变量进行线性变换。对于许多系统，都能大 大减少它们的图的规模和运行时间。但是对于有些系统来说，由于不能 找到一个合理的变换，有时甚至会增加它们的b d d 的节点数和运行时 间。上述的研究都在不同程度上起到简化节点和运行时间的作用，但是 随着系统规模的不断增大，b d d 表示与操作的复杂性仍较大。 研究发现，b d d 规模的大小决定着b d d 运算的复杂度，而b d d 规 模的大小主要取决于b d d 中变量的编序，所以以往的研究主要集中在如 第3 页 华南师范大学硕士学位论文 何找出某个逻辑函数的最佳变量序，关于这方面的文章很多。对于小型 系统来说，寻找最佳编序有一定的实际意义，但随着系统规模的增大， 其复杂性较大。目前，人们也在积极的寻找其他的解决办法。这其中最 有发展前途的方法就是l t _ b d d ( 线性变换b d d ) ，相比传统的做法，它 只是把原始输入变量进行线性变换，而不是变化整个函数的大小f 约为 2 n 1 。为了存贮这个线性变换1 1 6 , 1 7 1 ，需要一个n x 一非奇异布尔矩阵。通过 这个方法，可以有效的减小函数的空间复杂度和时间复杂度。它在电路 测试中的应用很好的说明了它的有效性。但是对于有些系统，变换后的 规模并不能取得显著效果，甚至图的规模更大。关键还是没有找到一个 合理的变换，因此现在研究的热点集中在怎样才可以找到一个使图的规 模显著减小的有效变换。 1 3 本文的研究内容 本文主要研究b d d 的编序算法，数字系统b d d 的建立以及应用 b d d 算法进行的两种应用研究。 本文一是研究b d d 实现的i t e 算法的步骤以及c + + 语言编程实现。 能完成对任意c d l 语言描述的组合逻辑电路或布尔函数实现其b d d 表 示，并通过对b d d 的操作，实现对相应组合电路或布尔函数的操作：二 是研究变量编序对b d d 规模( 节点数和路径深度) 的影响；三是研究基于 b d d 的网络可靠度的计算方法和组合电路的故障检测方法。而本文的重 点在二、三两个方面。 第一章：主要介绍本文的研究内容、目的和意义、国内外研究现状。 第二章：详细阐述了b d d 的基本概念，讨论影响b d d 的大小和深 度的主要因素一一变量编序，在此基础上提出了一种简单、易行的编序 算法，能够用较短的运算时间得到较小的b d d 。 第三章；主要说明了使用a p p l y 与r e d u c e 算法，和i t e 算法建立逻 辑函数的b d d 方法，比较了两者的优劣。最后研究了i t e 算法的c + + 语言实现，并给出了程序。 第4 页 华南师范大学硕士学位论文 第四章：研究b d d 在数字电路的固定型故障检测中的应用。相比传 统算法，应用b d d ，可以避免庞大的反向回溯，因而可以比较方便的得 出电路的故障点的测试矢量集。 第五章：研究了网络可靠度的b d d 计算方法，在已有算法的基础上， 本算法可以使得到的b d d 规模大大减少，并可计算在不同时间、不同故 障率下的可靠度。 第六章也是本文最后一章，对文中的工作和不足之处进行总结，并 对今后的研究方向进行了展望。 第5 页 华南师范大学硕士学位论文 第二章b d d 的原理与发展 本章详细论述了b d d 、o b d d 、r o b d d 的相关定义，并把以后的 大多数研究定位在r o b d d 的基础之上。讨论了对b d d 的规模大小有重 要影响的b d d 的变量编序问题，并提出了一种容易实施的、不涉及高深 概念、只与数字电路的知识相关的算法，可以使得到的b d d 的规模较小。 2 1b d d 的基本知识 b d d 是计算机科学和数字系统设计的基础，对不同形式的布尔函 数，只要它们的真值表相同，那么实际上它们是完全相同的两个布尔函 数。结合图论的知识，可以为它们建立一种图的表示形式，因为这种图 中的变量取值只有0 和1 两种。所以也把这种图称为二元判决图。b d d 能直观的表示布尔函数，并且能反映数字电路逻辑描述的细节，所以在 关于布尔函数的研究中，越来越受到人们的重视。 用图论的方法进行布尔函数处理的关键是在计算机中建立b d d 和 约简b d d 。应该注意的是，以b d d 为基础进行大型数字系统的设计、 分析和运算的图论算法研究中将不可避免地要应用到人工智能的方法。 在实际应用中，由于存储器和处理时间的限制，面对规模日益增大的集 成电路，要求b d d 尽可能地小。 定义2 1 【1 l 二元判决图( b d d ) 是一个具有有限个节点的有向无环图 ( d a g ) ，g = ，其中v 是g 中所有节点的集合，e 是g 中所有边的 集合。 更进一步说，b d d 的节点包括终节点和非终节点，终节点没有输出 边，且只可用“0 ”或“1 ”两个值来表示；而每一个非终节点用一个原 始输入变量表示，都有“高( h i g h ) ”、“低( 1 0 w ) ”两条输出边，“高”边表 示当这个节点的变量取“1 ”时函数的分支，“低”边表示当这个节点的 变量取“0 ”时函数的分支，每一个b d d 都只有一个根节点。 在表示b d d 时，通常规定所有的非终节点都由一个含有变量的圆圈 第6 页 华南师范大学硕士学位论文 来表示，而所有的终节点都由含有0 或1 值的方框来表示a 所有的“低 ( 0 ) ”边都用虚直线来表示，所有的“高( 1 ) ”边都由实线来表示，若无特 殊标明，本文中b d d 的表示方法都遵循这个规定。 给定一个布尔函数，就可以给出这个布尔函数的b d d 表示。 例2 - 1 布尔函数f i l z 2 x 3 + x l i 2 x 3 + x i x 2 x 3 的b d d 如图2 1 所示a 例点1 、 终节点 图2 1 函数f 的b d d 得到的b d d 如图2 1 所示。它是对这个布尔函数反复运用香农定理 而得到的。众所周知，每一个布尔函数f ：b “一b 都可以表示成一个b d d 的形式。都可以用香农定理在每一个节点上展开成一个有向无环图1 1 1 ： f = t 帅+ x i f 啊 对一个f 1 个变量分别为x 1 ，x 2 ，工。的布尔函数，( z 1 ，x 2 ，x 。) ，若 把它的某个变量x i 用b ( b 0 ，1 ) 来代替，得到的结果称为，的约束，也 称为余因子，可表示为，i 。 对于一个给定的布尔函数f ：b “一b ，它的余因子定义为，l 。等于： ，l 。“，x z ，) 一，瓴，z ：，t 一。，b ，t 。，) 可以看出，f i x i - b 也是一个布尔函数。同理，布尔函数，中的变量x i 由函 数g 代替时，称为布尔函数，和g 的合并，记为州帕g ，也就是： ，f 坼吕( x x ，x 2 ，。，x , n ) = ，( 毡，x 2 ，x i - 1 ，g ( 墨，z 2 ，靠) x i + 1 ，z 。) 显然函数的合并仍然是布尔函数。 下边通过图2 1 来说明，如何得到一个逻辑函数的b d d 。例如，在 第7 页 华南师范大学硕士学位论_ 文 上面的图2 1 中，z 1 就是这个b d d 的根节点，而x 2 ，x 3 都是这个b d d 的非终节点。正如上文所说的，每一个非终节点都有两个输出边，对于 图2 1 中的例点1 ，它是x 。的虚线输出边，也就是l o w ( o ) 输出边，是当 函数f 中的变量x l 为0 时，所得到的函数： f ( x 1 ，x 2 ，x 3 ) i x a - 0 if ( o ，x 2 ，x 3 ) - 0 x 2 x 3 + 0 i 2 x 3 + 0 + x 2 x 3 i x 2 x 3 ，l = x z x 3 也就是说，在这个例点1 得到的函数 一吃恐；而例点2 表示在例点1 舞a f c - t ，当x 2 的取值为1 时，函数 的结果，也就是 l ( x 1 ，工2 ，x 3 ) i q 1 一l ( o ，1 ，工3 ) = 1 。而一屯 ，2 - x 3 其它依次类推。 要注意的是，函数f 一_ 1 i z x 3 + 墨毒2 x 3 + 而一2 b + x l x 2 x 3 的b d d 并不是 唯一的，在图2 1 中，先分解的是变量工。，然后是变量x ：，x ，。若是改 变变量序，那么得到的b d d 很可能与图2 1 的b d d 不相同。 定义2 2 1 1 一个根节点为v 的b d d 递归地定义了一个函数，v 。 ( 1 ) 若v 是终节点： a ) 若v 的值为1 ，则，v = 1 b 1 若v 的值为0 ，则l = o b ) 若v 为非终节点，且它的索引值( 变量x i 的下标i ) i n d e x = i ，则 定义为： f 。( x l ，x 2 ，x n ) = i 几 1 ，z 2 ，x 。) + x f ， 材( 呻( z l ，x 2 ，x 。) 。 对两个函数的b d d ，若这两个b d d 的结构和属性都完全相同时， 称这两个图是同构的。 定义2 3 t 1 1 两个b d d 图g 和g ，是同构的，当它们存在一个从节点 g 到g 一对应的函数盯，对于任意一个节点v ，如果o ( v ) = ，则节点 y 和v 都是终节点，且它们的值v a l u e ( v ) = v a l u e ( v 1 1 ；若对非终节点v 和v ， 贝0 有i n d e x ( v ) = i n d e x ( v ) ，a ( t o ，( v ) ) = 如w ( ) ，o ( i g h ( v ) ) = h i g h ( v ) 。 由于每个函数图只有一个根节点并且它的任意非终节点的孩子都是 第8 页 华南师范大学硕士学位论文 不同的，因此要求g 和g t 之间的同构映射盯严格遵循：图g 的根节点对 应图g 的根节点，图g 的根节点的“低”边对应图g 根节点的“低”边， 一直对应相等，直到终节点。所以，检查两个b d d 是否同构并不难。 定义2 4 【1 】若两个b d d ，g 和g 是同构的，那么它们对应节点的子 图也同构。 上面定义的b d d 的规模还可以在不改变其所表示的函数的前提下， 进行约简，消去冗余的节点、重复的节点以及同构子图。 o b d d 是在b d d 的基础上对函数的变量进行编序产生的b d d ，也 即是选定了变量的先后顺序的b d d ( o r d e r e db d d ) 。研究发现，变量编 序对b d d 的大小有着重要的影响。例如对布尔函数f = 。l 茗2 + 上3 石4 + x s x 6 ，若 选它的变量序分别为z l ，x 2 ，。3 ，鞠，工5 ，和x 1 , x 3 ，x 5 ，x 2 ，z 4 ，则产生的b d d 的 大小分别由图2 2 ( a ) 和( b ) 给出。 图2 2 函数f = x i x 2 + x z , x 4 + x s x 6 在不同变量序对应的b d d 在图2 2 ( a ) 中，b d d 的节点数为8 个，其中有6 个非终节点和2 个 终节点。而在图2 2 ( b ) 中，b d d 的节点数是1 6 个，其中有1 4 个非终节 点和2 个终节点。相比图2 2 ( a ) 来说，图2 2 ( b ) 的节点数增加了一倍，而 且路径深度也有所增加。 第9 页 华南师范大学硕士学位论文 由于在计算机运算中，b d d 中节点数和路径的深度分别对应着计算 机实现算法的空问复杂度和时间复杂度，因此在计算机实现中最感兴趣 的是定义2 1 中的集合v 和集合b 的性质。也就是如何减小b d d 中节 点数和路径深度的问题。现今国内的研究也大多集中在这方面。 定义2 5 【1 4 1 ：当沿着某个b d d 的根节点向下搜索时，若每个节点在 每条分支上出现的次数最多一次且变量出现的顺序相同，则把这个b d d 称作编序b d d ( o b d d o r d e r e db d d ) 。 定义2 6 【1 4 】当一个o b d d 中不包含同构子图且节点的两条分支不 指向同一个节点时，称这个o b d d 为约简的编序b d d ( r o b d d r e d u c e d a n do r d e r e db d d ) 。 一个o b d d 可以通过以下三条规则转化为r o b d d l l l ，设o b d d 为 g = ： ( a ) 合并终节点中相同的节点，使之最多只有两个终节点，且它们 的取值只可能为0 或1 。 ( b ) 对非终节点h 和v ，如果有以下3 式成立 ( 1 ) v a r o ) 一v a r ( v ) ( 2 ) 肠协) 一肠吣) ( 3 ) h i g h 0 ) 一h i g h ( 则删除其中一个节点，将删除节点的所有入边指向保留节点。 ( c ) 对非终节点v ，如果有l o w ( v ) = h i g h ( v ) ，则删除节点v ，并把它的 所有入边指向l o 川v ) 。 下面通过一个例子来说明如何约简一个o b d d 。由于上面的例2 - 1 是选取变量序为x i ，x 2 ，z 3 的b d d ，它满足o b d d 的定义，所以就在这个 基础上把它约简为r o b d d 。 按上面的步骤： ( 1 ) 合并相同的终节点。也就是合并0 、1 节点，得到的结果如图 2 3 所示。 第1 0 页 华南师范大学硕士学位论文 图2 3 去掉图2 1 中的重复终节点 ( 2 )去除o b d d 中的同构子图。对于图2 3 ，其中有三个以x 3 为 根节点的同构子图。把它们合并为一个，结果如图2 4 所示。 图2 4 去掉图2 3 中的同构子图 ( 3 ) 删除图中的无效节点。若一个节点的两个输出边都指向同一 个节点，则说明这个节点对于输出无效。图2 4 中的节点x ： 和x 3 都是无效节点，删除它们，得到的图2 5 便是一个 r o b d d 。 图2 5 去掉图2 4 中的无效节点 研究发现”，对一个函数来说，它的r o b d d 表示是正则的，也就是 说对同一变量序，它的r o b d d 表示是唯一的。而对于由b d d 表示的布 第1 1 页 华南师范大学硕士学位论文 尔函数来讲，还有以下结论： ( 1 ) 布尔函数是同构的，当且仅当这两个函数等价。 ( 2 ) 一个布尔函数是可满足的当且仅当它的o b d d 表示的一个终节 点为1 。 ( 3 ) 一个布尔函数是永真的当且仅当它的o b d d 表示只有一个为1 的终节点。 ( 4 ) 如果一个布尔函数不含变量x ，则它的o b d d 表示不含v a l u e ( u ) 一工 的节点“。 b d d 中的节点数和路径的深度分别对应着计算机实现算法的空间 复杂度和时间复杂度【“】，因此在计算机实现中最感兴趣的是b d d 中节 点的数目和有向边的深度。 2 2b d d 的变量编序 b d d 的应用首先要考虑的是b d d 的约简问题。同一个布尔函数在构 造其b d d 时，若布尔函数的输入变量在图中的位置不同，即编序不同， 所得到的b d d 也不同，则对应的分析、测试和计算的算法的效果也不同。 b d d 中的节点数和路径长度分别对应算法的空间复杂度，约简的目的就 是对b d d 中的节点编序，尽量减小b d d 中的节点数和缩短b d d 中的 路径长度，并保持测试所需的信息。 由于o b d d 对变量序很敏感，使得变量编序 1 8 , 1 9 1 成为一个很重要的 问题。关于变量编序的方法，就目前的研究进展来看，有动态变量编序 法 2 0 , 2 1 】、启发式编序法 1 2 , 2 2 , 2 3 1 、迭代改善算法【2 “。现有的启发式算法不 能得到很好启发信息，尤其是对于大型的组合电路来说，效率不高，因 此，必须探求一种新的高效率的方法来适应新的大型的、复杂的组合电 路。 一般地，对于一个布尔函数或数字系统来说，它们的b d d 编序是一 个n p l 2 5 】问题，因此，对实际的电路，更趋向于找到一个“合理”的变 量编序。在本文中，对单输出电路和多输出电路分别进行讨论。首先， 第1 2 页 华南师范大学硕士学位论文 对单输出电路，因为只有一个输出，那么考虑的重点就是如何使这个输 出函数的b d d 尽量小，提出下面的算法1 。 算法1 ( a ) 首先，对于原始输出函数，考察函数，中每个变量( 变量和它的补 变量分别记数) 的出现次数，以出现次数最少的那一个变量作为第 一个展开的变量；若函数，中，出现次数最少的变量不止一个，则 观察哪个变量所在项的项数长度最短，则先展开此变量。 ( b ) 对于函数的子函数，则考虑所有子函数中每个变量出现的次数总和， 出现次数最小则先分解，同样若出现几个变量的次数都是最小，则 选定项数最短的变量，对所有子函数都先分解此变量。若还是不能 决定，则使用动态编序的方法进行调整。 ( c ) 对于几个子函数，利用( b ) 决定了先分解的变量后，若其中有的子函 数不含有即将分解的变量，则先不分解，等待下一次分解。若函数 b d d 中出现相同的子函数，则先把它们合并起来，再计算变量出现 次数。 使用这种算法的原理是在构建函数的b d d 时，充分利用逻辑代数的 基本公式，其中最主要的是利用吸收率。下面，通过几个例子来观察此 方法的有效性。首先对于上面图2 2 的函数f = x l x 2 + 工3 工4 + z 5 x 6 ，利用上述 算法，首先计算函数中每个变量出现的次数均是2 ，且对于每个变量它 们的项数的长短都为2 ，所以任意选取变量。这里，选择变量x ，作为首 先分解的变量。结果如图2 6 所示。 在得到的子函数，l 和，2 中，变量x - 、x ：、x ，、j 。出现的次数均为2 ， 而变量x 4 出现的次数为1 ，则接下来先分解x 4 。按照上面的算法，因为 函数 中未含有待分解的变量x 。，则先不分解，等待下一次机会。 当把，2 分解后，得到两个分支分别为x 1 x ：+ x s x 。和终节点1 ，因为 x l x 2 + x s x 6 和函数，1 相同，则合并在一起。接下来，b d d 中只剩下子函数 ，1 ，继续上述的过程，就可得到函数的b d d 。 第1 3 页 华南师范大学硕士学位论文 6 = x s x 6 图2 6 使用算法1 得到的图2 2 的函数i = - - x l x 2 + x 3 x 4 + x s x 6 的b d d 再通过一个例子，这也是第五章中用到的一个函数来说明算法的过 程。对函数f 一d g + a c e g + 口蟛+ a c f + 够+ b c d g + b e g ，使用算法1 ，求得 的b d d 如图2 7 所示； 图2 7 算法1 建立的函数f 的b d d 此函数是在讨论网络可靠度时，提出的一个网络的抽象布尔函数表 示式。利用文献【7 】中建立b d d 的方法得到的b d d 的规模很大，其中节 点数是6 8 个，路径深度是8 ，而且得到的b d d 表示不是一个范式，而 用算法1 得到的b d d 的节点数是1 8 个，路径的深度为7 ，大大减少的 节点数目，同时路径的深度也有所减少。 第1 4 页 华南师范大学硕士学位论文 而对于多输出电路，就要考虑变量编序2 6 1 对于所有输出函数b d d 中节点的总和是不是较小。多输出函数的变量编序方法是在单输出函数 变量编序方法的基础上提出来的，是算法1 的推广，在这里假定多输出 的几个输出函数是都是函数f 的予函数，因此也同样可用单输出的算法 来处理。 下面通过一个例子来说明，在此处选择标准电路中的c 1 7 。 图2 8 电路c 1 7 在此，假定，1 ，正是函数f 的子函数。那么同样对于这两个函数中变 量计算每个变量的出现次数。因为a 、e 的出现次数都为1 ，所以先分解 它们，在此因为属于不同的函数，所以a 、e 的先后顺序对函数的b d d 没有影响。然后剩余部分按照算法1 进行。所得到的b d d 如图2 9 所示。 对算法1 ，通过如上例子，说明了此算法有一定的有效性，可以得 到一个比较小的b d d ，但是相信也有不少局限性，为了得到规模更小的 b d d ，在电路的逻辑综合和验证中，国外的提出了线性变换【1 6 , i 7 】的算法， 以后我们关于减小图的规模的研究方向也将朝着这个方向。 第1 5 页 华南师范大学硕士学位论文 第三章b d d 包的构造 本章详细地阐述了建立b d d 的两种算法：a p p l y 与r e d u c e 算法，和 i t e 算法。指出了使用i t e 算法较之a p p l y 与r e d u c e 算法的优点以及改 进i t e 算法的措施。并且给出了使用i t e 算法建立b d d 的流程及其c + + 语言实现。 3 1a p p l y 与r e d u c e 算法 如前所述，对于b d d 的各种操作是建立在函数的b d d 表示图的基 础之上的。因此，在这一章，主要讨论b d d 的构建方法。关于b d d 的 构建，b r y a n t 于1 9 8 6 年提出著名的口即砂( 运算) 和r e d u c e ( 约简) 【1 1 算法， 用于二元判决图的构造和处理。 b d d 中的非终节点有一低、一高两个输出边，因此利用算法对它的 节点进行建模时，采用如下形式： s f ，u c tn o d e i n ti n d e x ；变量的索引 抽f 诚变量标志 b o o a nm 4 础：变量标志 v a l u e ( o ，1 ，x ) ；表示函数值，是枚举类型( e u m ) 变量 n o d eh i g h ，l o w ； ；两个输出边 其中，i n d e x 表示节点中的变量的索引值，谢是个整数变量，用来表示 b d d 图中的唯一节点。这个整形标识符在b d d 图的顺序并不重要，只 要它的数目是在1 到节点的数目之间就可以了。m a r k 是个布尔值，用来 标记图中已被访问过的节点。 f g h 和l o w 分别表示节点的两个输出边。 a ) r e d u c e 算法 r e d u c e 算法【1 1 可以把一个函数的任意b d d 变换成一个约简的b d d ， 即r o b d d a 它是利用检验两个图是否同构来达到约简的目的。从终节 点开始直到根节点，用一个唯一的整型计数器来标记每一个唯一的予图 第1 6 页 华南师范大学硕士学位论文 的根节点。也就是说，对每一个节点v ，用一个标记i d ( v ) 来表示它，同 样的方法对节点u ，只有当函数，( v ) - ，( u ) 时，才有i d ( u ) = i d ( v ) 。使用这种 标记方法，才能使产生的b d d 对每一个唯一的标记对应一个节点。 用r e d u c e 方法进行b d d 的约简时，分为如下几个步骤： 约简算法将一个任意函数图转换为表示同一个函数的约简图。在从 终节点到根节点的处理过程中，对每个唯一的子图的根赋予一个唯一的 整数标志。即：对每个节点v 赋予标志i t ( v ) 。对于两个节点u 和v ，当 且仅当a - - a 时，i t ( u ) = i t ( v ) 。给出此标志后，r e d u c e 方法对每个标志都以 一个节点来构造图。 从终节点到根节点，用下面的方法来标志节点。首先，当且仅当两 个终节点具有相同的值时，此两个节点有相同的标志。现在假定索引比 f 大的所有终节点和所有非终节点都已经标记，在处理节点索引为f 的节 点时，当且仅当下列两个条件之一满足时，节点v 的谢( 等于己标记的 节点的标志a 第一，如果i t ( 1 0 w ( v ) ) 一i d ( h i g h ( v ) ) ，则节点v 冗余并且i t ( v ) 设 置为i t ( 1 0 w ( v ) ) ，即i t ( v ) 一i t q o w ( v ) ) 。第二，如果有某已标记的节点u 有 i n d e x ( u ) 一i ，i t ( 1 0 w ( v ) ) 一i t ( 1 0 w ( u ) ) 和i d ( h i g h ( v ) ) 一i t ( i g h ( u ) ) ，则以此两个节 点为根的约筒子图是同构的，并且记为i d ( v ) i t ( u ) 。 对一个b d d 进行约简的过程也就是删除它的冗余节点和同构子图 的过程，删除一个b d d 中的冗余节点和同构子图并不会改变其对应的函 数，但是可以减小函数图的大小。 b ) a p p l y 算法 a p p l y 算法提供了一个对布尔表达式或者一个电路网络产生b d d 的基本方法。对一个用b d d 表示的逻辑函数，1 和，2 ，一个二进制操作 符( o p ) 1 产生一个用来表示函数f l ( o e f ：的约简的b d d ，定义为： 【，1 ，2 ( _ ，工2 ，工。) = ( 工l ，工2 ，z 。) ，2 1 ，z 2 ，) 。 可以使用此方法表述所有的布尔运算。这种方法比使用“与”、“或” 1 0 p 表示任意一种布尔运算 第1 7 页 华南师范大学硕士学位论文 等符号要简略得多。此算法由函数的根节点向终节点由上而下进行，在 结果图上产生一个由两个图的节点合成的节点。算法的主要部分就是下 面由香农定理得到的递归运算公式： t o p ，厂2 一置( 五f 。c o p ，2 f x i - o ) + ( ，l f 。c o p ，2 f x i - ) 该公式要对两个根节点分别为v 。和v 2 的函数的图进行运算，需要考 虑下面几个问题【1 1 。 首先，对这两个节点都是终节点的情况，则得到的合并图也是由终 节点组成，且它的终节点的值为节点v 1 的值与v 2 的值的 运算结果。 其次，假定两个节点中至少有一个是非终节点，若两个节点的i n d e x 相同且等于i ，那么递归调用l o w ( v ，) 和l o w ( v ：) 得到合并图节点的低边， 而递归调用 l g h ( v i ) 和h i g h ( ”2 ) 得到合并图节点的“高”边。 最后，若节点v l 的索引值为i ，而节点v 2 的索引值大于f ，则以v ： 为根节点的b d d 所表示的函数，2 的值与端无关。 由此可生成一个索引为f 的节点，并递归地在l o w ( v 1 ) 和y 2 上应用此 算法得到合并图节点的“低”边，递归地在_ i l f 曲( v ，) 和v ：上应用此算法 得到合并图节点的高边。当节点v 。和v 2 的关系正好相反时，算法的使用 也正好相反。一般地，这种方法建立的b d d 并不是约简的b d d ，所以 还需调用r e d u c e 算法进行约简。 接下来说明a p p l y 算法使用的两个规则。一是a p p l y 算法对给出的每 对子图的计算不超过一次。此规则说明了怎样在数据结构中使用共享子 图以便使所用的算法有较好的效果。如果每次两个子图都有许多共享子 图，则入口表的命中率就很高了。从实验中发现，入口表的命中率在 4 0 - 5 0 之间。注意，当入口表的命中率为5 0 时，算法的速度就会大 大超过预期的两倍。 定义3 1 若对布尔值k 和函数，有， k = k ，则称k 为函数的决 定值。 规则二：对两个节点应用a p p l y 算法时，若其中一个节点为终节点， 且它是另一个节点的决定值，则递归运算终止，并返回该节点。 第1 8 页 华南师范大学硕士学位论文 需要说明的是在实际应用中，需把a p p l y 和r e d u c e 算法结合起来用。 因为a p p l y 运算后得到的b d d 并不是约简的，还需要再执行约简算法。 利用上述的方法建立组合电路的b d d 的过程可以分为以下几步： f 1 1 建立原始输入的b d d ； ( 2 ) 利用a p p l y 和r e d u c e ，建立电路内部信号线的b d d ；