An efficient structural technique for Boolean decomposition

Andres Martinelli; Elena Dubrova

doi:10.1117/12.608720

30 June 2005 An efficient structural technique for Boolean decomposition

Andres Martinelli, Elena Dubrova

Proceedings Volume 5837, VLSI Circuits and Systems II; (2005) https://doi.org/10.1117/12.608720
Event: Microtechnologies for the New Millennium 2005, 2005, Sevilla, Spain

Abstract

Boolean decomposition techniques offer a powerful alternative to traditional algebraic methods when partitioning a circuit graph in the technology independent stage of the circuit design flow. These techniques usually require to transform the circuit from a structural representation to a representation based on Binary Decision Diagrams (BDDs). It is well known that BDDs can grow exponentially in some cases, so the power of Boolean decomposition comes at the expense of an exponential increase in the size of the circuit representation. The following stages in the design flow may suffer severely from the space penalty imposed on each partitioned block. To cope with this space explosion, each block of the partitioned circuit has to be re-synthesized before further processing. The extra re-synthesis, on the other hand, may impose a prohibitive time/space penalty on the design flow. This paper proposes an inexpensive technique to avoid re-synthesizing the BDD blocks obtained after Boolean decomposition. This technique works by structurally partitioning the original circuit representation, according to information provided by the partitioned BDD blocks. After all the blocks have been recovered, the BDDs are not needed and can be discarded. The resulting circuit will be proportional to the original circuit representation, and not to the intermediate BDD representation.

Citation Download Citation

Andres Martinelli and Elena Dubrova "An efficient structural technique for Boolean decomposition", Proc. SPIE 5837, VLSI Circuits and Systems II, (30 June 2005); https://doi.org/10.1117/12.608720

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
6 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Binary data

Logic

Computer programming

Composites

Hybrid circuits

Tolerancing

Transistors

Show All Keywords

Keywords/Phrases

Search In:

Publication Years