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

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

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

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

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

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

模糊计算树逻辑的符号模型检测

对含有模糊不确定性信息的系统进行模型检测时,状态空间爆炸问题成为了亟待解决的主要问题.将形式化的系统模型用拟布尔公式表示,用多终端二叉决策图来对拟布尔公式进行存储.对模糊计算树逻辑的不动点语义给出了解释和证明,然后给出模糊计算树逻辑的符号化模型检测算法,最后通过一个实例验证算法的正确性.该算法可有效缓解对模糊模型检测验证时的状态空间爆炸问题,并扩展了模型检测的应用范围.     

异步时序电路的功能测试自动生成方法

异步时序电路的测试一直是一个比较困难的问题。该文通过在前人研究的基础上，提出了一种实用、高效的自动测试生成方法。该方法通过使用基于OBDD(有序二元判决图)的布尔特征函数的运算求解来确定电路的状态转换图，然后通过对转换图的强连通图的搜索运算简化状态转换图，最后使用图论的方法求出测试序列。     

结合因式分解与布尔表达式图的可逆电路综合方法

为降低由布尔表达式图(BED)综合所得可逆电路的成本,提出一种将因式分解与BED表示模型相结合的可逆电路综合方法.给定布尔函数的积之异或和(ESOP)覆盖,首先由ESOP立方体的共享零抑制多输出决策图表示借助代数除法对立方体实施因式分解,并在此基础上构建BED;然后将BED结点映射为可逆门级联.对基准函数的可逆电路综合结果表明,该方法具有较高的时间效率.与现有将有向无环图作为函数表示模型的综合方法相比,该方法在许多情况下能降低综合所得可逆电路的量子成本和量子位数.从平均角度看,与结合变量分组和BED表示模型的综合方法相比,该方法可将量子成本和量子位数分别降低5.01％和5.47％.     

基于BDD的组合电路等价性检验

本文分析了基于BDD的组合电路等价性检验；讨论了构造输出函数的二叉判定图BDD的不同方法，并分析了BDD间布尔操作的不同的算法的异同；然后给出了一种基于BDD的组合电路等价性检验方法。     

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

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

用VIS验证微处理器PIC

近年来,二叉判定图ＢＤＤ和符号模型检验在形式验证数字电路设计中取得了突破性进展,文中介绍了符号模型检验的基本原理和方法,重点介绍了如何用ＶＩＳ系统验证微处理器ＰＩＣ设计的正确性。利用ＶＩＳ证明了ＰＩＣ设计部分电路的等价性。发现了一个设计错误并证明了ＰＩＣ中一些重要模块的特性。     

结合无依赖性割集和量化的等价性验证

提出一新的验证算法,利用电路拓扑信息选择有效割集,以减小验证规模,并对割集进行无依赖性处理,减少伪错误发生概率,提高验证效率;同时,利用启发式信息选择复杂度较高的节点变量进行量化,进一步减小二叉决策图（BDD）的内存要求．最后用ISCAS’85电路的实验结果证明了该算法的有效性．