This work was supported in part by the NSF grants MIP-9629419 and CCR-9988402.
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.
Chrzanowska-Jeske, Malgorzata, et al. "Logic synthesis for layout regularity using decision diagrams." International Workshop on Logic Synthesis. 2004.