对称检测算法的研究

对称是逻辑综合，逻辑优化以及映像技术领域中一个非常重要的性质，对于对称函数，可以使用特殊的逻辑综合程序来改进设计结果，使用对称也可以提高映像技术和等价检测的有效性，提出一种用于OBDD布尔函数对称性检测的精确有效的算法。     

基于OBDD的航空电子网络可靠性分析

针对航空电子网络通信任务的实时性需求,建立具有时延约束的面向任务的网络可靠性模型,并从共因失效(common cause failure, CCF)的角度分析了部件故障相关性,提出一种基于有序二叉决策图(ordered binary decision diagram, OBDD)的航空电子网络可靠性评价方法--时延约束边扩张算法。算法结合时延约束,利用边扩张构建网络OBDD,递归遍历OBDD结构计算部件故障统计独立条件下航空电子网络可靠度,并在此基础上引入CCF分析,利用同一OBDD结构综合评价航空电子网络可靠性。通过实例阐述了算法的原理,实验表明算法能有效评价航空电子网络的可靠性。     

一种新的布尔函数对称检测算法

对称是逻辑综合、逻辑优化以及映象技术领域中的一个十分重要的性质－ 对于对称函数, 可以使用特殊的逻辑综合程序来改进设计结果－ 使用对称也可以提高映象技术和等价检测的有效性－ 本文提出一种用于ＯＢＤＤ 布尔函数对称检测的高效算法     

基于自动机理论的符号模型检验

状态爆炸是模型检验需解决的一个关键问题.基于GPVW算法,以及从LTL公式导出识别该公式的Büchi自动机,用OBDD符号表示,通过符号操作求解自动机乘积.采用符号方法求解出含有初始状态或接受状态的最大连通图,判断自动机是否存在初始状态能否到达含有接收状态的最大连通分支,从而判定所接受的语言是否非空来模型检验LTL公式.采用本文所提出模型检验LTL公式的方法,能在一定程度上解决空间爆炸问题.     

Properties of Paths in ROBDD and Its Application to Signal Probability Calculations

Introduction Powerconsumptionhasbecomeagreatconcerninchip design.Inordertocomputepowerdissipation,wehaveto firstlycalculatenodeswitchingactivityEn(sw).FromEq.1 En(sw)canbeestimatedthroughprob(n)[2]andtherefore thepowerdissipationcanbeobtainedthroughEq.2[3]. En(sw)=2prob(n)(1-prob(n))(1) Pavg=0.5V2ddfclkCloadE(SW)(2) Thereareseveralmethodsincalculatingprob(n) includingtheapplicationofMarkovchain,theentropyapproach,andothers[1].Yettwoimportantproblemsarise whenapplyingthesea…     

基于OBDD的通信网链路重要性评估

通信网的链路重要性评估是网络设计和维护的重要依据。在链路重要性评估方法上提出了一种基于有序二叉决策图(ordered binary decision diagram, OBDD)的新方法--BO(Birnbaum OBDD, BO)方法。该方法引入了Birnbaum测度来量化链路重要性,并采用边扩张图(edge expansion diagram,EED)来创建网络的OBDD结构,在可靠度计算基础之上,通过分析链路故障时网络可靠度得到Birnbaum测度值。BO方法将高效的OBDD结构与hash表结合起来,并通过识别计算中出现的同构子网,减少冗余状态与重复计算来提高整体计算效率。引入并对比经典可靠性文献中一些规模较大网络,通过实验验证了BO方法不仅能正确地评估网络链路重要性,而且在计算效率方面优于因子分解方法。     

Efficient Heuristic Variable Ordering of OBDDs

Introduction　　Orderedbinarydecisiondiagrams(OBDDs)[1]areefficientrepresentationsofBooleanfunctions.However,thesizeofOBDDsdependsheavilyonvariableordering[1].HowtofindasatisfyingvariableorderisthuscrucialtotheapplicationofOBDDs[211].HeuristicanddynamicmethodsarewidelyusedinorderingthevariablesforOBDDs.Heuristicmethodsusetheinformationimpliedinthecircuitstructure,whiledynamicmethodsimprovethevariableordergraduallyongivenOBDDs.Althoughadynamicmethodmaygivebetterresults,itsruntimedepen…     

加速布尔匹配算法的研究

逻辑验证和综合中，布尔匹配利用有序二叉判定图（Ordered Binary Decision Diagram,OBDD)检验两个给定的逻辑函数是否相等。直接枚举每个函数中输入变量的各种排列顺序，并根据这些顺序进行匹配，算法时间复杂度为O(n!2^n2),n为变量数。为了提高匹配算法的效率，文中用最小项数目作为标签标定变量（变量组）。对比两函数 中变量（变量组）的标签，可删除不可能的排序，加快匹配过程。在此基础之上，利用重构将待匹配变量压缩在OBDD图的底部。利用这部分结构可以进一步区分变量。实验结果表明，该算法不仅变量区分能力要好于其他算法，且执行速度快，更具实用价值。