Control Systems and Computers

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

Control Systems and Computers, 2019, Issue 5 (283), pp. 5-11.

UDC 519.713

B.Ye. Rytsar, Doctor (Eng.), Professor, Department of Radioelectronic Devices Systems, Institute of Telecommunications, Radioelectronics and Electronic Engineering, L’viv polytechnic National University, Bandera srt., 12, L’viv, Ukraine, e-mail: bohdanrytsar@gmail.com

A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. II

The paper presents a new method for the recognition of the different types of total and partial symmetry in Boolean functions based on the numeric set-theoretical differentiation. The proposed algorithm is based on the theorem on the recognition of different types of partial symmetry. This algorithm, compared to the known, has a relatively less computational complexity of realization due to a comparatively smaller number of operations and procedures necessary for the accomplishment of the given task. This is proved by the presented examples for the recognition of the proposed method of the different types of symmetry in complete and incomplete of Boolean functions, including given in the SOP format, taken for comparison reasons from publications of the well-known authors.

   Download full text! (On English)

Keywords: recognition of total and partial symmetry, Boolean function, numeric set-theoretical differentiation.

1. Maurer, P.M., 2015. “Symmetric Boolean Functions”, Int. J. of Math., Game Theory and Algebra, 24 (2–3), pp. 159-202.
2. Scholl, Ch., 2001. “Functional Demposition with Application to FPGA Synthesis”, Kluwer Academic Publishers, Boston/Dordrecht/London, pp. 50–63.
3. Schneeweiss, W. G., 1989. Boolean Functions with Engineering Applications and Computer Programs, Springer-Verlag Berlin Heidelberg, 264 p.
4. Bhattacharjee, P.K., 2010. “Digital Combinational Circuits Design with the Help of Symmetric Functions Considering Heat Dissipation by Each QCA Gate”, Intern. J. of Computer and Electrical Engineering, 2 (4), pp. 666-672.
   https://doi.org/10.7763/IJCEE.2010.V2.209
5. Stanica, P., Maitra, S., 2008. “Rotation symmetric Boolean functions – Count and cryptographic properties”, Discrete Applied Mathematics, 156 (10), pp. 1567-1580.
   https://doi.org/10.1016/j.dam.2007.04.02
6. Butler, J.T., Sasao, T., 2010. “Boolean Functions for Cryptography”, In book Sasao T., Butler J.T.: Progress in Applications of Boolean Functions, pp. 33–53.
7. Zhang, J. S., Mishchenko, A., Brayton, R., Chszanowska, M., 2006. “Symmetry Detection for Large Boolean Functions using Circuit Representation, Simulation and Satisfiability”, DAC 2006, July 24-28. pp. https://people.eecs.berkeley.edu/~alanmi/publications/2006/dac06_sym.pdf
   https://doi.org/10.1145/1146909.1147044
8. Butler, J.T., Dueck, G.W., Holowinski, G., Shmerko, V.P., Janushkewich, V.N., 1999. “On Recognition of Symmetries for Switching Functions in Reed-Muller Forms”, Proc. PRIP’99, Belarus, 1, pp. 215–234.
9. Paulin, O.N., Lyakhovetskiy, A.M., 2007. “Metod doopredeleniya nepolnost’yu zadannoy funktsii do simmetricheskoy”, Elektron. modelirovaniye, 21 (6), pp. 21-30. (In Russian).
10. Zakrevskiy A.D., Pottosin Yu.V., Cheremisinova L.D., 2007. Logicheskiye osnovy proyektirovaniya diskretnykh ustroystv, M.: Fizmatlit, 592 p. (In Russian).
11. Rytsar, B., 2018. “Set-Theoretical Decomposition on the Basis of Symmetric Functions”, Proc. TCSET’2018, 20-24 Feb., pp. 868-872.
    https://doi.org/10.1109/TCSET.2018.8336334
12. Steinbach, B., Posthoff, C., 2009. Logic Functions and Equations, Examples and Exercises. Springer Science + Business Media B.V., 230 p.
13. Steinbach, B., Posthoff, C., 2017. Boolean Differential Calculus. Morgan & Claypool Publishers series, 195 p., morganclaypool.com
14. Kuo-Hua Wang and Jia-Hung Chen, 2004. “Symmetry Detection for Incompletely Specified Functions”, DAC 2004, June 7–11, San Diego, California, USA, pp. 434–437, https://www.sciencedirect.com/science/journal/0166218X/156/10
15. Rytsar, B.Ye., 2016. “Simple Numeric Set-Theoretical Method of the Logic Differential Calculus”, Control Systems and Computers, 6, pp.12-23.
    https://doi.org/10.15407/usim.2016.06.012
16. Rytsar, B., Romanowski, P., Shvay, A., 2010. “Set-theoretical Constructions of Boolean Functions and theirs Applications in Logic Synthesis”, Fundamenta Informaticae, 99 (3), pp. 339-354.
    https://doi.org/10.3233/FI-2010-253
17. Rytsar, B., 2003. “Identification of symmetry of Boolean function decomposition cloning method”, Proc. 6thInter. Conf. on Telecom., TELSIKS 2003, Yugoslavia, Nis, pp.596–603.
18. Rytsar, B., 2015. “A new minimization method of logical functions in polynomial set-theoretical format. 1”, Generalized rules of conjuncterms simplification. Control Systems and Computers, 2, pp. 39–57. (In Russian).
19. Rytsar, B.Ye., 2013. “A nunerical Set-Theoretical  Interpretation of the Reed-Muller Expression with Fixed and Mixed polarity”, Control Systems and Computers, 3, pp. 30–50. (In Russian).
20. Yang, S., 1991. Logic synthesis and optimization benchmarks user guide – version 3.0. Microelectronics Center of North Carolina, Research Triangle Park, NC.
21. Kravets, V.N., Sakallah, K.A., Generalized Symmetries in Boolean Functions, eecs.umich.edu.
22. Kaeslin, H., 2008. “Digital Integrated Circuit Design From VLSI Architectures to CMOS Fabrication”, Cambridge University Press, pp. 741.
    https://doi.org/10.1017/CBO9780511805172

 Received  22.07.2019