基于二分图完善匹配的布尔匹配算法

提出了一种改进的基于二分图完善匹配的布尔匹配算法。该算法通过把布尔变量之间的匹配问题转换为二分图的完善匹配问题,避免了原算法中因乘积项过多而导致计算时间过长的缺点。对MCNC标准测试电路的实验结果表明;与原算法相比,改进后的算法可以减少21％左右的计算时间。同时,文中提出了布尔变量强匹配的概念,它是对传统布尔匹配概念的引申。     

简化BDD的SBDD和变量重排序结合算法

二叉判定图是一种基于图表的用来表示布尔函数的数据结构。它泛广地应用于计算机半辅助设计和数字电路的形式化验证中。本文主要研究如何存储和如何简化BDD。提出了一种把SBDD和变量重排序结合在一起的新算法，用来简化BDD的大小。     

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

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

基于OBDD的有向图的存储与操作研究

本文讨论了一种基于OBDD的有向图的存储结构,给出了基于OBDD的有向图的操作方法及搜索算法.实验结果表明,该存储结构与传统的邻接表的存储结构相比,在处理大规模的有向图时,具有较高的存储效率.     

基于ROBDD的布尔函数同构判定算法研究

布尔函数是密码体制设计与分析中一个不可缺少的工具,在布尔函数的应用中,判定两个布尔函数的同构问题具有广泛的需求,但是,判定布尔函数同构是NP-难问题,并且采取穷举法也将随着变量的增多,因极高的时间复杂度而使其难以实现.该文基于图的思想,提出了一种基于ROBDD(简化有序二元决策图)的布尔函数同构判定算法,其算法的复杂度...     

一种基于OBDD图的事件复合匹配方法

基于内容的Pub／Sub系统的核心问题是基于内容的事件匹配．在现有的方法中,订阅者使用简单约束来匹配事件内容,难以支持事件复合匹配．针对此问题,提出新的匹配模型,扩展简单匹配方法为多语义匹配并引入时间约束变量,支持依据语义对事件采取不同的操作和离散事件的处理,增强了事件匹配表达能力．在此基础上,将OBDD图扩展为层次着色OBDD图,证明了图扩展的等价性,给出基于扩展ODBB图的复合匹配算法,分析并验证了该算法的有效性．     

一种基于动态故障树的SBDD方法

在分析基于Pandora的动态故障树时,SBDD方法未考虑各底事件间复杂的关系,造成生成的SBDD中存在无效分支,即计算的不交化割集中存在无效割集。针对该问题,提出了一种基于动态故障树的SBDD方法,可以动态删除无效节点,避免无效分支的产生。该方法主要包括两个方面:基于结构式排序方法的关系式排序方法和动态优化SBDD生成算法。关系式排序方法的基本思想是利用故障树的结构关系和底事件间的关系给底事件赋予不同的排序优先级。在底事件排序队列的基础上,使用动态优化SBDD生成算法来生成SBDD。在计算过程中,该算法动态删除无效的节点,使结果中不存在无效割集。实验结果表明,在相近的时间内,使用基于动态故障树的SBDD方法生成的SBDD规模更小,不交化割集数目更少且不存在无效割集。     

图的布尔矩阵化简

复杂图常常包含有成百个顶点、上千条边,结构庞杂,在分析处理中需进行简化。通常的作法是按顶点的空间分布对原始图进行分块,但分块的准则并非单一。这一特性虽然有助于化简时增加系统的先验条件,但却不利于编制规范的计算机软件来进行复杂图组合结构的变换。该文讨论复杂图组合结构的化简问题,提出通过布尔矩阵把复杂图变换为能够用维数较低的邻接矩阵进行分析与描述的化简算法,这种变换可大大减少图中顶点和边的数量。     

一个高效BDD的简洁实现

二叉判定图BDD作为一种表示和操作布尔函数的数据结构,被广泛地应用在模型检测、系统验证等领域.在最坏情况下,BDD的空间规模是指数级的,因此为了设计和实现一个高效BDD包,研究者们做了大量技术性工作,同时涌现出多个高效BDD包.为了节省空间和提高运算速度,这些BDD包的实现都限定了一个较小的变量个数上限(不超过2~(16)),然而这种限定同时也限制了BDD包的适用性.为了突破这种限制,文中给出了一个高效的BDD包实现,该包在采纳了经典BDD包高效实现技术的同时,使用了内存分片分配、轻量级垃圾回收等技术.这些技术使得BDD包在保持高性能的情况下,将可处理的变量规模提高到2~(32),与现有BDD包的处理规模2~(16)相比,大大提高了BDD包的适用性.实验证明其性能非常接近可获得的最快的2~(16)变量规模的BDD包——CUDD.     

