ABSTRACT
An algorithm of digital logarithm calculation for the Galois field G F ( 257 ) is proposed. It is shown that this field is coupled with one of the most important existing standards that uses a digital representation of the signal through 256 levels. It is shown that for this case it is advisable to use the specifics of quasi-Mersenne prime numbers, representable in the form p = 2 n + 1 , which includes the number 257. For fields G F ( 2 n + 1 ) , an alternating encoding can be used, in which non-zero elements of the field are displayed through binary characters corresponding to the numbers + 1 and - 1. In such an encoding, multiplying a field element by 2 is reduced to a quasi-cyclic permutation of binary symbols (the permuted symbol changes sign). Proposed approach makes it possible to significantly simplify the design of computing devices for calculation of digital logarithm and multiplication of numbers modulo 257. A concrete scheme of a device for digital logarithm calculation in this field is presented. It is also shown that this circuit can be equipped with a universal adder modulo an arbitrary number, which makes it possible to implement any operations in the field under consideration. It is shown that proposed digital algorithm can also be used to reduce 256-valued logic operations to algebraic form. It is shown that the proposed approach is of significant interest for the development of UAV on-board computers operating as part of a group.
ABSTRACT
It is shown that in order to increase the efficiency of using methods of abstract algebra in modern information technologies, it is important to establish an explicit connection between operations corresponding to various varieties of multivalued logics and algebraic operations. For multivalued logics, the number of variables in which is equal to a prime number, such a connection is naturally established through explicit algebraic expressions in Galois fields. It is possible to define an algebraic δ-function, which allows you to reduce any truth table to an algebraic expression, for the case when the number of values accepted by a multivalued logic variable is equal to an integer power of a prime number. In this paper, we show that the algebraic δ-function can also be defined for the case when the number of values taken by a multivalued logic variable is p - 1, where p is a prime number. This function also allows to reduce logical operations to algebraic expressions. Specific examples of the constructiveness of the proposed approach are presented, as well as electronic circuits that experimentally prove its adequacy.
ABSTRACT
An alternating representation of integers in binary form is proposed, in which the numbers -1 and +1 are used instead of zeros and ones. It is shown that such a representation creates considerable convenience for multiplication numbers modulo p = 2n+1. For such numbers, it is possible to implement a multiplication algorithm modulo p, similar to the multiplication algorithm modulo the Mersenne number. It is shown that for such numbers a simple algorithm for digital logarithm calculations may be proposed. This algorithm allows, among other things, to reduce the multiplication operation modulo a prime number p = 2n+1 to an addition operation.
Subject(s)
Algorithms , Signal Processing, Computer-AssistedABSTRACT
Multivalued logics are becoming one of the most important tools of information technology. They are in great demand for creation of artificial intelligence systems that are close to human intelligence, since the functioning of the latter cannot be reduced to the operations of binary logic. At the same time, the problem of improving the efficiency of using the results of research in multivalued logics, as well as the problem of interpreting variables of multivalued logic, is acute. These problems create certain interdisciplinary barriers and make it difficult to implement the results of research in the field of multivalued logics in other fields of knowledge. It is shown that the problem of interpreting multivalued logic variables can be removed by establishing correspondence with fuzzy logic variables. Improving the efficiency of using of operations of multivalued logics and their variables can be provided by using their close connection to Galois fields. This connection, among other things, makes it possible to reduce any operations of multivalued logics, the number of variables in which is equal to a prime number, to algebraic functions whose arguments take values in Galois fields. This allows, among other things, to eliminate the very cumbersome constructions used in works on multivalued logic and make its apparatus convenient for use in related scientific disciplines in information technology. Direct verification of the adequacy of algorithms based on the use of Galois fields can be carried out by means of radio-electronic circuits, examples of which are presented in the present paper.
