利用OBDD编码的快速二值图算法(英文)

对利用有序二元判定图 OBDD 编码二值图像进行了研究,该方法可以节约大量的空间,并在此基础上,提出了各种二值图的算法,包括解码和集合运算(并、交、差、对称差、包含和互补)。实验结果表明这种基于OBDD 编码的方法比现有的二值图编码方法效率更高。

二值图像序列的符号OBDD表征模型的研究

利用有序二叉决策图OBDD对二值图像序列数据进行建模,根据图像序列的帧间相关性,图像序列的OBDD共享了大量结点,节省一定的存储空间,为图像序列的有关处理提供了一个新的数据表示方法。

工程图纸识别过程中特征点判定

特征点的判定对扫描输入的二值工程图纸图像进行图文分离及图形的识别过程中起着十分重要的作用。现有的判定条件对于比较复杂的二值工程田像往往不能满足要求。本文根据工程图纸的实际情况,对传统的特征点判定条件进行了补充和修正,提出了一组比较完善的二值图像特征点的判定条件。

基于OBDD的SMC中PRE■操作的改进算法

提出一种基于排序二值判定图(OBDD)的符号模型检测中PRE■操作的改进算法。该算法处理PRE■步骤3(嵌套布尔存在量化)的方法是一次遍历"删除"所有被量化变量的节点,产生表示布尔函数与嵌套存在量化结果等价的不确定排序二值判定图,把不确定排序二值判定图转换成OBDD。实验表明,该算法能有效缩短计算时间,减少中间节点所需空间。

用OBDD算法评估无线传感网的可靠度和结点重要性

基于有序二叉判定图(OBDD),提出用结点扩张(NE)算法来评估无线传感网的可靠度和结点重要性。NE算法执行结点扩张操作来处理不可靠结点,从两方面增强了计算效率:利用OBDD结构表示网络状态,减少了大量冗余的等价状态;利用Hash表存储同构子网的OBDD,减少了同构子网的重复计算。另外,该算法对结点重要性进行了评估,为脆弱结点的保护提供参考。实验结果表明NE算法的计算开销比传统的factoring算法低,能有效评估无线传感网的可靠度。

基于SBDD图的布尔匹配

在逻辑验证和综合中 ,布尔匹配利用有序二叉判定图 OBDD来检验两个给定的逻辑函数是否相等 .为了提高匹配算法的效率 ,文中用最小项数作为标签标定变量 (变量组 ) .对比两函数中变量 (变量组 )的“标签”,可以删除不可能的排序 ,从而加快匹配过程 .在提取变量标签时 ,提出简约二分决策图—— SBDD,并利用其节点少的特性进一步提高“标签”提取算法的效率 .实验结果表明本算法执行速度快 。

基于OBDD时序电路设计的验证

依据有序二叉判定图 (OBDD)和计算树逻辑 (或称分支时态逻辑 )CTL(ComputationalTreeLogic)的基本原理 ,分析了基于OBDD和CTL的验证数字电路设计的基本原理 ,并在此基础上 。

对称检测算法的研究

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

符号化模型检测CTL

提出了一个关于时态逻辑CTL*的符号化模型检测算法.该算法通过所谓的tableau构造方法来判定一个有限状态系统是否满足CTL*规范.根据该理论,作者已实现了一个基于OBDD技术的CTL*符号化模型检测工具MCTK,并完成了相当数量的实验.到目前为止,已知有名的符号化模型检测工具,如SMV和NuSMV等,都只能对CTL*的子集逻辑(如CTL,LTL)进行检测,而文中算法的结果是令人满意的,并且当规范不是特别复杂时,高效的CTL*符号化模型检测是可能的.

数字电路设计中的符号模型检验技术

符号模型检验把有序二叉判定图OBDD技术引入到模型检验中,有效地缓解了状态组合爆炸问题。文章主要介绍了CTL模型检验基本概念和原理,给出了符号模型检验算法,验证了模4计数器的某些特性。

基于符号化模型检测的对弈必胜策略验证

在对弈的研究中,验证对弈双方是否存在必胜策略的问题一直没能很好地解决,因为这涉及到超大规模的状态空间搜索。而随着符号化模型检测技术的发展,大规模系统的验证成为了可能。给出了使用符号化模型检测来验证对弈必胜策略的一般方法,并给出了一个井字棋必胜策略验证的实例。

CMOS集成电路中Glitch Power的分析方法研究

在集成电路中器件延迟数学模型的基础上,介绍了如何利用定时布尔函数和定时有序二值决策图对集成电路GlitchPower进行分析;借助CUDD软件包,构建了电路的Timed-OBDD表达形式,对一些典型的BenchMark进行了仿真。

基于广义可能性的模态μ演算符号模型检测

随着计算机功能的不断增强,软硬件系统也变得越来越复杂,使得人们对系统的需求更高。系统建模中可能存在的诸多不确定性信息也亟待被解决,为了充分解决系统信息来源的种种不确定性特征和各种不完备性,本文引入了广义可能性决策过程理论作为系统模型。在此基础上,给出了广义可能性模态μ演算的语法和语义;然后通过约简有序二叉决策图进行布尔存储来描述广义可能性不确定信息系统的特征属性;最后给出了广义可能性的模态μ演算符号化模型检测算法和时间复杂度。同时,通过广义可能性的模态μ演算符号化模型检测算法也有效缓解了状态爆炸问题,这对不确定性信息系统的模型检测提供了一种新的思路。