基于灾变遗传算法的二叉判定图最小化算法

二叉判定图广泛应用于形式验证,但相关算法存在节点规模过大的问题。提出了一种基于灾变遗传算法的二叉判定图最小化算法,它能在不扩大种群规模的情况下增加个体多样性,改善遗传算法局部收敛的问题。试验结果表明该算法的全局特性显著优于传统遗传算法,能够进一步减小节点规模,改善程度最高可达25%。而且,由于使用何种进化策略并不影响灾变的发生,因此,算法可扩展性好,极易与其他改进策略结合起来,在原有特性的基础上引入全局优势,以进一步减小节点规模。

基于动态筛选算法的二元判定图的优化

作为逻辑布尔函数的一种高效简洁的描述方法,BDD规模结构对应着计算机实现算法的空间和时间复杂性。随着应用领域的不同,BDD的节点和路径的规模成为关注的两个焦点。文章讨论利用基于动态规划的筛选算法来实现从节点规模和路径的大小两方面对BDD的优化。在将筛选算法用于节点优化的基础上,从理论上提出了优化路径的思路及可行算法。

一种基于二叉判定图的包过滤规则设计方法

提出了一种采用二叉判定图来表示规则集的新的算法,通过仿真实验证明:对于较大规模的规则集,基于BDD的包过滤规则设计方法简洁可行,且在存储空间和查询性能上要优于传统的线性顺序方法。

数字电路测试生成的二元判定图方法

测试是保证电路系统可靠性的重要手段,已成为集成电路设计与生产的一个组成部分,研究了基于二元判定图的数字电路测试生成方法,对布尔函数的表示和操作的二元判定图进行研究,详细讨论了其中的ite算符;给出了基于二元判定图的电路测试生成方法的实现步骤,并用实例进行了说明。

尔函数操作的二元判定图方法研究

布尔函数在计算机科学和数字电路与系统的设计中有着广泛的应用,本文研究对布 尔函数进行表示和操作的二元判定图方法,对其中的ite算符的实现做了详细讨论,基于该算 符能容易地完成二元判定图的计算机程序实现。

基于混沌差分进化方法的二元判定图极小化

逻辑布尔函数在数字电路的设计与测试、计算机科学、人工智能等领域有广泛的应用.二元判定图是逻辑布尔函数的一种有效表示方法,它的节点数与变量的编序有关.提出了一种基于混沌差分进化的二元判定图极小化方法,在该方法中,使用混沌映射来产生初始种群,并在差分进化算法所获得的一些近似解的附近寻找较优的解;同时设计了一种双种群进化方案,来计算二元判定图的变量编序.对数字电路的测试矢量生成的结果说明,该方法能够得到较优的变量编序,因此,可以获得规模较小的二元判定图.

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

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

二叉判定图最优化算法研究综述

对近年来二叉判定图 (BDD)最优化算法的成果和发展趋势进行了综述和讨论 ,重点介绍精确排序算法和动态启发式排序算法 .给出了BDD优化算法的改进建议 :用不完全枚举法的优势和随机过程动态规划策略改进BDD优化算法 .

二元判定图在逻辑模拟中的应用

逻辑模拟可分为两部分:排队和求值。后者在逻辑模拟过程中要进行成千上万次。为减少模拟时间,我们采用二元判定图描述各种集成电路的逻辑功能。由于原始二元判定图有一定的局限性,为此对它作了扩充。在此基础上建立了一个集成电路元件库,开发了相应的逻辑模拟器。该元件库内包括了Texas TTL和National CMOS手册中常用的元件。本文将讨论对二元判定图的扩充,并给出逻辑模拟器的梗概。

一种新型二元判定图器件和电路

提出了一种基于二元判定图 (BDD)原理的新型逻辑器件和电路 .BDD器件以电流模式的开关电流存储器为基本单元 ,具有符合二元判定图的两向通路的特点 .用这种器件按照BDD树形图可以构成任意形式的组合逻辑电路 .给出了或门、异或门及四位加法器电路的例子 ,并使用HSPICE仿真器进行了仿真 。

基于遗传禁忌混合策略的二叉判定图最小化算法研究

提出了一种新的动态启发式二叉判定图(BDD)最小化算法.该算法将遗传算法的全局搜索能力和禁忌搜索的邻域搜索策略相结合来寻找BDD的最优变量排序,以实现BDD结点规模最小化.实验结果表明该算法性能优于其它启发式算法.*

确定三相变压器联结组标号的判定图

介绍了一种判定绕组联结组别的方法———判定图法的原理，通过实例对该判字方法的使用进行了说明。

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

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

实时二叉判定图

对布尔函数的有效操作是许多计算机辅助设计的重要组成部分，二叉判定图（ＢＤＤ）是对布尔函数的一种有效表示，为了表示带时间参数的布尔函数，在ＢＤＤ的基础上，本文给出了带时间参数的布尔函数（ＴＢＦ）的表示—带时间参数的二叉判定图（ＴＢＤＤ），并利用ＣＵＤＤ包实现了ＴＢＤＤ．

确定三相变压器联接组标号的判定图

介绍了已知绕组联接图确定其组别标号；已知组别标号确定其绕组联接图的判定图。此判定图通俗易懂，简化了以往利用相量分析的复杂过程，在现场应用非常方便。

利用Westgard标准决定图判定测定方法性能

目的利用Westgard标准决定图定量分析实验方法的不精密度和不准确度,确定实验方法的可接受性。方法定量测定各实验方法的不精密度和不准确度,利用Westgard标准决定图判断各项目的方法性能的可接受性。结果23个常规生化项目中,仅有谷氨酰转肽酶(γGT)和丙氨酸氨基转移酶(ALT)需要进行方法的改进和性能的重新评估;标准决定图可简单、准确、直观地判断方法性能,从而为质量改进提供依据。

一种基于邻接矩阵的二部图判定算法

在二部图定义的基础上,给出一种基于邻接矩阵的新判定算法,通过在每对结点间逐步插入中间结点进行路径长度检测,并进行了实验测试。结果表明,新算法能较好解决二部图的判定问题。

有向H-图的新判定准则

应用布尔代数上的行列式det2(A),引入det2(A)的特征行列式,讨论了det2(A)的特征行列式的性质与有向图的圈的关系,并用这些结论给出有向H-图的新特性和新判定准则.

无向H-图的新判定准则

讨论了无向图G的等价有向图D(G)的构成,并利用布尔行列式det2(A)和det2(A)的性质,以及有向H-图的布尔行列式的判定方法和判定准则,给出了无向H-图的新特性和新判定准则.

新的二部图判定算法

二部图是现代图论中一类非常重要的图,然而关于其判定的充要条件却很少,而且用算法实现它们很复杂,需要指数级的时间代价。利用图的广度优先遍历,提出了一个易于实现的二部图判定的充要条件:无向图G是二部图当且仅当G的广度优先生成森林中的同一层上的任意两点在G中不邻接。给出了该判定条件的实现算法,算法的时间复杂度是O(n2),很好地解决了二部图的判定问题。