An algorithm for bi-decomposition of logic functions

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.

REFERENCES

• 1: R. L. Ashenhurst. "The decomposition of switching functions". Computation Lab, Harvard University, 1959, Vol. 29, pp. 74-116.
• 2: A. Curtis. New approach to the design of switching circuits. Van Nostrand, Princeton, NJ, 1962.
• 3: Valeria Bertacco , Maurizio Damiani, The disjunctive decomposition of logic functions, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.78-82, November 09-13, 1997, San Jose, California, United States
• 4: Shin-ichi Minato , Giovanni De Micheli, Finding all simple disjunctive decompositions using irredundant sum-of-products forms, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.111-117, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288586]
• 5: T. Sasao, M.Matsuura. "DECOMPOS: An Integrated System for Functional Decomposition". Proc. of IWLS 1998, pp. 471-477.
• 6: D. Bochmann , F. Dresig , B. Steinbach, A new decomposition method for multilevel circuit design, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 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.
• 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.
• 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 - 168
• 10: Congguang Yang , Maciej Ciesielski , Vigyan Singhal, BDS: a BDD-based logic optimization system, Proceedings of the 37th conference on Design automation, p.92-97, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337323]
• 11: C. Yang, M. Ciesielski. "BDD-Based Logic Optimization System". Tech. Report CSE-00-1, February 2000.
• 12: T. Sasao, J. Butler, "On bi-decomposition of logic functions", Proc. of IWLS 1997.
• 13: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 14: F. Somenzi. BDD package "CUDD v. 2.3.0." http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html
• 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.
• 16: Bernd Steinbach , Marek A. Perkowski , Christian Lang, Bi-Decompositions of Multi-Valued Functions for Circuit Design and Data Mining Applications, Proceedings of the Twenty Ninth IEEE International Symposium on Multiple-Valued Logic, p.50, May 20-22, 1999

INDEX TERMS

Primary Classification:
  B. Hardware

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Standardization, Theory