Reduced offsets for two-level multi-valued logic minimization

ABSTRACT

The approaches to two-level logic minimization can be classified into two groups: those that use tautology for expansion of cubes and those that use the offset. Tautology based schemes are generally slower and often give somewhat inferior results, because of a limited global picture of the way in which the cube can be expanded. If the offset is used, usually the expansion can be done quickly and in a more global way because it is easier to see effective directions of expansion. The problem with this approach is that there are many functions that have a reasonable size onset and don't care set but the offset is unreasonably large. It was recently shown that for the minimization of such Boolean functions, a new approach using reduced offsets, provides the same global picture and can be computed much faster. In this paper we extend reduced offsets to logic functions with multi-valued inputs.

REFERENCES

• 1: 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
• 2: Douglas W. Brown, A State-Machine Synthesizer—SMS, Proceedings of the 18th conference on Design automation, p.301-305, June 29-July 01, 1981, Nashville, Tennessee, United States
• 3: G. DeMicheli, R. K. Brayton, and A. L. Sangiovanni- Vincentelli. Optimal State Assignment of Finite State Machines. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, CAD- 4(3):269-284, July 1985.
• 4: S. J. Hong, R. G. Cain, and D. L. Ostapko. MINI: A Heuristic Approach for Logic Minimization. IBM Journal of Research and Development, 18:443--458, September 1974.
• 5: B. Lin and A. Newton. Restructuring State Machines and State Assignment: Relationship to Minimizing Logic Across Latch Boundaries. In Proceedings of 2nd MCNC1nternational Workshop on Logic Synthesis, Research Triangle Park, North Carolina, May 1989.
• 6: A. A. Malik, R. Bmyton, A. R. Newton, and A. Sangiovanni-Vincentelli. A Modified Approach to Two-Level Minimization. In Proceedings of International Conference on Computer-Aided Design, pages 106-109, Santa Clara, November 1988.
• 7: S. Malik, R. Brayton, and A. Sangiovanni-Vincentelli. Encoding Symbolic Inputs for Multi-Level Logic Implementation. In Proceedings of 2nd MCNC International Workshop on Logic Synthesi ,J, Research Triangle Park, North Carolina, May 1989.
• 8: R. L. Rudell. Multiple-Valued Logic Minimization for PLA Synthesis. Technical Report M86165, Electronics Research Laboratory, College of Engineering, University of California at Berkeley, Berkeley, CA 94720, 1986.
• 9: Tsutomu Sasao, An application of multiple-valued logic to a design of programmable logic arrays, Proceedings of the eighth international symposium on Multiple-valued logic, p.65-72, January 1978, Rosemont, Illinois, United States

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

General Terms:
Algorithms, Experimentation