RECURSIVE TERNARY-BASED ALGORITHM FOR COMPUTING PRIME IMPLICANTS OF MULTI-OUTPUT BOOLEAN FUNCTIONS

Authors

  • Zaid Al-Wardi Electrical Engineering Department, College of Engineering, Mustansiriyah University, Baghdad, Iraq Author https://orcid.org/0000-0002-9117-4801
  • Osama Al-Wardi Brandenburg University of Technology, Cottbus-Senftenberg, Germany Author

DOI:

https://doi.org/10.31272/jeasd.27.3.2

Keywords:

Boolean Algebra, Sum of products, Two-level Boolean representation, Logic Circuit Synthesis

Abstract

The problem of computing the set of prime implicants to represent a Boolean function is a classical problem that is still considered a running problem for research because all known approaches have limitations. The article reviews existing methods for computing prime implicants and highlights their limitations, particularly for multi-output functions and limited scalability due to the growth in memory required to complete the computation. Then it proposes a recursive ternary-based minimization algorithm to compute the prime implicants of multi-output Boolean functions. The algorithm is based on the concept of Programmable Logic Array (PLA) tables, which provide a structured and efficient representation of Boolean functions. The algorithm takes advantage of the ternary logic system to efficiently compute the prime implicants while maintaining scalability for large and complex functions, which has significant implications for digital circuit design and optimization.

References

Prasad, V. C. (2018). Novel method to simplify Boolean functions. Automatyka/Automatics, 22(2), 29. https://doi.org/10.7494/automat.2018.22.2.29

Rai, S., Neto, W. L., Miyasaka, Y., Zhang, X., Yu, M., Yi, Q., Fujita, M., Manske, G. B., Pontes, M. F., da Rosa, L. S., de Aguiar, M. S., Butzen, P. F., Chien, P.-C., Huang, Y.-S., Wang, H.-R., Jiang, J.-H. R., Gu, J., Zhao, Z., Jiang, Z., … Chatterjee, S. (2021). Logic Synthesis Meets Machine Learning: Trading Exactness for Generalization. 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE). https://doi.org/10.23919/date51398.2021.9473972

Fujita, M. (2019). Basic and Advanced Researches in Logic Synthesis and their Industrial Contributions. Proceedings of the 2019 International Symposium on Physical Design. https://doi.org/10.1145/3299902.3311069

Salhi, Y. (2018). Approaches for Enumerating All the Essential Prime Implicants. Lecture Notes in Computer Science, 228–239.

https://doi.org/10.1007/978-3-319-99344-7_21

Mados, B., Bilanova, Z., Chovancova, E., and Adam, N. (2019). Field Programmable Gate Array Hardware Accelerator of Prime Implicants Generation for Single-Output Boolean Functions Minimization. 2019 17th International Conference on Emerging ELearning Technologies and Applications (ICETA). https://doi.org/10.1109/iceta48886.2019.9040020

Kubica, M., Opara, A., and Kania, D. (2020). Methods for Representing Boolean Functions—Basic Definitions. Technology Mapping for LUT-Based FPGA, 15–24. https://doi.org/10.1007/978-3-030-60488-2_2

Quine, W. V. (1952). The Problem of Simplifying Truth Functions. The American Mathematical Monthly, 59(8), 521–531. https://doi.org/10.1080/00029890.1952.11988183

McCluskey, E. J. (1956). Minimization of Boolean Functions*. Bell System Technical Journal, 35(6), 1417–1444. https://doi.org/10.1002/j.1538-7305.1956.tb03835.x

Petrick, S. R., and Sethares, G. C. (1968). On the Determination of Complete Sets of Logical Functions. IEEE Transactions on Computers, C-17(3), 273–273. https://doi.org/10.1126/science.162.3858.1109

Seda, P., Seda, M., Hosek, J., Dvorak, J., and Sedova, J. (2019). The Improvement of Quine-McCluskey Method Using Set Covering Problem for Safety Systems. 2019 4th International Conference on Intelligent Green Building and Smart Grid (IGBSG). https://doi.org/10.1109/igbsg.2019.8886174

Joshi, M., Sunori, S. K., Tewari, N., Maurya, S., Joshi, M., and Juneja, P. K. (2021). Formulation of C++ program for Quine–McCluskey Method of Boolean Function Minimization. Machine Learning, Advances in Computing, Renewable Energy and Communication, 341–346. https://doi.org/10.1007/978-981-16-2354-7_31

