Record Details

A heuristic for decomposition in multilevel logic optimization

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A heuristic for decomposition in multilevel logic optimization
 
Creator SINGH, VINAYA KUMAR
DIWAN, AJIT A
 
Subject computational complexity
polynomials
formal logic
optimization
 
Description In this paper, we propose a new heuristic to find common subexpressions of given Boolean functions based on Shannon-type factoring. This heuristic limits the search space of finding common subexpressions considerably by applying a top-down approach. In this top-down approach, synthesis of a Boolean network flows from the primary outputs to the primary inputs. The common subexpressions and their complements in N variables are extracted before common subexpressions and their complements in (N - 1) variables. This decomposition of the network depends upon a permutation of Boolean variables and has a polynomial complexity for restricted extraction of complements. A multilevel logic optimization system, MULTI, has been implemented using this heuristic. Good results on several benchmark circuits show its effectiveness.
 
Publisher IEEE
 
Date 2009-05-14T13:53:13Z
2011-12-08T07:18:35Z
2011-12-26T13:02:05Z
2011-12-27T05:48:02Z
2009-05-14T13:53:13Z
2011-12-08T07:18:35Z
2011-12-26T13:02:05Z
2011-12-27T05:48:02Z
1993
 
Type Article
 
Identifier IEEE Transactions on Very Large Scale Integration (VLSI) Systems 1(4), 441-445
1063-8210
10.1109/92.250191
http://hdl.handle.net/10054/1365
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1365
 
Language en