KaydedilenlerDerginizi ekleyin

Dergiler / 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
Sayfa
1041–1052
Yayın Tarihi
2010-06-01
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

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

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez: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.
📊
Temel Bulgular & Veri: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.
💡
Sonuç & Katkı:The results show that proposed algorithm obtains good results and faster than ESPRESSO.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Boolean minimization · logic operations · prime implicants

Ö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.

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.

🔖

Bu Makaleye Atıf Yap

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

📄 Tam Metin PDF Okuyucu

📄

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

Kaynakça (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