PALMINI—fast Boolean minimizer for personal computers

ABSTRACT

This paper describes a fast and efficient method for minimization of two level single output Boolean functions. The minimization problem is reduced to that of coloring of the graph of incompatibility of implicants. The program permits also to remove static hazards and allows inversion of output's polarity which proves to be very convenient when designing with PAL's. It gives solutions within a very reasonable amount of time. On small industrial examples its speed is slightly better than Espresso and it occupies 6 times less memory.

REFERENCES

• 1: Bartholomeus, M., Man, H.D., : '~Prestol-II: Yet Another Logic Minimizer for Programmed Logic Arrays", Proc. Int. Symp. Circ. Syst., June 1985, p. 58.
• 2: Bessllch, P.W., Pichlbauer, P. : '~Fast Transform Procedure for the Generation of Near-Minimal Covers of Boolean Functions", IEE Proc. Vol. 128, PTE, No.6, Nov. 1981, pp.250-254.
• 3: Nripendra N. Biswas, Computer aided minimization procedure for boolean functions, Proceedings of the 21st conference on Design automation, p.699-702, June 25-27, 1984, Albuquerque, New Mexico, United States
• 4: 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
• 5: Breithart, Y., Vairavan, tC : "The Computational Complexity of a Class of Minimization Algorithms for Switching Functions", IEEE TC, Vol. C-20, No. 12, December 1979, pp. 941-943.
• 6: Breuer, M.A. (ed) : "Design Automation of Digital Systems", Vol. 1, Prentice Hall, Englewood Cliffs, New Jersey, 1972.
• 7: 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
• 8: Oaruso, G. : "A Local Selection Algorithm for Switching Function Minimization", IEEI~ TC., Vol. C-33, Jan. 1984, pp. 91-96.
• 9: Dietmeyer, Logic design of digital systems, Allyn & Bacon, Inc., Needham Heights, MA, 1988
• 10: McCluskey, E. J. : '~Viinimization of Boolean Functions", Bell Syst. Tech. J., Vol.35, p.1417, April 1956.
• 11: Dagenals, M.R., Agarwal, V.K., Rum_in, N.C. : '~VIcBoole: A New Procedure for Exact Logic Minimization", IEEE Trans. on CAD, Jan. 1986, pp. 229 - 238.
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
• 13: Gimpel, J.F. "The Minimization of TANT Networks", IEEE TEC, Vol EC-I6, pp. 18-38, February 1967.
• 14: Hong~ S.J.~ Cain, R.G., Ostapko, D.L. : '~~IINI: A Heuristic Approach for Logic Minimization", IBM J. Res. and Dev., Vol.18, No.5, pp. 443-458, September 1974.
• 15: Johnson, D.S. : '~~orst-Case Behavior of Graph Coloring Algorithms". Proceedings of the Fifth Southeastern Conference on Gombinatorics, Graph Theory and Computing, pp. 513-528, Winnipeg, Canada, Utilitas Mathematica Publishing, 1974.
• 16: Kerntopf9 P., Michalskl, A. : "Selected Problems in Synthesis of Combinatorial Logic Circuits", PWN, Warsaw, 1972 in Polish).
• 17: Lee, E.B., Perkowskl, M. : "Concurrent Minimization and State Assignment of Finite State Machines". Proceedings of 1984 Intern. Cont. on Systems, Man and Cybernetics, IEEE, Halifax, Nova Scotia, Canada, October 9- 12, 1984.
• 18: MeDiarmi~ C.J.H. : 'Y)etermining the Chromatic Number of a Graph", SIAM J. Computing, Vol. 8, pp. 1 - 19, 1979.
• 19: C. McMullen , J. Shearer, Prime implicants, minimum covers, and the complexity of logic simplification, IEEE Transactions on Computers, v.35 n.8, p.761-762, Aug. 1986 [doi>10.1109/TC.1986.1676828]
• 20: Miller, R.E. : "Switching Theory", Vol. 1 and 2, John Wiley, New York, 1965.
• 21: Perkowskl, M. : "Synthesis of Multioutput Three Level NAND Networks", Proceedings of Seminar on Computer Aided Design, pp. 238 - 265, Budapest, November 3 - 5, 1976.
• 22: Perkowsk|, M., :"A General Method to Solve Combinatorial Problems in the Automatic Design of Digital Systems", Publishers of Warsaw Technical University, Warsaw, Poland, September 1980 (in Polish), 434 pages.
• 23: Perkowski~ M. : "Systolic Architecture for the Logic Desigr, Machine", Proc. Intern. Conf. on Computer Aided Design, pp. 133- 135, Santa Clara, November 1985.
• 24: Perkowski, M.A., Nguyen, L.B.~ Goldstein, N.B. :"An Approach to Minimization, Decomposition and Partitioning of PLA and PAL Gircuits Based on Multi-Valued Algebra and Graph Coloring", Technical Report, Dept EE, PSU 1987.
• 25: Patrick, S.R. : "On the Minimization of Boolean Functions", Proceedings of Syrup. on Switching Theory, ICIP, Paris, France, June 1959.
• 26: Rudell, R., Sangiovanni-Vineentelli, A., 'T~spresso-mv" Algorithms for Multiple-Valued Logic Minimization", Proc. 1985 Custom Integrated Circuits Conference, pp. 230- 234, Portland, OR, May 1985.
• 27: Rudell, R. : '~Viultiple-Valued Logic Minimization for PLA Synthesis", Research report, June 5, 1986, Univ. of California, Berkeley.
• 28: Rudell, R., Sanglovanni-Vincentelll, A., '~Exact Minimization of Multiple-Valued Functions for PLA Optimization", Proc. ICOAD-86, pp.352 - 355, Santa Clara, CA, November 1986.
• 29: Sasao, W. : "An Algorithm to Derive the Complement of a Binary Function with Multiple-Valued Input", IEEE Trans. on Comput., Vol. C~34, 1No.2, pp.131-140, Febr. 1985.
• 30: Single, j.R., Chang~ C.L., Lee, R.O.T. : "A New Algorithm for Generating Prime implicants", IEEE TEC, Vol. EC-19, pp. 304-311, April 1970.
• 31: Antonin Svoboda, The Concept of Term Exclusiveness and Its Effect on the Theory of Boolean Functions, Journal of the ACM (JACM), v.22 n.3, p.425-440, July 1975 [doi>10.1145/321892.321904]
• 32: Wojutynskl, J. :"A General System to Solve Combinatorial Problems by Reduction to Graph Coloring", M.Sc. Thesis, (M. Perkowski ~uperv,), Institute of Automatic Control, School of Electronic Engineering, Warsaw Technical University, May 1979, (in Polish).

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

Additional Classification:
  C. Computer Systems Organization

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Design, Measurement, Performance, Theory