Symmetry detection and Boolean matching utilizing a signature-based canonical form of Boolean functions

被引：19

作者：

Abdollahi, Afshin ^{[1
]}

Pedram, Massoud ^{[2
]}

机构：

[1] Univ Calif Riverside, Dept Elect Engn, Riverside, CA 92521 USA

[2] Univ So Calif, Dept Elect Engn, Los Angeles, CA 90089 USA

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 2008年 / 27卷 / 06期

关键词：

Boolean matching; canonical form; functional symmetry; signatures; technology mapping;

D O I：

10.1109/TCAD.2008.923256

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A compact canonical form and a computational procedure for solving the Boolean matching problem under permutation and complementation of variables are presented. The proposed approach, which utilizes generalized signatures and variable symmetries, can handle combinational functions with no limitation on the number of input variables. Experimental results; demonstrate the generality and effectiveness of the proposed canonical form and the associated Boolean matching algorithm.

引用

页码：1128 / 1137

页数：10

共 23 条

[1]

Abdollahi A, 2005, DES AUT CON, P379

[2]

Benini L., 1997, ACM Transactions on Design Automation of Electronic Systems, V2, P193, DOI 10.1145/264995.264996

[3]

Chai D, 2006, DES AUT TEST EUROPE, P1078

[4]

Chan DJ, 2004, J INFRARED MILLIM W, V23, P1

[5] Post-placement rewiring and rebuffering by exhaustive search for functional symmetries [J].

Chang, KH ;

Markov, IL ;

Bertacco, V .

ICCAD-2005: INTERNATIONAL CONFERENCE ON COMPUTER AIDED DESIGN, DIGEST OF TECHNICAL PAPERS, 2005, :56-63

[6] Local transformation techniques for multi-level logic circuits utilizing circuit symmetries for power reduction [J].

Chung, KS ;

Liu, CL .

1998 INTERNATIONAL SYMPOSIUM ON LOW POWER ELECTRONICS AND DESIGN - PROCEEDINGS, 1998, :215-220

[7] Efficient canonical form for Boolean matching of complex functions in large libraries [J].

Ciric, J ;

Sechen, C .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2003, 22 (05) :535-544

[8]

CLARKE EM, 1993, ACM IEEE D, P54

[9]

Darga PT, 2004, DES AUT CON, P530

[10] Fast Boolean matching under permutation using representative [J].

Debnath, D ;

Sasao, T .

PROCEEDINGS OF ASP-DAC '99: ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE 1999, 1999, :359-362

← 1 2 3 →