二叉决策图在逻辑综合中的应用

二叉决策图(BDDs)是布尔函数的一个表示方法,最近它被广泛应用于逻辑综合、布尔电路的模拟和测试等领域.在这些应用中,有些基本问题需要解决,其中包括电路图到决策图的转换.本文提出一个转换的方法.文中分两步叙述,首先是对无扇出电路的转换,然后是对有扇出电路的转换,最后把两者结合为一个通用算法.     

基于二叉决策图的网络可达性计算

针对现有攻击图生成方法中普遍通过网络扫描获得网络可达性信息存在信息不完整、耗时长、产生网络干扰等不足,提出一种基于二叉决策图的网络可达性计算方法。该方法利用二叉决策图建模防火墙规则,通过高效的集合运算计算网络可达性。真实环境检测和模拟实验均表明该方法具有精确、耗时短、无网络干扰等优点,适用于大规模网络可达性的计算,推动了攻击图在大规模网络中的应用。     

产生式知识的有序二叉决策图表示及其推理

为了更完整地表示产生式规则构成的知识库及更有效地进行知识推理,给出了基于有序二叉决策图OBDD(Ordered Binary Decision Diagram)的产生式知识表示模型.在此基础上实现了基于OBDD的知识推理规则及相关算法,并结合实例对OBDD模型及其推理规则的可行性进行了分析.     

基于有序二叉决策图的装配序列符号表示方法

通过建立装配状态的二进制编码和装配操作的布尔特征函数,给出了装配序列描述的有序二叉决策图(OBDD)方法;建立了从装配序列的与或图模型到OBDD模型的转换规则;并对装配序列表示的与或图模型和OBDD模型进行了存储效率比较.实验结果表明:OBDD方法具有较好的存储性能,可以改善复杂装配体的装配序列表示的存储效率,适合于复杂装配体的可行装配序列的描述.     

网络可靠性分析中自顶向下的二叉决策图构造研究

采用边界分区标识网络的思想,实现基于边界分区的自顶向下K端可靠度二叉决策图(BDD)构建算法。针对BDD构建过程中存在的节点冗余问题,提出无效边冗余消除和K点非连通冗余消除2种处理技术。在规则网络和实际工程中的实验结果表明,利用无效边冗余消除和K点非连通消除技术后的BDD改进算法,在不影响算法时间性能的情况下,可大幅缩减BDD尺度,提升K端网络可靠度分析算法性能,适用于大规模的网络可靠度分析。     

基于符号零压缩二叉决策图的组合测试用例生成方法

组合测试是系统测试中一种非常有效的方法,能够在保证错误检出率的前提下采用较少的测试用例来测试系统。但是,组合测试用例集构造问题的复杂度是NP完全的。给出了一种基于符号零压缩二叉决策图(Zero-suppressed Binary Decision Diagram,ZBDD)的组合测试用例生成方法。该方法首先利用ZBDD的结构特性,对测试系统进行紧凑的符号表示。然后利用ZBDD的隐式操作,结合贪心算法的思想,不断地覆盖更多的组合并缩小未覆盖组合集合,生成2～4维覆盖强度的较小测试用例集。实验证明,所提方法不仅可行而且节点开销小。     

基于符号零压缩二叉决策图的装配可行性判定方法

为了扩大装配序列规划的求解规模并提高求解效率,提升装配自动化水平,给出了装配体联接矩阵和干涉矩阵的零压缩二叉决策图描述,建立了基于符号零压缩二叉决策图的装配操作可行性判定方法。基于该方法,可以高效地求解出一个装配体的可行装配操作。结合实例验证了基于符号零压缩二叉决策图的装配体模型和可行装配操作判定方法的正确性和可行性。     

柔性制造系统中生产调度问题的零压缩二叉决策图算法

针对赋时有界Petri网模型下柔性制造系统的生产调度问题,给出了有界Petri网的零压缩二叉决策图表示方法,进而建立了此类生产调度问题求解的符号零压缩二叉决策图算法.该算法在求解过程中对状态空间及其搜索过程中的相关数据,采用零压缩二叉决策图表示,避免了状态和搜索的显式枚举,实现了隐式高效操作,有效地改善了算法的计算性能.实验结果表明了算法的有效性.     

利用二叉判定图对集成块进行功能性故障模拟

本文给出一种用二叉判定图对集成块进行功能性故障模拟的方法及算法,该算法的复杂性为O(N),其中N为集成块的输入端数.     

数据的逻辑综合分析及决策算法

