SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Belarusian National Technical University
2016-03-01
|
| Series: | Системный анализ и прикладная информатика |
| Subjects: | |
| Online Access: | https://sapi.bntu.by/jour/article/view/92 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832557326807072768 |
|---|---|
| author | A. V. Sokolov O. N. Zhdanov O. A. Ayvazian |
| author_facet | A. V. Sokolov O. N. Zhdanov O. A. Ayvazian |
| author_sort | A. V. Sokolov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-ab8d428c88bf46eb85c5febdb37f1eb2 |
| institution | Kabale University |
| issn | 2309-4923 2414-0481 |
| language | English |
| publishDate | 2016-03-01 |
| publisher | Belarusian National Technical University |
| record_format | Article |
| series | Системный анализ и прикладная информатика |
| spelling | doaj-art-ab8d428c88bf46eb85c5febdb37f1eb22025-02-03T05:16:55ZengBelarusian National Technical UniversityСистемный анализ и прикладная информатика2309-49232414-04812016-03-0101697683SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONSA. V. Sokolov0O. N. Zhdanov1O. A. Ayvazian2Odessa National Polytechnic UniversitySiberian State Aerospace UniversityOdessa National Polytechnic UniversityThe 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.https://sapi.bntu.by/jour/article/view/92algebraic normal form, many-valued logic, reed-muller transform |
| spellingShingle | A. V. Sokolov O. N. Zhdanov O. A. Ayvazian SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS Системный анализ и прикладная информатика algebraic normal form, many-valued logic, reed-muller transform |
| title | SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS |
| title_full | SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS |
| title_fullStr | SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS |
| title_full_unstemmed | SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS |
| title_short | SYNTHESIS METHODS OF ALGEBRAIC NORMAL FORM OF MANY-VALUED LOGIC FUNCTIONS |
| title_sort | synthesis methods of algebraic normal form of many valued logic functions |
| topic | algebraic normal form, many-valued logic, reed-muller transform |
| url | https://sapi.bntu.by/jour/article/view/92 |
| work_keys_str_mv | AT avsokolov synthesismethodsofalgebraicnormalformofmanyvaluedlogicfunctions AT onzhdanov synthesismethodsofalgebraicnormalformofmanyvaluedlogicfunctions AT oaayvazian synthesismethodsofalgebraicnormalformofmanyvaluedlogicfunctions |