共 11 条
[11]
Yoffa E. J., 1985, 22nd ACM/IEEE Design Automation Conference Proceedings 1985 (Cat. No.85CH2142-8), P32, DOI 10.1145/317825.317830
FINDING THE OPTIMAL VARIABLE ORDERING FOR BINARY DECISION DIAGRAMS
被引：111
作者：
FRIEDMAN, SJ
SUPOWIT, KJ
机构：
[1] Department of Computer Science, Princeton University, Princeton
关键词：
Binary decision diagrams;
Boolean functions;
differential cascode voltage switch trees;
logic design verification;
D O I：
10.1109/12.53586
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The ordered binary decision diagram is a canonical representation for Boolean functions, presented by Bryant as a comput representation for a broad class of interesting functions derived for circuits. However, the size of the diagram is very sensitive to the choice of ordering on the variables; hence, for some applications, such as differential cascode voltage switch (DCVS) trees, it becomes extremely important to find the ordering leading to the most compact representation. We present an algorithm for this problem with time complexity O(n23n), an improvement over the previous best, which required 0(n!2n). © 1990 IEEE
引用
收藏
页码：710 / 713
页数：4
相关论文