Control Systems and Computers

https://doi.org/10.15407/csc.2021.01.003

Control Systems and Computers, 2021, Issue 1 (291), pp. 3-14.

UDC 519.718

B.Ye. RYTSAR, Doctor of Technical Sciences, Professor, Department of Radioelectronic Devices Systems, Institute of Telecommunications, Radioelectronics and Electronic Engineering, L’viv polytechnic National University, Bandera str., 12, L’viv, 79013, Ukraine, bohdanrytsar@gmail.com
A.O. BELOVOLOV, Master, Institute of Telecommunications, Radioelectronics and Electronic Engineering, L’viv polytechnic National University, Bandera str., 12, L’viv, 79013, Ukraine, bohdanrytsar@gmail.com

A New Method of the Logical FunctionsMinimization in the Polynomial Set-Theoretical Format. «Handshaking» Procedure

A new minimization method of logic functions of n variables in polynomial set-theoretical format has been considered. The method based on the so-called “handshaking” procedure.  This procedure reflects the iterative polynomial extension of two conjuncterms of different ranks, the Hamming distance between which can be arbitrary. The advantages of the suggested method are illustrated by the examples.

 Download full text! (On English)

Keywords: minimization of logical function, conjuncture, polynomial set-theoretic format, heming distance, “handshake” procedure.

1. Besslish P. W. 1983. “Efficient computer method for EXOR logic design”, IEEProc. Pt. E., 130, pp. 203-206.
   https://doi.org/10.1049/ip-e.1983.0045
2. Sasao T., 1999. Switching Theory for Logic Synthesis. Kluwer Academic Publ. 361 p.
   https://doi.org/10.1007/978-1-4615-5139-3
3. Papakonstantinou G., 2014. “A Parallel algorithm for minimizing ESOP expressions”, J. Circuits Syst. Comp., 23 (01), 1450015 (17 p.).
   https://doi.org/10.1142/S0218126614500157
4. Saul J., 1992. “Logic Synthesis for Arithmetic Circuits using the Reed-Muller Representation”, IEEE Proc. of 3rd European Conf. on Design Automation, pp. 109-113. DOI: 10.1109/EDAC.1992.205904.
   https://doi.org/10.1109/EDAC.1992.205904
5. Perkowski M., Chrzanowska-Jeske M., 1990. “An exact algorithm to minimize mixed-radix exclusive sums of products for incompletely specified boolean functions”, Proc. Int. Symp. Circuits Syst., New Orleans, LA, pp. 1652-1655.
6. Tsai C., Marek-Sadowska M., 1996. “Multilevel Logic Synthesis for Arithmetic Functions”, Proc. DAC’96, pp. 242-247.
   https://doi.org/10.1145/240518.240563
7. Hirayama T., Nishitani Y., 2009. “Exact minimization of AND-EXOR expressions of practical benchmark functions”, Journal of Circuits, Systems and Computers, 18 (3), pp. 465-486.
   https://doi.org/10.1142/S0218126609005356
8. Debnath D., Sasao T., 2005. “Output phase optimization for AND-OR-EXOR PLAs with decoders and its application to design of adders”, IEICE Trans. Inf. & Syst., E88-D (7), pp. 1492-1500.
   https://doi.org/10.1093/ietisy/e88-d.7.1492
9. Fujiwara H., 1986. “Logic testing and design for testability”, Comp. Syst. Series, Mass. Inst. Tech., MA, Cambridge.
   https://doi.org/10.7551/mitpress/4317.001.0001
10. Sasao T., 1997. “Easily testable realizations for generalized Reed-Muller expressions”, IEEE Trans. On Computers, 46 (6), pp. 709-716.
    https://doi.org/10.1109/12.600830
11. Faraj K., 2011. “Design Error Detection and Correction System based on Reed-Muller Matrix for Memory Protection”, Inter. J. of Computer Applications (0975-8887), 34 (8), pp. 42-55.
12. Sampson M., Kalathas M., Voudouris D., Papakonstantinou G., 2012. “Exact ESOP expressions for incompletely specified functions”, VLSI Journal, 45 (2), pp. 197-204.
    https://doi.org/10.1016/j.vlsi.2011.10.001
13. Stergiou S., Papakonstantinou G., 2004. “Exact minimization of ESOP expressions with less than eight product terms”, Journal of Circuits. Systems and Computers, 13 (1), pp. 1-15.
    https://doi.org/10.1142/S0218126604001295
14. Debnath D., Sasao T., 2007. “A New Relation of Logic Functions and Its Application in the Desing of AND-OR-EXOR Networks”, IEICE Trans. Fundamentals, E90-A (5), pp. 932-939.
    https://doi.org/10.1093/ietfec/e90-a.5.932
15. Mishchenko A., Perkowski M., 2001. “Fast Heuristic Minimization of Exclusive-Sums-of-Products”, Proc. Reed-Muller Inter. Workshop’01, pp. 242-250.
16. Wu X., Chen X., Hurst S. L., 1982. “Mapping of Reed-Muller Coefficients and the Minimization of Exclusive OR Switching Function”, IEEE Proc. Pt. E., 129, pp. 5-20.
    https://doi.org/10.1049/ip-e.1982.0004
17. Fleisher H., Tavel M., Yager J., 1987. “A computer algorithm for minimizing Reed-Muller cannonical forms”, IEEE Trans. Comput., C-36, pp. 247-250.
    https://doi.org/10.1109/TC.1987.1676890
