Research PapersNo Access

A Nonlinear Integer Programming Approach for the Minimization of Boolean Expressions

K. G. Papakonstantinou

http://orcid.org/0000-0002-5254-1066

Department of Civil and Environmental Engineering, The Pennsylvania State University, University Park, PA 16802, USA

E-mail Address: [email protected]

Corresponding author.

Search for more papers by this author

and

G. Papakonstantinou

School of Electrical and Computer Engineering, National Technical University of Athens, Zografou Campus, Athens 15780, Greece

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S0218126618501633Cited by:3 (Source: Crossref)

Abstract

A novel approach is suggested in this paper for the minimization of Boolean expressions. This is particularly useful in logic synthesis, since it leads to simpler logic circuit implementations. Although the proposed method is general, emphasis is given on Exclusive-or Sum Of Products (ESOPs) functions. A transformation is derived to convert the problem from the Boolean algebra area to the classical algebraic area. The resulting problem becomes a nonlinear, integer program and an original branch-and-bound procedure with several relaxations is developed for its solution. The suggested methodology is especially suitable for the minimization of incompletely specified functions, which is a difficult problem in the Boolean area. Numerical examples are provided to demonstrate the applicability and performance of the approach and possible future directions are described. The resulting nonlinear problems can sometimes be very demanding but their challenging solutions could solve open ESOP problems.

This paper was recommended by Regional Editor Emre Salman.

Keywords:

References

1. T. Sasao and P. Besslich, On the complexity of mod-2 sum pla’s, IEEE Trans. Comput. 39 (1990) 262–266. Crossref, Web of Science, Google Scholar
2. A. Gaidukov, Algorithm to derive minimum esop for 6-variable function, 5th Int. Workshop on Boolean Problems (TU Freiberg, Freiberg, Germany, 2002), pp. 141–148. Google Scholar
3. T. Hirayama and Y. Nishitani, A faster algorithm of minimizing and-exor expressions, IEICE Trans. Fund. Electr. 85 (2002) 2708–2714. Google Scholar
4. T. Hirayama and Y. Nishitani, Exact minimization of and–exor expressions of practical benchmark functions, J. Circuits Syst. Comput. 18 (2009) 465–486. Link, Web of Science, Google Scholar
5. N. Koda and T. Sasao, Lp characteristic vector for logic functions, in IFIP WG 10.5 Workshop on Applications of the Reed–Muller Expansion in Circuit Design (Elsevier, Grenoble, France, 1993), pp. 99–108. Google Scholar
6. G. Papakonstantinou, Minimization of modulo-2 sum of products, IEEE Trans. Comput. 100 (1979) 163–167. Crossref, Google Scholar
7. G. Papakonstantinou, Minimal modulo-2 expressions of switching functions with five variables, Int. J. Electron. 50 (1981) 211–214. Crossref, Web of Science, Google Scholar
8. G. Papakonstantinou, A parallel algorithm for minimizing esop expressions, J. Circuits Syst. Comput. 23 (2014) 1450015. Link, Web of Science, Google Scholar
9. M. Sampson, M. Kalathas, D. Voudouris and G. Papakonstantinou, Exact esop expressions for incompletely specified functions, Integration 45 (2012) 197–204. Crossref, Web of Science, Google Scholar
10. S. Stergiou, D. Voudouris and G. Papakonstantinou, Multiple-value exclusive-or sum-of-products minimization algorithms, IEICE Trans. Fund. Electr. 87 (2004) 1226–1234. Google Scholar
11. S. Stergiou and G. Papakonstantinou, Exact minimization of esop expressions with less than eight product terms, J. Circuits Syst. Comput. 13 (2004) 1–15. Link, Web of Science, Google Scholar
12. A. Mishchenko and M. Perkowski, Fast heuristic minimization of exclusive-sums-of-products, in Int. Workshop on Applications of the Reed–Muller Expansion in Circuit Design (Starkville, MS, USA, 2001), pp. 242–250. Google Scholar
13. T. Sasao, Exmin2: A simplification algorithm for exclusive-or-sum-of-products expressions for multiple-valued input two-valued output functions, IEEE T. Comput. Aid. D. 12 (1993) 621–632. Crossref, Web of Science, Google Scholar
14. M. Kalathas, D. Voudouris and G. Papakonstantinou, A heuristic algorithm to minimize esops for multiple-output incompletely specified functions, in Proceedings of the 16th ACM Great Lakes Symposium on VLSI (GLSVLSI), ACM (2006), pp. 357–361. Google Scholar
15. T. Kozlowski, E. L. Dagless and J. M. Saul, An enhanced algorithm for the minimization of exclusive-or sum-of-products for incompletely specified functions, in IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors, IEEE 1995, pp. 244–249. Google Scholar
16. N. Song and M. A. Perkowski, Minimization of exclusive sum-of-products expressions for multiple-valued input, incompletely specified functions, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 15 (1996) 385–395. Crossref, Web of Science, Google Scholar
17. R. Drechsler, B. Becker and N. Drechsler, Genetic algorithm for minimisation of fixed polarity Reed–Muller expressions, IEE Proc., Comput. Digit. Tech. 147 (2000) 349–353. Crossref, Google Scholar
18. R. Drechsler, B. Becker and N. Göckel, A genetic algorithm for minimization of fixed polarity Reed–Muller expressions, in Artificial Neural Nets and Genetic Algorithms (Springer, Vienna, Austria, 1995), pp. 393–395. Google Scholar
19. A. Finder and R. Drechsler, An evolutionary algorithm for optimization of pseudo kronecker expressions, in 40th IEEE Int. Symp. Multiple-Valued Logic (ISMVL) (IEEE, Barcelona, Spain, 2010), pp. 150–155. Google Scholar
20. C. Pedraza, J. Castillo, J. I. Martinez, P. Huerta, J. L. Bosque and J. Cano, Genetic algorithm for boolean minimization in an fpga cluster, J. Supercomput. 58 (2011) 244–252. Crossref, Web of Science, Google Scholar
21. R. H. Byrd, M. E. Hribar and J. Nocedal, An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim. 9 (1999) 877–900. Crossref, Web of Science, Google Scholar
22. R. A. Waltz, J. L. Morales, J. Nocedal and D. Orban, An interior algorithm for nonlinear optimization that combines line search and trust region steps, Math. Program. 107 (2006) 391–408. Crossref, Web of Science, Google Scholar