Document Type

Conference Proceeding

Publication Date



Logic circuits, Computer algorithms, Boolean algebra


This paper presents a methodology for logic synthesis of Boolean functions in the form of regular structures that can be mapped into standard cells or programmable devices. Regularity offers an elegant solution to hard problems arising in layout and test generation, at no extra cost or at the cost of increasing the number of gates, which does not always translate into the increase of circuit area. Previous attempts to synthesize logic into regular structures using decision diagrams suffered from an increase in the number of logic levels due to multiple repetitions of control variables. This paper proposes new techniques, which lead to fewer variable repetitions and significantly improve the performance of synthesis algorithms. Experimental results show that the generated regular circuits are larger in the number of gates and comparable in delay to the circuits without regularity produced by SIS, yet they exhibit a number of important advantages, such as localization and predictability of interconnect, reduction in the gate output load, and improved testability.


Originally presented at the International Workshop on Logic Synthesis, held in Temecula, California in June, 2004, and subsequently included in its proceedings. See for further information.

Persistent Identifier