SavedAdd your journal

Journals / Turkish Journal of Electrical Engineering and Computer Science / 2010 / Cilt: 18 - Sayı: 6

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

Fatih BAŞÇİFTÇİ
Şirzat KAHRAMANLI
Pages
1041–1052
Publication Date
2010-06-01
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The results show that proposed algorithm obtains good results and faster than ESPRESSO.

📌 3 Key Takeaways

🎯
Objective & Hypothesis: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.
📊
Key Findings & Data: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.
💡
Conclusion & Impact:The results show that proposed algorithm obtains good results and faster than ESPRESSO.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Boolean minimization · logic operations · prime implicants

Abstract

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.

Özet

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.

🔖

Cite This Article

BAŞÇİFTÇİ, F., KAHRAMANLI, Ş. (2010). Fast computation of determination of the prime implicants by a novel near minimum minimization method. Turkish Journal of Electrical Engineering and Computer Science, Cilt: 18 - Sayı: 6, 1041–1052. https://ajindex.com/articles/188826

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (11)

  1. T. Sasao, “Worst and Best Irredundant Sum-of–Product Expressions”, IEEE Transactions on Computers, Vol. 50(9), pp. 935-947, 2001.
  2. 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.
  3. 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.
  4. R. K. Brayton, G.D. Hachtel, C.T. McMullen, A. Singiovanni-Vincentelli, “Logic Minimization Algorithms for VLSI Synthesis”, Boston, Kluwer Academic, 1984.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. K.A. Bartlett, R.K. Brayton, G. D. Hachtel, R. M. Jacoby, C. R. Morrison, R. L. Rudell, A. Sangiovanni-Vincentelli, Albert R. Wang, “Multilev