基于重量分析的OBDD变量排序算法

有序的二叉判决图（ＯＢＤＤ）是布尔表达式的一种有效表示方法，但它的体积对变量排序具有较强的依赖性。本文提出一种电路结构图，并在此基础上定义了原始输入重量和节点重量等参数，并建立了用重量分析来指导的ＯＢＤＤ变量排序算法。由于从考虑变量对输出函数的影响出发与从考虑ＯＢＤＤ节点共享性出发对变量排序的要求不同，本文分别设计了两类算法。实验结果表明，本文对大多数标准电路变量排序的效果都优于国际上的同类算法，     

基于布尔矩阵的Deep Web复杂模式匹配

在正负关联规则中引入布尔矩阵的概念,在双重相关性挖掘算法的基础上提出一种Deep Web复杂模式匹配算法。将查询接口模式中的属性项转化成布尔矩阵,通过对矩阵进行正关联规则运算挖掘组属性,对矩阵进行负关联规则运算挖掘同义属性。实验结果表明该算法的执行效率较高。     

Computation of signal output probability for Boolean functions represented by OBDD

In [l] and [2], two algorithms have been proposed to calculate the output probability of Boolean functions represented by OBDDs, assuming that the input variables are equiprobable and each variable is statistically independent from others. In this paper, we point out that under these assumptions, the output probability calculation is equivalent to counting the number of minterms of the corresponding Boolean functions. An algorithm is proposed to compute the output probability using simple integer arithmetic as opposed to floating point arithmetic involved in [1,2]. To compute output probability of Boolean functions represented by shared OBDI)s and OBDDs with edge negation, we further propose a generalized algorithm.     

基于布尔置换的ElGamal体制

在现有的公钥密码系统中,大部分算法有信息膨胀的缺点。文章根据布尔置换的特点对ElGamal体制进行了改进,使信息的膨胀率降低,并且新体制可以避免一些原有的攻击。     

Arithmetic Boolean Expression Manipulator Using BDDs

Recently, there has been a lot of works on LSI design systems using Binary Decision Diagrams (BDDs), which are efficient representations of Boolean functions. We previously developed a Boolean expression manipulator, that can quickly calculate Boolean expressions by using BDD techniques. It has greatly assisted us in developing VLSI design systems and solving combinatorial problems.In this paper, we present an Arithmetic Boolean Expression Manipulator (BEM-II), that is also based on BDD techniques. BEM-II calculates Boolean expressions that contain arithmetic operations, such as addition, subtraction, multiplication and comparison, and then displays the results in various formats. It can solve problems represented by a set of equalities and inequalities, which are dealt with in 0-1 linear programming. We discuss the algorithm and data structure used for manipulating arithmetic Boolean expressions and show the formats used for displaying the results.The specifications for BEM-II are described and several application examples are presented. Arithmetic Boolean expressions will be useful for various applications. They perform well in terms of the total time for programming and execution. We expect BEM-II to facilitate research and development of digital systems.     

从布尔代数到布尔微积分

布尔函数作为最简单的有限值函数具有特殊的重要性．它在包括信息、控制等许多领域有着广泛的应用．本文综合介绍有关布尔函数的理论基础．包括从布尔代数到布尔微积分的主要理论结果,它们在信息与控制中的一些重要应用,以及其前沿动态与新进展．介绍的一个重点是矩阵半张量积在这些领域的应用．     

布尔表达式匹配问题研究

提出了布尔表达式匹配问题,并给出了它的形式化定义;提出了一个解决布尔表达式匹配问题的通用算法框架,并在此框架上给出了一种算法及其改进;通过理论分析和实验数据给出了影响布尔表达式匹配算法性能的因素和它们之间的关系.     

基于布尔可满足性的电路设计错误诊断算法

提出了一种组合电路设计错误诊断算法,该算法结合传统基于模拟的方法和可满足性问题求解技术,在不依赖于故障模型的条件下实现对电路逻辑错误的诊断定位．提出了基于布尔可满足性的增量式电路诊断方法,通过对可满足解依据电路结构信息筛选分级,提高了多错误诊断定位的分辨率和准确性;并提出多项启发式方法,避免了大量不必要的操作,使算法在时间和内存上保持有效性．实验结果表明,利用形式验证的技术来导向模拟的过程,抓住了高复杂度的多错误定位问题的特征,提高了电路错误诊断的效率．