FINDING THE OPTIMAL VARIABLE ORDERING FOR BINARY DECISION DIAGRAMS

被引：111

作者：

FRIEDMAN, SJ

SUPOWIT, KJ

机构：

[1] Department of Computer Science, Princeton University, Princeton

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1990年 / 39卷 / 05期

关键词：

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

共 11 条

[1] FUNCTIONAL TEST GENERATION FOR DIGITAL CIRCUITS DESCRIBED USING BINARY DECISION DIAGRAMS. [J].

Abadir, Magdy S. ;

Reghbati, Hassan K. .

IEEE Transactions on Computers, 1986, C-35 (04) :375-379

[2]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[3]

AKERS SB, 1978, IEEE T COMPUT, V27, P509, DOI 10.1109/TC.1978.1675141

[4]

BRYANT RE, 1986, IEEE T COMPUT, V35, P677, DOI 10.1109/TC.1986.1676819

[5]

BRYANT RE, 1985 CHAP HILL C VER, P419

[6]

HELLER LG, 1984, 31ST INT SOL STAT CI, P16

[7]

LEE C, 1959, AT&T TECH J, P985

[8]

MORET BME, 1982, COMPUT SURV, V14, P593, DOI 10.1145/356893.356898

[9]

NAIR R, 1986, IBM RC11863 T J WATS

[10]

Supowit K. J., 1986, 23rd ACM/IEEE Design Automation Conference. Proceedings 1986 (Cat. No.86CH2288-9), P200, DOI 10.1145/318013.318045

← 1 2 →