Vu, H.-G., Bui, N.-D., Nguyen, A.-T., and ThanhBangLe. (2021). Performance Evaluation of Quine-McCluskey Method on Multi-core CPU. 2021 8th NAFOSTED Conference on Information and Computer Science (NICS). https://doi.org/10.1109/nics54270.2021.9701506

Balasubramanian, P., Bernasconi, A., Ciriani, V., and Villa, T. (2021). A Boolean Heuristic for Disjoint SOP Synthesis. 2021 24th Euromicro Conference on Digital System Design (DSD). https://doi.org/10.1109/dsd53832.2021.00019

Su, S., Zou, C., Kong, W., Han, J., and Qian, W. (2020). A Novel Heuristic Search Method for Two-Level Approximate Logic Synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39(3), 654–669. https://doi.org/10.1109/tcad.2018.2890532

Miao, J., Gerstlauer, A., & Orshansky, M. (2013). Approximate logic synthesis under general error magnitude and frequency constraints. 2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). https://doi.org/10.1109/iccad.2013.6691202

Ammes, G., Neto, W. L., Butzen, P., Gaillardon, P.-E., & Ribas, R. P. (2022). A Two-Level Approximate Logic Synthesis Combining Cube Insertion and Removal. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(11), 5126–5130. https://doi.org/10.1109/tcad.2022.3143489

Ammes, G., Butzen, P. F., Reis, A. I., & Ribas, R. (2022). Two-Level and Multilevel Approximate Logic Synthesis. Journal of Integrated Circuits and Systems, 17(3), 1–14. https://doi.org/10.29292/jics.v17i3.661

Kanakia, H., Nazemi, M., Fayyazi, A., & Pedram, M. (2021). ESPRESSO-GPU: Blazingly Fast Two-Level Logic Minimization. 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE). https://doi.org/10.23919/date51398.2021.9473961

Potvin, N., Bersini, H., and Milojevic, D. (2022). Espresso to the rescue of genetic programming facing exponential complexity. Proceedings of the Genetic and Evolutionary Computation Conference Companion. https://doi.org/10.1145/3520304.3529005

Duşa, A. (2008). A mathematical approach to the boolean minimization problem. Quality & Quantity, 44(1), 99–113. https://doi.org/10.1007/s11135-008-9183-x

Rudell, R. L., and Sangiovanni-Vincentelli, A. (1987). Multiple-Valued Minimization for PLA Optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(5), 727–750. https://doi.org/10.1109/tcad.1987.1270318

Fiser, P., Rucky, P., and Vanova, I. (2008). Fast Boolean Minimizer for Completely Specified Functions. 2008 11th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems. https://doi.org/10.1109/ddecs.2008.4538768

Lee, S.-Y., Kim, S., and Kang, S. (2019). Ternary Logic Synthesis with Modified Quine-McCluskey Algorithm. 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL). https://doi.org/10.1109/ismvl.2019.00035

Stanković, R. S., Astola, J. T., and Moraga, C. (2012). Representation of Multiple-Valued Logic Functions. Synthesis Lectures on Digital Circuits & Systems, Morgan & Claypool Publishers. ISBN: 978-3-031-79852-8

Al-Wardi, Z. (2021). Radix-p Multiple Valued Logic Function Simplification using Higher Radix Representation. Journal of Physics: Conference Series, 1804(1), 012016. https://doi.org/10.1088/1742-6596/1804/1/012016

Downloads

Published

2023-05-01

Issue

Vol. 27 No. 3 (2023): Journal of Engineering and Sustainable Development

Section

Articles

License

Copyright (c) 2023 Zaid Al-Wardi, Osama Al-Wardi

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The Journal of Engineering and Sustainable Development is an open-access journal that all contents are free of charge. Articles of this journal are licensed under the terms of the Creative Commons Attribution International Public License CC-BY 4.0 (https://creativecommons.org/licenses/by/4.0/legalcode) that licensees are unrestrictly allowed to search, download, share, distribute, print, or link to the full texts of the articles, crawl them for indexing and reproduce any medium of the articles provided that they give the author(s) proper credits (citation). The journal allows the author(s) to retain the copyright of their published article.
Creative Commons-Attribution (BY)

How to Cite

RECURSIVE TERNARY-BASED ALGORITHM FOR COMPUTING PRIME IMPLICANTS OF MULTI-OUTPUT BOOLEAN FUNCTIONS. (2023). Journal of Engineering and Sustainable Development, 27(3), 308-316. https://doi.org/10.31272/jeasd.27.3.2