An Efficient Algorithm Finding Simple Disjoint Decompositions Using BDDs

Yusuke MATSUNAGA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.12   pp.2715-2724
Publication Date: 2002/12/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Logic Synthesis
Keyword: 
functional decomposition,  BDDs,  logic synthesis,  FPGA,  

Full Text: PDF(295.2KB)>>
Buy this Article




Summary: 
Functional decomposition is an essential technique of logic synthesis and is important especially for FPGA design. Bertacco and Damiani proposed an efficient algorithm finding simple disjoint decomposition using Binary Decision Diagrams (BDDs). However, their algorithm is not complete and does not find all the decompositions. This paper presents a complete theory of simple disjoint decomposition and describes an efficient algorithm using BDDs.