18. Even S., Kohavi I., Paz A., 1967. “On minimal modulo-2-sum of products for switching functions”, IEEE Trans. Electr. Comput.”, EC-16:671-674.
    https://doi.org/10.1109/PGEC.1967.264777
19. Helliwell M., Perkowski M., 1988. “A fast algorithm to minimize mixed polarity generalized Reed-Muller forms”, Proceedings of the 25th ACM/IEEE Design Automation Conference, IEEE Computer Society Press, Washington, DC, United States, pp. 427-432.
20. Song N., Perkowski M., 1996. “Minimization of Exclusive Sum-of-Products Expressions for Multiple-Valued Input, Incompletely Specified Functions”, IEEE Trans. Comput.-Aided Design of Integrated Circuits and Systems, 15 (4), pp. 385-395.
    https://doi.org/10.1109/43.494702
21. Saul J., 1991. Logic synthesis based on the Reed-Muller representation. URL: http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=A765F8A29F4FB9D2143A1DB7CDC91593?doi=10.1.1.45.8570.
22. Zakrenskij A., 1995. “Minimum Polynomial Implementation of Systems of Incompletely Specified Functions”, Proc. of IFIP WG 10.5 Workshop on Applications of Reed-Muller Expansion in Circuits Design, pp. 250-256.
23. Brand D., Sasao T., 1993. “Minimization of AND-EXOR Using Rewrite Rules”, IEEE Trans. on Comp., 42 (5).
    https://doi.org/10.1109/12.223676
24. Knysh D., Dubrova E., 2011. “Rule-Based Optimization of AND-XOR Expressions”, Facta universitatis – series: Electronics and Energetics” 24 (3), pp. 437-449.
    https://doi.org/10.2298/FUEE1103437K
25. Wang L., 2000. Automated Synthesis and Optimization of Multilevel Logic Circuits. URL: http://researchrepository.napier.ac.uk/4342/1/Wang.pdf.
26. Stergiou S., Daskalakis K., Papakonstantinou G., 2004. “A Fast and Efficient Heuristic ESOP Minimization Algorithm”, GLSVLSI’04, Boston, Massachusetts, USA.
    https://doi.org/10.1145/988952.988971
27. Rytsar B. Ye., 1998. “Minimizatsiya bulevykh funktsiy metodom rozcheplennya konyunktermiv”, Control systems and Computers, 5, pp. 14-22. (In Ukrainian).
28. Rytsar B. Ye., 2004. Teoretyko-mnozhynni optymizatsiyni metody lohikovoho syntezu kombinatsiynykh merezh, D. Sc. Dissertation, Lviv, 348 p. (In Ukrainian).
29. Rytsar B. Ye., 2013. “Minimizatsiya systemy lohikovykh funktsiy metodom paralelnoho rozcheplennya konyunktermiv”, Visnyk NU LP “Radioelektronika ta telekomunikatsiyi”, 766, pp. 18-27. (In Ukrainian).
30. Rytsar B. Ye., 2013. “Chyslova teoretyko-mnozhynna interpretatsiya polinoma Zhegalkina”, Control systems and Computers, 1, pp. 11-26. [online] Available at: <http://usim.org.ua/arch/2013/1/3.pdf> (In Ukrainian).
31. Rytsar B. Ye., 2007. “Vizerunky bulovykh funktsiy: metod minimizatsiyi”, Control systems and Computers, 3, pp. 34-51. (In Ukrainian).
32. Tran A., 1987. “Graphical method for the conversion of minterms to Reed-Muller coefficients and the minimization of exclusive-OR switching functions”, Proc. IEE, Pt. E, Computer Digital Techs, 134 (2), pp. 93-99.
    https://doi.org/10.1049/ip-e.1987.0016
33. Tinder R. F., 2000. Engineering digital design. Academic Press, 884 p.
34. Zakrevskiy A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskiye osnovy proyek-tirovaniya diskretnykh ustroystv, Fizmatlit, Moscow, 2007. 592 p. (In Russian).
35. Sasao T. A Design Method for AND-OR-EXOR Three-Level Networks. [online] Available at: http://www.researchgate.net/publication/2362534.
36. Tran A., 1989. “Tri-state map for the minimization of exclusive-OR switching functions”, Proc. IEE, Pt E, Computer Digital Techs, 136 (1), pp. 16-21.
    https://doi.org/10.1049/ip-e.1989.0003
37. McKenzie L., Almaini A. E. A., Miller J. F., Thomson P., 1993. “Optimisation of Reed-Muller logic functions”, Inter. J. of Electronics, 75 (3), pp. 451-466.
    https://doi.org/10.1080/00207219308907124
38. Majewski W., 1997. Uklady logiczne. Wzbrane zagadnienia. Wydawnictwo Politechniki Warszawskiej, Warszawa, 180 p.
39. Zeng X., Perkowski M., Dill K., 1995. “Approximate Minimization Of Generalized Reed-Muller Forms”, Proc. Reed-Muller’95, pp. 221-230.
40. Al Jassani B. A., Urquhart N., Almaini A. E. A., 2009. “Minimization of Incompletely Specified Mixed Polarity Reed-Muller Functions using Genetic Algorithm”, 2009 3rd International Conference on Signals, Circuits and Systems (SCS). DOI: 10.1109/ICSCS.2009.5412318
    https://doi.org/10.1109/ICSCS.2009.5412318
41. Sasao T., 2011. Memory-Based Logic Synthesis, Springer, 189 p.
    https://doi.org/10.1007/978-1-4419-8104-2

Received 24.11.2020