Division-Based Versus General Decomposition- Based Multiple-Level Logic Synthesis

During the last decade, many different approaches have been proposed to solve the multiple-level synthesis problem withdifferent minimum functionally complete systems of primitive logic blocks. The most popular of them is the division-basedapproach. However, modem microelectronic technology provides a large variety of building blocks which considerablydiffer from those typically considered. The traditional methods are therefore not suitable for synthesis with many modembuilding blocks. Furthermore, they often fail to find global optima for complex designs and leave unconsidered someimportant design aspects. Some of their weaknesses can be eliminated without leaving the paradigm they are based on, otherones are more fundamental. A paradigm which enables efficient exploitation of the opportunities created by themicroelectronic technology is the general decomposition paradigm. The aim of this paper is to analyze and compare thegeneral decomposition approach and the division-based approach. The most important advantages of the generaldecomposition approach are its generality (any network of any building blocks can be considered) and totality (all importantdesign aspects can be considered) as well as handling the incompletely specified functions in a natural way. In many cases,the general decomposition approach gives much better results than the traditional approaches