Boolean resubstitution with permissible functions and binary decision diagrams

ABSTRACT

In this paper, we present a new Boolean resubstitution technique with permissible functions and ordered binary decision diagrams, abbreviated as OBDD[8]. Boolean resubstitution is one technique for multi-level logic optimization. Permissible functions are special don't care sets. We represent the data structure of permissible functions and logic functions at each node in Boolean networks in terms of OBDD. Therefore, logic functions can be flexibly manipulated and rapidly executed. We have previously reported a multi-level logic optimization technique called transduction methods[1] using OBDD in ICCAD'89[7]. We have improved the OBDD operation techniques, so that now OBDD operations can be executed faster than we reported before. We also applied Boolean resubstitution to our multi-level logic synthesis. We present results of experiments employing the improved OBDD operation techniques and applying Boolean resubstitution to our multi-level logic synthesis.

REFERENCES

• 1: S. Muroga , Y. Kambayashi , H. C. Lai , J. N. Culliney, The Transduction Method-Design of Logic Networks Based on Permissible Functions, IEEE Transactions on Computers, v.38 n.10, p.1404-1424, October 1989 [doi>10.1109/12.35836]
• 2: R.K.Brayton, R.Rudell, A.Sangiovanni-Vincentelli and A.R.Wang," MIS: Multi-level interactive logic optimization system," IEEE TC., Vol.CAD-6(6), November 1989, pp 1062-1081.
• 3: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 4: A. Saldanha , A. R. Wang , R. K. Brayton , A. L. Sangiovanni-Vincentelli, Multi-level logic simplification using don't cares and filters, Proceedings of the 26th ACM/IEEE conference on Design automation, p.277-282, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74429]
• 5: D.Bostick, G.D.Hachtel, R.Jacoby, M.R.Lightner, P.Moceyunas, C.R.Morrison, D.Ravenscroft," THE BOULDER OPTIMAL LOGIC DESIGN SYSTEM," IEEE ICCAD, 1987, pp62-65.
• 6: G.Hachtel, R.Jacoby, P.Moceyunas and C.Morrison," Performance Enhancements in BOLD using "implications"," IEEE ICCAD, November 1988, pp94-97.
• 7: Y.Matsunaga and M. Fujita," Multi-level logic optimization using binary decision dJLagrams," IEEE ICCAD, November 1989.
• 8: 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]
• 0: Robert K. B ray ton , " Multi- level Logic Synthesis," ICCAD-89 Tutorial, November 1989.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.2 Reliability and Testing**
          Subjects: Testability**
      B.6.m Miscellaneous

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Design, Performance, Reliability