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

被引：4

作者：

龙望宁，杨士元，闵应骅，童诗白

机构：

[1] 清华大学自动化系，中国科学院计算技术研究所ＣＡＤ开放实验室

来源：

计算机学报 | 1997年 / 08期

关键词：

二叉判决图，OBDD变量排序，逻辑设计验证;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：702 / 710

页数：9