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

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

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

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

同一变量排序下的多OBDD合并算法

有序决策图（OBDD）是一种用于表示布尔表达式的数据结构,并在许多领域得到了广泛应用。在分布式或者动态环境下,利用已知布尔表达式的OBDD构造目标布尔表达式的OBDD是一个决定实际问题解决效率的关键问题。基于Shannon分解原理提出了一个同一变量排序下的OBDD合并算法。该算法首先建立目标布尔表达式的表存储模型,然后按照变量排序的逆序,依次处理各个变量,并且合并取值相同的行,直到所有变量处理完毕。     

一种基于熵的OBDD变量排序算法

有序二叉决策图（OBDD）是一种有效表示布尔函数的数据结构,其大小依赖于所采用的变量序。熵是定量描述布尔函数中变量重要性的一种方法。基于变量的熵值分析了高质量变量序的特征,给出了一种基于熵的OBDD变量排序算法。实验结果表明：该算法与模拟退火算法和遗传算法结果相当。时间仅为相应算法的80．84％和29．79％。     

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

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

基于OBDD的描述逻辑εL循环术语集推理

循环术语集推理是描述逻辑研究中面临的难点问题,尚未得到很好的解决.有序二叉决策图（ordered binary decision diagram,简称OBDD）是一种对布尔函数进行紧凑表示和高效操作的数据结构,适用于表示和处理大规模问题.将OBDD应用于描述逻辑循环术语集的推理.首先,针对描述逻辑εL中的循环术语集,给出了描述图上关于最大模拟关系的重要性质,并借助集合表示和集合运算对该性质进行了表述和证明.在此基础上,应用布尔函数对描述图进行编码,给出了基于OBDD求解最大模拟关系的方法,进而给出了最大不动点语义下基于OBDD对概念包含关系进行判定的算法;接下来,基于OBDD给出了求解描述图中可以到达循环路径的所有结点的方法,进而给出了最小不动点语义下基于OBDD对概念包含关系进行判定的算法;最后,对算法的正确性、复杂度等进行了分析和证明,并对算法进行了编程实现,给出了关于计算性能的实验结果.该工作为循环术语集的推理提供了一条有效途径,也为OBDD在逻辑推理中的应用提供了新的案例.     

基于OBDD的灰度图像无损压缩算法

提出一种基于有序决策二叉图(OBDD)的灰度图像无损压缩算法,该算法将灰度图像划分成独立的位平面,利用二值图像的开关性,用OBDD模型来表征位平面,然后对OBDD进行有效的编码,最后用算术编码压缩进一步减少冗余.实验结果表明,本算法的压缩比优于WinZIP.     

基于SBDD图的布尔匹配

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

基于二元决策图的节点不可靠网络可靠度计算

针对节点不可靠网络可靠度计算效率较低的问题,提出一种基于二元决策图的网络可靠度计算方法.通过因子分解得到节点可靠网络的有序二元决策图(OBDD),根据节点和边的关系对边的变量节点执行边替换操作,生成节点不可靠网络的OBDD,并利用其高效存储结构提高不可靠节点的处理效率.在遍历OBDD计算可靠度时,引入Hash表以避免对同一节点的重复访问,从而减少冗余计算,进一步提高计算效率.在基准网络中的对比实验结果表明,该方法不仅能正确计算网络可靠度,而且能快速分析大型网络.     

二进神经网络中汉明球突的判定及其逻辑意义

在布尔空间中,汉明球突表达了一类结构清晰的布尔函数, 由于其特殊的几何特性,存在线性可分与线性不可分两种空间结构. 剖析汉明球突的逻辑意义对二进神经网络的规则提取十分重要, 然而,从线性可分的汉明球突中提取具有清晰逻辑意义的规则, 以及如何判定非线性可分的汉明球突,并得到其逻辑意义,仍然是二进神经网络研究中尚未很好解决的问题. 为此,本文首先根据汉明球突在汉明图上的几何特性, 采用真节点加权高度排序的方法, 提出对于任意布尔函数是否为汉明球突的判定算法;然后, 在此基础上利用已知结构的逻辑意义, 将汉明球突分解为若干个已知结构的并集,从而得到汉明球突的逻辑意义; 最后,通过实例说明判定任意布尔函数是否为汉明球突的过程, 并相应得到汉明球突的逻辑表达.