文章给出了逻辑综合分析的基本理论和决策算法。并利用逻辑综合中逻辑单元的随机覆盖问题产生的随机数据,对算法加以验证。实验结果表明决策算法的精确度可以达到97.2%。     

Factored Edge-Valued Binary Decision Diagrams

Factored Edge-Valued Binary Decision Diagrams form an extension to Edge-Valued Binary Decision Diagrams. By associating both an additive and a multiplicative weight with the edges, FEVBDDs can be used to represent a wider range of functions concisely. As a result, the computational complexity for certain operations can be significantly reduced compared to EVBDDs. Additionally, the introduction of multiplicative edge weights allows us to directly represent the so-called complement edges which are used in OBDDs, thus providing a one to one mapping of all OBDDs to FEVBDDs. Applications such as integer linear programming and logic verification that have been proposed for EVBDDs also benefit from the extension. We also present a complete matrix package based on FEVBDDs and apply the package to the problem of solving the Chapman-Kolmogorov equations.     

布尔函数表示的二元判定图方法的研究与实现

布尔函数是数字系统与计算机科学等领域的基础，有广泛的应用。本文对布尔函数的二元判定图表示方法进行了详细讨论，说明了基于布尔函数的真值表和香农展开式来构造二元判定图的方法、二元判定图的简化、以及它在数字电路设计与测试中的应用。     

基于BDD算法的系统安全性分析

随着现代武器系统越来越趋于大型化和复杂化,采用事故树方法进行系统安全性分析的难点问题也日益突出,本文研究了基于BDD的FTA优化求解算法,并采用此方法对某系统进行了相关安全性分析。     

Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation

In this paper, we discuss the use of binary decision diagrams to represent general matrices. We demonstrate that binary decision diagrams are an efficient representation for every special-case matrix in common use, notably sparse matrices. In particular, we demonstrate that for any matrix, the BDD representation can be no larger than the corresponding sparse-matrix representation. Further, the BDD representation is often smaller than any other conventional special-case representation: for the n×n Walsh matrix, for example, the BDD representation is of size O(log n). No other special-case representation in common use represents this matrix in space less than O(n²). We describe termwise, row, column, block, and diagonal selection over these matrices, standard an Strassen matrix multiplication, and LU factorization. We demonstrate that the complexity of each of these operations over the BDD representation is no greater than that over any standard representation. Further, we demonstrate that complete pivoting is no more difficult over these matrices than partial pivoting. Finally, we consider an example, the Walsh Spectrum of a Boolean function.     

基于BDD算法的某系统事故发生概率分析

随着现代武器系统趋于大型化和复杂化,利用事故树进行系统安全性分析日益困难。本文重点研究了基于BDD的FTA优化求解算法,并利用贝叶斯方法研究小样本的独特优势,提出蒙特卡洛仿真方法求解底事件发生概率,进而利用BDD求解系统顶事件发生概率的方法。     

广义自缩序列的FBDD攻击

流密码是加密体制中的一种重要体制,一直是军事、政府等敏感部门加密的主要手段,近年来在新一代移动通信中占有主流地位。其安全性主要依赖于密钥流序列的安全。基于LFSR的构造是密钥流构造中最为常见的一种。针对基于单个LFSR的广义自缩序列,提出了一种FBDD攻击。该攻击基于BDD攻击,充分利用了BDDs对布尔函数操作上的优良特性。算法分析表明,其时间复杂度是理想的,但是其所需的内存空间较大,有待于进一步的改进。     

符号化模型检测CTL

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

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

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

Gate-delay-fault testability properties of multiplexor-based networks

We investigate the gate-delay-fault testability properties of multilevel, multiplexor-based logic circuits. Based on this investigation, we describe a procedure for synthesizing gate-delay-fault testable multilevel circuits. The procedure involves the construction of a multilevel circuit from a general, unordered Binary Decision Diagram (BDD) by replacing vertices of the BDD with multiplexors. The procedure relies on the following result derived in this article: If the multilevel circuit constructed from the BDD is initially fully single stuck-at fault testable, or made fully single stuck-at fault testable by redundancy removal, then it is completely robustly gate-delay-fault testable. Once the initial gate-delay-fault testable circuit has been obtained, constrained algebraic factorization is used to improve the area and performance characteristics without compromising testability. Unlike previous techniques for synthesizing robustly gate-delay-fault testable circuits, this procedure can be used to synthesize fully testable circuits directly from nonflattenable, logic-level implementations.