SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS
Abstract
The rapid development of methods of error-correcting coding, cryptography, and signal synthesis theory based on the principles of many-valued logic determines the need for a more detailed study of the forms of representation of functions of many-valued logic. In particular the algebraic normal form of Boolean functions, also known as Zhegalkin polynomial, that well describe many of the cryptographic properties of Boolean functions is widely used. In this article, we formalized the notion of algebraic normal form for many-valued logic functions. We developed a fast method of synthesis of algebraic normal form of 3-functions and 5-functions that work similarly to the Reed-Muller transform for Boolean functions: on the basis of recurrently synthesized transform matrices. We propose the hypothesis, which determines the rules of the synthesis of these matrices for the transformation from the truth table to the coefficients of the algebraic normal form and the inverse transform for any given number of variables of 3-functions or 5-functions. The article also introduces the definition of algebraic degree of nonlinearity of the functions of many-valued logic and the S-box, based on the principles of many-valued logic. Thus, the methods of synthesis of algebraic normal form of 3-functions applied to the known construction of recurrent synthesis of S-boxes of length N = 3k, whereby their algebraic degrees of nonlinearity are computed. The results could be the basis for further theoretical research and practical applications such as: the development of new cryptographic primitives, error-correcting codes, algorithms of data compression, signal structures, and algorithms of block and stream encryption, all based on the perspective principles of many-valued logic. In addition, the fast method of synthesis of algebraic normal form of many-valued logic functions is the basis for their software and hardware implementation.
About the Authors
A. V. Sokolov
Odessa National Polytechnic University
Ukraine
Doctor of Engineering, Senior Lecturer
Ukraine
Doctor of Engineering, Senior Lecturer
O. N. Zhdanov
Siberian State Aerospace University
Russian Federation
Russian Federation
Associate Professor, PhD in Engineering
O. A. Ayvazian
Odessa National Polytechnic University
Ukraine
Graduate student
Ukraine
Graduate student
References
1. Mazurkov, M. I. On the effect of the type of orthogonal transform on PAPR of signal spectrum in CDMA systems /M. I. Mazurkov, A. V. Sokolov, N. A. Barabanov. – Іnformatika ta matematichnі metodi v modeljuvannі, 2015. – Vol. 5, № 1. – P. 28–37.
2. Falkowski, B. J. Application of Sign Hadamard¬Haar Transform in Ternary Communication System / B. J. Falkowski, S. Yan. – International Journal of Electronics, 1995. – Vol. 79(5). – P. 551–559.
3. Kuznecov, V. S. Trinity concatenated codes with QAM¬9 and their capabilities / V. S. Kuznecov. – «Info¬Jelektrosvjaz», 2009. – P. 30–33.
4. Mazurkov, M. I. Broadband radio systems / M. I. Mazurkov. – Odessa: Nauka i Tehnika, 2010, p. 340. – ISBN 978¬ 966¬8335¬95¬2.
5. Petelin, Ju. V. Perspectives of using of signal¬code structures such as ternary M¬sequences in the satellite communication channels / Ju. V. Petelin, M. A. Kovalev, A. A. Makarov // Informacionno¬upravljajushhie sistemy. – 2006. – №. 5. – P. 32–35.
6. Zhdanov, O. N. Algorithm of construction of optimal according to criterion of zero correlation nonbinary S¬boxes / N. Zhdanov, A. V. Sokolov. – Problems of physics, mathematics and technics, 2015. – № 3(24). – P. 94–97.
7. Logachev, O. A. Boolean functions in coding theory and cryptology / O. A. Logachev, A. A. Sal’nikov, V. V. Jashhen¬ ko. – M: Izdatel’stvo MCNMO. – 2004. – 472 p.
8. Qingshu, Meng A novel algorithm enumerating bent functions / Qingshu Meng, Min Yang, Huanguo Zhang, Jingsong Cui // Discrete Mathematics, 2008. – Volume 308, Issue 23. – P. 5576–5584.
9. MacWilliams, F. J. Theory of Error-Correcting Codes / F. J. MacWilliams, N. J. A. Sloane. – M.: Svjaz’, 1979. – p. 745.
10. Mazurkov, M. I. The key sequences generator based on bent functions dual couples / M. I. Mazurkov, N. A. Barabanov, A. V. Sokolov. – Works of the Odessa polytechnic university. – Vol. 3 (42). – P. 150–156.
11. Zhegalkin, I. I. Arithmetization of symbolic logic / I. I. Zhegalkin. – Matem. sb., 1929. – P. 305–338.
12. Rostovcev, A. G. Cryptography and Data Protection / A. G. Rostovcev. – SPb.: Mir i Sem’ja. – 2002.
13. Kormen, T. Construction and analysis of algorithms / T. Kormen, Ch. Lejzerson, R. Rivest, K. Shtajn, – M.: Vil’jams, 2006. – p. 1328.
14. Sokolov, A. V. New methods of the synthesis of non-linear transforms of modern ciphers / A. V. Sokolov. – Lap Lambert Academic Publishing, Germany, 2015. – p. 100.
Review
For citations:
Sokolov A.V., Zhdanov O.N., Ayvazian O.A. SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS. «System analysis and applied information science». 2016;(1):69-76. (In Russ.)
Views:
1963
Email this article 