Alan Mishchenko
ABSTRACT
We propose a new BDD-based method for decomposition of multi-output incompletely specified logic functions into netlists of two-input logic gates. The algorithm uses the internal don't-cares during the decomposition to produce compact well-balanced netlists with short delay. The resulting netlists are provably non-redundant and facilitate test pattern generation. Experimental results over MCNC benchmarks show that our approach outperforms SIS and other BDD-based decomposition methods in terms of area and delay of the resulting circuits with comparable CPU time.
- 1.R. L. Ashenhurst. "The decomposition of switching functions". Computation Lab, Harvard University, 1959, Vol. 29, pp. 74-116.Google Scholar
- 2.A. Curtis. New approach to the design of switching circuits. Van Nostrand, Princeton, NJ, 1962.Google Scholar
- 3.V. Bertacco, M. Damiani. "The Disjunctive Decomposition of Logic Functions". Proc. of ICCAD 1997, pp. 78-82. Google ScholarDigital Library
- 4.S. Minato, G. De Micheli. "Finding All Simple Disjunctive Decompositions Using Irredundant Sum-of-Products Forms". Proc. of ICCAD 1998, pp. 111-117. Google ScholarDigital Library
- 5.T. Sasao, M.Matsuura. "DECOMPOS: An Integrated System for Functional Decomposition". Proc. of IWLS 1998, pp. 471-477.Google Scholar
- 6.D.Bochmann, F.Dresig, B.Steinbach, "A new decomposition method for multilevel circuit design". Proc. of Euro-DAC 1991, pp. 374 - 377. Google ScholarDigital Library
- 7.B. Steinbach, F. Schumann, M. Stockert. "Functional Decomposition of Speed Optimized Circuits". In Power and Timing Modelling, D. Auvergne, R. Hartenstein, eds., Springer-Verlag, 1993, pp. 65-77.Google Scholar
- 8.B. Steinbach, M. Stockert. "Design of Fully Testable Circuits by Functional Decomposition and Implicit Test Pattern Generation". Proc. of VLSI Test 1994, pp. 22-27.Google Scholar
- 9.B. Steinbach, A. Wereszczynski, "Synthesis of Multi-Level Circuits Using EXOR-Gates". Proc. of "IFIP WG 10.5 - Workshop on Applications of the Reed-Muller Expansion in Circuit Design", Japan, 1995, pp. 161 - 168Google Scholar
- 10.C. Yang, M. Ciesielski, V. Singhal. "BDS: A BDD-based Logic Optimization System". Proc. of DAC 2000, pp. 92-97. Google ScholarDigital Library
- 11.C. Yang, M. Ciesielski. "BDD-Based Logic Optimization System". Tech. Report CSE-00-1, February 2000.Google Scholar
- 12.T. Sasao, J. Butler, "On bi-decomposition of logic functions", Proc. of IWLS 1997.Google ScholarCross Ref
- 13.R. E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Trans. on Comp., Vol. C-35, No. 8 (August, 1986), pp. 677-691. Google ScholarDigital Library
- 14.F. Somenzi. BDD package "CUDD v. 2.3.0." http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.htmlGoogle Scholar
- 15.E. Sentovich, et al. "SIS: A System for Sequential Circuit Synthesis", Tech. Rep. UCB/ERI, M92/41, ERL, Dept. of EECS, Univ. of California, Berkeley, 1992.Google Scholar
- 16.B. Steinbach, M. A. Perkowski, Ch. Lang. "Bi- Decomposition of Multi-Valued Functions for Circuit Design and Data Mining Applications." Proc. of ISMVL 1999, pp. 50 - 58. http://www.informatik.tu-freiberg.de/ prof2/publikationen/ismvl99_final.ps. Google ScholarDigital Library
Index Terms
- An algorithm for bi-decomposition of logic functions
Recommendations
Decomposition of logic functions for minimum transition activity
EDTC '95: Proceedings of the 1995 European conference on Design and TestIn this age of portable electronic systems, the problem of logic synthesis for low power has acquired great importance. The most popular approach has been to target the widely-accepted two-phase paradigm of technology-independent optimization and ...
Multi-Input Variable-Threshold Circuits for Multi-Valued Logic Functions
ISMVL '00: Proceedings of the 30th IEEE International Symposium on Multiple-Valued LogicIn this paper, two-types of Multi-Input Variable-Threshold (M-I V-T) circuits and their applications to Multi-Valued Logic (MVL) are proposed. M-I V-T circuits are extensions of binary CMOS NAND and NOR gates to multi-valued logic. First, definitions of ...
Multiple-Valued Decomposition of Generalized Boolean Functions and the Complexity of Programmable Logic Arrays
Generalized Boolean functions are shown to be useful for the design of programmable logic arrays (PLA's), and the complexity of three types of PLA's is obtained by the theory of multiple- valued decomposition. A two-level PLA consists of an AND array ...
Comments