Fast computation of determination of the prime implicants by a novel near minimum minimization method

In this study proposed is an off-set-based direct-cover near-minimum minimization method for single-output Boolean functions represented in a sum-of-products form. To obtain the complete set of prime implicants including given on-cube (on-minterm), the proposed method uses off-cubes (off-minterms) expanded by this On-cube. The amount of temporary results produced by this method does not exceed the size of the off-set. To make fast computation, we used logic operations instead of standard operations. Expansion off-cubes, commutative absorption operations and intersection operations are realized by logic operations for fast computation. The proposed minimization method is tested on several different kinds of problems and benchmarks results of which are compared with logic minimization program ESPRESSO. The results show that proposed algorithm obtains good results and faster than ESPRESSO.

Anahtar Kelimeler:

Boolean minimization, logic operations, prime implicants, direct cover

Fast computation of determination of the prime implicants by a novel near minimum minimization method

Keywords:

Boolean minimization, logic operations, prime implicants, direct cover,

PDF

___

T. Sasao, “Worst and Best Irredundant Sum-of–Product Expressions”, IEEE Transactions on Computers, Vol. 50(9), pp. 935-947, 2001.
A. Mishchenco, T. Sasao, “Large-Scale SOP Minimization Using Decomposition and Functional Properties”, IEEE CNF, Design Automation Conference, Proceedings, pages:149-154, 2-6 June 2003.
S. Kahramanli, F. Ba¸s¸cift¸ci, “Boolean Functions SimpliŞcation Algorithm of O(N) Complexity”, Journal of Math- ematical And Computational Applications Vol. 8, No 4, pp. 271–278, 2002.
O. Coudert, “Two-Level Logic Minimization: an Overview”, The VLSI Journal, 17-2, pp. 97-140, October 1994.
D.L. Dietmeyer, “Logical Design of Digital Systems”, 2nded. Boston, 1978.
R. K. Brayton, G.D. Hachtel, C.T. McMullen, A. Singiovanni-Vincentelli, “Logic Minimization Algorithms for VLSI Synthesis”, Boston, Kluwer Academic, 1984.
E. Hong, S. Muroga, “Absolute Minimization of Completely SpeciŞed Switching Functions”, IEEE Trans. Comput- ers, vol. 40, no 11, pp 53-65, January, 1991.
P.R. Tirumalai, J.T. Butler, “Minimization Algorithms for Multiple-Valued Programmable Logic Arrays”, IEEE Trans. Comp, vol.40, no:2, pp:167-178, 1991.
T. Sasao, “A SimpliŞcation Algorithm for Exclusive OR-Sum-of Products Expressions for Multiple–Valued- Input Two- Valued – Output Functions”, IEEE Trans. Computer Aided Design, vol. 12, no 5, pp.621-632, May, 1993.
P. McGeer, J. Sanghavi, R.K. Brayton, A. Sangiovanni-Vincentelli, “ESPRESSO-SIGNATURE: A New Exact Minimizer for Logic Functions”, IEEE Transactions on VLSI, Vol. 1, No. 4, pp. 432-440, 1993.
R. S. Perkins, T. Rhyne, “An Algorithm for Identifying and Selecting The PI’s of a Multiple-Output Boolean Function”, IEEE Trans. Computer Aided Design, vol. 7, no 11, pp.1215-1218, November 1988.
B. Gurunath, N. N. Biswas, “An Algorithm for Multiple Output Minimization”, IEEE Trans. Comp.Aided Design, Vol. 8, no 9, September 1989.
S¸. Kahramanlı,S. G¨une¸s, S. S¸ahan, F. Ba¸s¸cift¸ci, “A New Method Based on Cube Algebra for The SimpliŞcation of Logic Functions”, The Arabian Journal For Science and Engineering Volume 32, Number 1B, pages:1-14, April 2007.
P. Fisher, J. Hlavicka, H. Kubatova, “FC-Min: “A Fast Multi-Output Minimizer”, IEEE CNF, Digital System Design, Proceedings, Euromicro Symposium on, 1-6, pages:451-454, Sept. 2003.
R. E. Miller, “Switching Theory”, Vol. 1. New York: Wiley, 1965.
K.A. Bartlett, R.K. Brayton, G. D. Hachtel, R. M. Jacoby, C. R. Morrison, R. L. Rudell, A. Sangiovanni-Vincentelli, Albert R. Wang, “Multilevel Logic Minimization Using Implicit Don’t Cares”, IEEE Trans. Computer Aided Design, vol. 7, no 6, pp. 723-740, June 1988.
A.A. Malik, R.K. Brayton, A.R. Newton, A.Singiovanni-Vincentelli, “Two-Level Minimization of Multi valued Functions with Large Oﬀsets”, IEEE Trans. Comput., vol. 42, no 11, pp. 1325-1342, November 1993.
T. Sasao, J.T. Butler, “Worst and Best Irredundant Sum-of-Product Expressions”, IEEE Trans. Comput., vol. 50, no 9, pp. 935-947, September 2001.
A.A. Malik, R.K. Brayton, A.R. Newton, A. Singiovanni-Vincentelli, “Reduced Oﬀsets for Minimization of Binary- Valued Functions”, IEEE Trans. Comput., vol. 10, no 4, pp. 413-426, April 1991.
C. Umans, T.Villa and A. Singiovanni-Vincentelli, “Complexity of Two-Level Logic Minimization”, IEEE Trans. Comput. Aided Design of Integrated Circuits and Systems, vol. 25, no 7, pp. 1230-1246, July 2006.
F. Ba¸s¸cift¸ci, “Local SimpliŞcation Algorithms for Switching Functions”, PhD Thesis, Graduate School of Natural and Applied Sciences, Selcuk University, 2006.
De Micheli Giovanni, “Synthesis and Optimization of Digital Circuits”, New York, Mccraw-Hill, 1994.
F. Ba¸s¸cift¸ci, S¸. Kahramanlı, “An Oﬀ-Cubes Expanding Approach to the Problem of Separate Determination of the Essential Prime Implicants of the Single-Output Boolean Functions” EUROCON 2007, Warsaw-Poland, ISBN:1- 4244-0813-X, pages: 432-438, 09-12 September 2007.
F. Ba¸s¸cift¸ci, “SimpliŞcation of Single Output Boolean Functions by Exact Direct Cover Algorithm Based on Cube Algebra” EUROCON 2007, Warsaw-Poland, ISBN:1-4244-0813-X, pages: 427-431, 09-12 September 2007.
E. Nadjafov and. S¸. Kahramanlı, “On The Synthesis of Multiple Output Switching Scheme”, ScientiŞc Notes of Azerbaijan Institute of Petroleum and Chemistry, 9(3), pp. 65-69, 1973.
F. Ba¸s¸cift¸ci, S¸. Kahramanlı, “The Modelling of Cube Algebra Operations by the Basic Computer Operations”, Proceeding of The International Conference on Modeling and Simulation, The Association for Modeling and Simulation in Enterprises (AMSE), Sel¸cuk Uni., Vol.II, pages:595-599, 2006.