Methods for comparing numbers in non-positional notation of residual classes

Abstract

Methods for optimizing computations in computer systems and components that are based on the use of arithmetic transformations in the system of residual classes are considered. Methods of comparing numbers in the system of residual classes based on the representation and processing of data without directly converting the compared numbers from a modular code to a positional code and back are investigated. Some methods are based on the principle of obtaining and comparing a unitary single-row code. Based on the proposed methods, algorithms for their implementation have been developed, in accordance with which a class of patentable devices has been developed for performing arithmetic and algebraic comparison of numbers in the system of residual classes.

Keywords

• Non-positional number system class of residues arithmetic nonpositional coding computer systems and components

-

It is known that the use of non-positional number system in residual classes (RCS) significantly increases the reliability and performance of the computer system (CS) [1-8]. However, the need to determine the positional characteristics of numbers in the RCS reduces the overall effectiveness of the use of modular codes. Existing methods for processing positional data, in particular, methods for comparing numbers into RCS, have significant drawbacks, the main of which is the need to convert numbers from RCS to positional number system and vice versa, which reduces user productivity and reliability of CS [9-12].

In the article there are four methods for comparing numbers into RCS, based on the presentation and processing of data without directly converting the compared numbers from a modular code (an RCS code) into a positional code and backward.

Methods for arithmetic comparison of numbers in RCS Let the RCS be given by ordered (mi < mi+1) mutually n pairs by simple natural numbers (bases) m1, m2, …, mn, d let the compared operands be represented as:

A= (a1, a2, …, an), B = (b1, b2, …, bn).

In the case, it is assumed that the source operands lie in the appropriate intervals:  ,  and  j2M , ( j2  1)M  ,  j1M ( j1  1)M   mn mn   mn mn  n where M   m1 , and the interval's number jk 1 is determined by the well-known i1 expression jk   nmn (mod mn ) , where the value of mn is determined from the comparison solution mn M / mn  l(mod mn ) . When j1 ≠ j2 the operation of arithmetic comparison can be implemented by comparing the number of intervals, namely: if j1 < j2, then A < B, if j1 > j2, then A > B. When j1 = j2 is determined by the number 0  j3  ( mn 1 ) / 2 , then A < B, and if mn  1

 j3  m , then A > B.

2

The well-known [1] method of arithmetic comparison of numbers with RCS involves the conversion of numbers and type A( H )  ( 0,0,..., n ) , which requires n 1 clock cycles of the null operation. In addition, it is necessary to make a positional comparison of the (j1 + 1) and (j2 + 1) intervals of the source operands A and B. All of this complicates the comparison algorithm and increases the comparison time of numbers, which leads to the need to develop a comparison method for RCS, which do not require determination of positional characteristics. Consider each of these methods. 2.1

The method of arithmetic comparison of numbers in the RCS (the method of arithmetic parallel subtraction) We will consider comparable numbers in arbitrary intervals:  jmi , ( j 1)mi  , where    n  j  1, N 1 N   mk  .

 kk li 

In the case, the source operands A, B are reduced to numbers that are multiples to mi , by modular subtraction of the following form:

Am  A  ai  ( a1( i ) ,a2(i ) ,...,ai(i1) ,0,ai(i1) ,...,an(i ) ,

i Bm  B  bi  ( b1( i ) ,b2(i ) ,...,bi(i1) ,0,bi1 ,...,bn(i ) ,

( i ) i ai  ( a1 ,a2 , ..., ai ,an ) , bi  ( b1,b2 , ..., bi , bn ) . where lows ( 1 ):

Further, by means of a set of constants 0, mi , 2mi , ..., ( N 1)mi , represented by ( n 1) -у base of the RCS m1 , m2 , ..., mi1 , mi1 , ..., mn , the construction of the socalled single-row code, respectively, in the form

K(NnA )  { zN zN 1...z2 z1 } , znA  0 ( z1  1;1  1, N ,1  nA ) ,

K(NnB )  { zN zN 1...z2 z1 } , znB  0 ( z1  1,1  1, N ,1  nB ) .

The algorithm for constructing a single-row code in RCS can be represented as fol Am  0  z1 ,  i  Ami  mi  z2 ,   Ami  2mi  z3 , z  0 , at Bm  nB  mi  0; z  1 , at Bm  nB  mi . nB i nB i ( 1 ) Geometrically, this number comparison method can be explained as follows. The  n  interval 0,  mi  is divided into segments. The source operands A и B, by subtract i1  ing the constants of the form n1  m , с and shift to the left edge of their hit interval.  1  i This is the equivalent to bringing the compared numbers to numbers, which are compile to comparison mi of the RCS. On this basis, the accuracy W с and comparison of the operands depends on the size of the base mi , that is W  W ( mi ) . However, with the maximum accuracy of the comparison Wmax  W ( mmin ) (for an ordered of the RCS Wmax  W ( m1 ) the number of equipment for technical devices realizing the comparison operation in the RCS increases dramatically. Indeed, the number of equipment N0 of the comparison device in the RCS significantly depends on the number of address N1, performing the operation of parallel subtraction:

In this way, necessity of ensure a high degree of accuracy of comparison requires a significant amount of equipment, which reduces the efficiency of using existing methods of comparing numbers in the RCS. This situation determines the relevance and importance of finding more effective methods of comparing numbers in the RCS, ensuring a high accuracy of W comparison with a minimum numbers N0 of equipment comparing devices.

In general, the task is interpreted as follows. It is necessary to find N0  min at Wmax, i.e. N0(Wmax )  min . As shown above Wmax  W ( m1 ) . In this case, a change in the base mi ( i  1,n ) affects only the number N1 of the equipment of the group of adders. In this case, the problem is correctly formulated as a definition ( 2 ) N1(Wmax )  min . ( 2 )

Obviously, with high accuracy equal to the unit length of the interval, Wmax  W ( mi  2 ) . However, in this case N1(Wmax )  max , и and this result does not satisfy the condition ( 2 ). On the other hand – N1(Wmin )  min . Thus, it is necessary to develop such a method of comparison ( 2 ). This problem is solved by the method described below. 2.2

The method of arithmetic comparison of numbers in the RCS (the method of parallel subtraction with the comparison of residues) We introduce an additional operation of comparing the residues an and bn the magnitude of the bases mn of the RCS. In this case, the result of the comparison of the residuals simultaneously with the result of the comparison of the single-row code K (NnA ) and K (NnB ) , is determined by the solution of the problem ( 2 ), i.e. Wmax and with the minimum amount of equipment Nmin is the result of solving the operation of if nA  nB , then A  B;  if nA  nB , then A  B; if nA  nB , and at the same time  an  bn , at A  B,

 an  bn , at A  B,  an  bn , at A  B.

The set of relations ( 3 ) represents the general algorithm for the implementation of the operation of arithmetic comparison of numbers in the RCS. It is advisable to consider examples of specific performance of the operation of arithmetic comparison of numbers in the RCS. Let the RCS be given by bases, m1  2, m2  3 and m3  5 . Code words are given in Table 1. In Table 2 given constants an (bn) presented in a given RCS, and in Table 3, constants of a single-row code are   mn  n1    0,  m  mi on the basis of the RCS ( i  1,n 1) .  i1 i  comparing two numbers in RCS. The algorithm for determining the result of an arithmetic comparison operation can be represented as follows: B21  ( 1,00,001 ) . In this case, the values of the constants (Table 2) determine the values Amn  A23  an  ( 0,10,000 ) , Bmn  B21  bn  ( 01,00,000 ) , which corresponds to the shift of the operands A and B to the left edge of the interval [20, 25). Then we use the constants of the single-row code (Table 3), we determine the singlerow code for the input numbers in the form:

K (NnA )  K( 4 )  {110111} ; K (NnB )  K( nB )  K( 4 )  {110111} ,

6 6 6 where

n1 N1   mi  6 .

i1

At the same time the comparison result an  011  bn  001 is determined in parallel with the ( n  [log2( mn 1 )]  1 )-th bit comparison circuit in time. So, if nA  nB  4 , in accordance with the above algorithm, we determine that A23  B21 . ( 0  N 1) mn 0  m3  0 1 m3  5 2  m3  10 3  m3  15 4  m3  20 5  m3  25 B3  ( 1,00,011 ) . In this case, the following differences are determined from the values of the constants (Table 2):

Amn  A23  an  ( 0,10,00 ) and Bmn  B3  bn  ( 1,00,000 ) , which corresponds to the shift of the operand А23 to the left edge of the interval [20, 25), and the operand B3 to the left edge of the interval [0, 5). Next, using the constants of the single-row code (Table 3), we determine the single-row code for the considered input operands A23 , and B3:

K (NnA )  K( 5 )  {101111} , K(NnB )  K ( 1 )  {111110 } .

6 6

So, if nA  5  nB  1 , in accordance with the above algorithm, we determine that A23  B3 . 2.3

The arithmetical method of comparison of numbers in the RCS (the method of comparison with a constant) Consider the method of implementing the operation of arithmetic comparison of numbers in the RCS. The essence of this method is that not the operands A and B, are directly compared, but the quantities   ( A  B ) mod M  ( 1 , 2 ,..., n ) and m1.

In this case, the value is determined:  m    1  ( 0, 2 , 3 , ..., n ) ,

1 where constants  1  ( 1 , 2 , 3 , ..., n ) and  1  ( a1  b1 ) mod m1 are represented in a given RCS.

Then the general algorithm for comparison of the operands is presented in the form:  A  B, at  m  m1;  1  A  B, at  m  m1;  1  A  B, at  m  0.  1 ( 4 ) By dialing constants  n  0, m1 , 2m1 , ..., ( N 1)  m1  N   mi  ,  i1  which were represented in the RCS with bases m2 , m3 , ..., mn , the construction of a single-row code in the form of:

K n(n )  { zN zN 1...z2 z1 } , where In addition

The first module m1 RCS is also represented by a single-row code of length N binary digits, in which the second place on the right will be zero ( m1 1 m1  0 ) , and on the rest - one, i.e. the single-row unitary code will be represented as: Kn( 2 )  {11...101} .

Further, by known methods, in accordance with algorithm ( 4 ), operands A and B, represented by a single-row code, are compared.

Example 3. For the above RCS we consider an example of the implementation of this method. Let the numbers be equal A  ( 0,01,010 ) and B  ( 1,10,011 ) . We define the value:   ( A  B ) mod M  ( 0 1) mod 2, ( 01 10 ) mod 3, ( 010  011 ) mod 5   ( 1,10,100 ).

By value  1  1 we define a constant in the form  1  ( 1,01,001 ) (Table 4). Then we perform the operation:  m     ( 00,01,011) .

1 The operand  m , which is a multiple of the module m1  2 value, goes to the 1 first inputs of the corresponding adders, the second inputs of which receive the corresponding constants (Table 5). Since  m1 14mi  0 , then the single-row code will take the form:

Kn(n )  K1(514 )  { 011111111111111} .

In accordance with algorithm ( 4 ), we determine that A < B.

The advantage of the considered method is to ensure maximum accuracy of comparison with an acceptable amount of equipment for its implementation. 2.4

The method of algebraic comparison of numbers in the RCS It is easy to go from the implementation of the operation of arithmetic comparison of numbers to the algebraic comparison of numbers. In this case, the compared numbers A and B have one additional significant digit, i.e. the number is accompanied by a indication  A( B ) of the sign signA( signB ) , where:

0, if A( B )  0,  A(  B )  

1, if A( B )  0.

In this way, the compared numbers are presented in the form:

A  (  A ; A )   A ;( a1,a2 ,...,an ) , and B  (  B ; B )   B ;( b1,b2 ,...,bn ) , and the method of comparing numbers A and B is determined by the set of operations ( 5 ).

We will conduct a comparative analysis of the implementation time of the comparison operation of two numbers А and В or the proposed method and the most wellknown. The essence of the known method is to convert the numbers А and В from the system of residual classes to the positional number system АПСС, ВПСС and the further comparison of the operands of АPNS и ВPNS. Moreover, the transfer of numbers from RCS to PNS is made in accordance with the expression:

n APNS   ai Bi

M , where ai  [ APNS / mi ]mi , where Bi – is the orthogonal basis over the mi base of the RCS. ( 5 )

For the known and proposed methods of comparing numbers, the implementation time is determined by the corresponding mathematical relations where  t( 11 ) – is the implementation time of the multiplication operation for the maximum mn by the magnitude of the RCS module (the implementation time of the multiplication operation of two-digit binary numbers K  [log2( mn 1)]  1 );  t( 12 ) – is the time ( n 1) of the th addition of two numbers of the type ai Bi  ai1Bi1( i  1,n 1) ;  t( 13 ) – is the time for determining the deduction of the number of АPNS (ВPNS);  t( 14 ) – is the comparison time of the positional operands of the АPNS and ВPNS;  t(21) – is the time of implementation of the operation of subtraction in the RCS

ACOK  ai ;  t(22) – is the time of implementation of the operation of subtraction in the RCS

Ami  k  mi ;  t(23) – is the time of comparison of two positional N-bit single-row unitary codes of two corresponding numbers.

It is known that the time of addition of tc and ty multiplication of two operands in the PNS is determined by the following relations:

tc   ( 2 1) and ty  2 2 ,0 where ρ is the bit width of the processed operands; τ – is the time of "shift" of one binary digit. In this case, the time of "triggering" of the logical element AND (OR) is determined by the expression: tAND  tOR   / 2 , and t( 23 )  6tn and expression   n  2 t( 13 )  2 log2   mi 1  1 .

  i1   TR(1C)S  t( 11 )  t( 12 )  t( 13 )  t( 14 ) ,

TR(C2S)  t( 21)  t( 22 )  t( 23 ) , ( 6 ) ( 7 ) ( 8 ) ( 9 )

Taking into account the above, relations ( 6 ) and ( 7 ), respectively, are presented in the form:   n  2 TR(1C)S  2 k 2  ( n 1) ( 2k 1)  2 log2   mi 1  1  3 ;

  i1  

TR( C2S)  2  2  3 .

According to with expressions ( 8 ) and ( 9 ), values are calculated TR(1C)S , TR(C2S) (table 6) for various l – byte bit CS grids ( l  1,4 ) . From Table 6 it can be seen that with increasing length of the CS discharge grid, which is typical of the current trend in the development of systems and tools for processing digital information, the effectiveness of applying the proposed methods for comparing numbers, as compared to existing ones, increases.

On the basis of the proposed methods, algorithms for their implementation have been developed, in accordance with which a class of patentable devices has been developed for performing arithmetic and algebraic comparisons of numbers in an RCS [13-15]. Prospective direction of a further research is the argumentation of practical recommendations concerning a realization of the introduced method and the ways of its use in different mechanisms of an information security of telecommunications networks and systems [16-31]. 3

Conclusion In this paper, a method is proposed for comparing numbers in a non-positional number system of remainder classes, which is based on the principle of obtaining and comparing a unitary single-row code.

The developed method can be used to improve advanced computer systems and their components. In particular, its practical use allows to increase the performance of computer calculations and the reliability of information systems. 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 101–104. (2017) doi:10.1109/INFOCOMMST.2017.8246359 19. Kuznetsov, A., Kiyan, A., Uvarova, A., Serhiienko, R., Smirnov, V.: New Code Based Fuzzy Extractor for Biometric Cryptography. In: 2018 International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkiv, Ukraine, 2018, pp. 119–124. (2018) doi:10.1109/INFOCOMMST.2018.8632040 20. Gorbenko, I., Kuznetsov, A., Tymchenko, V., Gorbenko, Y., Kachko, O.: Experimental Studies of the Modern Symmetric Stream Ciphers. In: 2018 International ScientificPractical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkiv, Ukraine, 2018, pp. 125–128. (2018) doi:10.1109/INFOCOMMST.2018.8632058 21. Eberhart, R.C., Shi, Y.: Tracking and optimizing dynamic systems with particle swarms.

In: Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546), Seoul, South Korea, 2001, pp. 94–100. (2001) doi:10.1109/CEC.2001.934376O 22. Ivanov, O., Ruzhentsev, V., Oliynykov, R.: Comparison of Modern Network Attacks on TLS Protocol. In: 2018 International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkiv, Ukraine, 2018, pp. 565– 570. (2018) doi:10.1109/INFOCOMMST.2018.8632026 23. Kandemir, M., Choudhary, A., Ramanujam, J., Kandaswamy, M.A.: A unified framework for optimizing locality, parallelism, and communication in out-of-core computations. IEEE Transactions on Parallel and Distributed Systems, 2000, vol. 11( 7 ), pp. 648–668. (2000) doi:10.1109/71.877759 24. Pousset, Y., Vauzelle, R., Combeau, P.: Optimising the computation time of radio coverage predictions for microcellular mobile systems. IEEE Proceedings - Microwaves, Antennas and Propagation, 2003, vol. 150( 5 ), pp. 360–364. (2003) doi:10.1049/ipmap:20030543 25. Xing, C., Wang, H.: Optimized similarity computation for nearest neighbor choosing.

In: Proceedings of 2012 2nd International Conference on Computer Science and Network Technology, Changchun, 2012, pp. 2011–2014. (2012) doi:10.1109/ICCSNT.2012.6526313 26. Munetomo, M., Bando, S.: A scalable infrastructure of interactive evolutionary computation to evolve services online with data. In: 2013 IEEE International Conference on Big Data, Silicon Valley, CA, 2013, pp. 28–28. (2013) doi:10.1109/BigData.2013.6691793 27. Kavun, S.: Conceptual fundamentals of a theory of mathematical interpretation. Int. J. Computing Science and Mathematics, 2015, vol. 6( 2 ), pp. 107–121. (2015) doi:10.1504/IJCSM.2015.069459 28. Kavun, S.: Indicative-geometric method for estimation of any business entity. Int. J. Data Analysis Techniques and Strategies, 2016, vol. 8( 2 ), pp. 87–107. (2016) doi: 10.1504/IJDATS.2016.077486 29. Kovtun, V., Kavun, S., Zyma, O.: Co-Z Divisor Addition Formulae in Homogeneous Representation in Jacobian of Genus 2 Hyperelliptic Curves over Binary Fields. International Journal Biomedical Soft Computing and Human Sciences, 2012, vol. 17( 2 ), pp. 37–43. (2012) doi:10.24466/ijbschs.17.2_37 30. Zamula, A., Kavun, S.: Complex systems modeling with intelligent control elements. Int.

J. Model. Simul. Sci. Comput., 2017, vol. 08(01). (2017) doi:10.1142/S179396231750009X 31. Kavun, S., Zamula, A., Mikheev, I.: Calculation of expense for local computer networks.

In: Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), 2017 4th International, Kharkiv, Ukraine, 2017, pp. 146–151. (2017) doi:10.1109/INFOCOMMST.2017.8246369

References

1. Shu , S. , Wang , Y. , Wang , Y. : A research of architecture-based reliability with fault propagation for software-intensive systems . In: 2016 Annual Reliability and Maintainability Symposium (RAMS) , Tucson, AZ , 2016 , pp. 1 - 6 . ( 2016 ) doi:10.1109/RAMS. 2016 .7447984

2. Gokhale , S.S. , Lyu , M.R. , Trivedi , K.S.: Reliability simulation of component-based software systems . In: Proceedings Ninth International Symposium on Software Reliability Engineering (Cat. No.98TB100257) , Paderborn, Germany, 1998 , pp. 192 - 201 . ( 1998 ) doi:10.1109/ISSRE. 1998 .730882

3. Tiwari , A. , Tomko , K. : Enhanced Reliability of Finite State Machines in FPGA Through Efficient Fault Detection and Correction . IEEE Transaction on Reliability , vol. 54 ( 3 ), pp. 459 - 467 . ( 2005 ) doi:10.1109/TR. 2005 .853438

4. Singh , C. , Sprintson , A. : Reliability assurance of cyber-physical power systems . In: IEEE PES General Meeting , Providence, RI, 2010 , pp. 1 - 6 . ( 2010 ) doi:10.1109/PES. 2010 .5590189

5. Krasnobayev , V.A. , Koshman , S.A. , Mavrina , V.A. : A Method for Increasing the Reliability of Verification of Data Represented in a Residue Number System . Cybernetics and Systems Analysis , 2014 , vol. 50 ( 6 ), pp. 969 - 976 . ( 2014 ) doi:10.1007/s10559-014-9688-3

6. Reddy , M. , Nalini , N.: FT2R2Cloud: Fault tolerance using time-out and retransmission of requests for cloud applications . In: 2014 International Conference on Advances in Electronics Computers and Communications , Bangalore, 2014 , pp. 1 - 4 . ( 2014 ) doi:10.1109/ICAECC. 2014 .7002396

7. Braun , C. , Wunderlich , H.: Algorithm-based fault tolerance for many-core architectures . In: 2010 15th IEEE European Test Symposium , Praha, 2010 , pp. 253 - 253 . ( 2010 ) doi:10.1109/ETSYM. 2010 .5512738

8. Radu , M. : Reliability and fault tolerance analysis of FPGA platforms . In: IEEE Long Island Systems, Applications and Technology (LISAT) Conference 2014 , Farmingdale, NY, 2014 , pp. 1 - 4 . ( 2014 ) doi:10.1109/LISAT. 2014 .6845211

9. Akushsky , I. , Yuditsky , D. : Machine arithmetic in residual classes . Moscow, Sov. Radio (in Russian) ( 1968 )

10. Torgashov , V.: System of residual classes and reliability of digital computers . Moscow, Sov. Radio (in Russian) ( 1973 )

11. Krasnobayev , V. , Kuznetsov , A. , Koshman , S. , Moroz , S. : Improved Method of Determining the Alternative Set of Numbers in Residue Number System . In: Recent Developments in Data Science and Intelligent Analysis of Information. ICDSIAI 2018. Advances in Intelligent Systems and Computing , Springer, Cham, 2018 , vol. 836 , pp. 319 - 328 . ( 2019 ) doi:10.1007/978-3- 319 -97885-7_ 31

12. Krasnobayev , V.A. , Yanko , A.S. , Koshman , S.A. : A Method for arithmetic comparison of data represented in a residue number system . Cybernetics and Systems Analysis , 2016 , vol. 52 ( 1 ), pp. 145 - 150 . ( 2016 ) doi:10.1007/s10559-016-9809-2

13. Patent for utility model No. 73379 , Ukraine , G 06F 7 /04. Device for the popular danich, which is presented in the classroom extra . No. u 2012 01885. Appl. 02 /20/2012. Publ. 09 /25/2012, Bull. No. 18

14. Patent for utility model No. 73384 , Ukraine , G 06F 7 /04. Device for the same number of numbers in the classroom too . No. u 2012 01916. Appl. 02 /20/2012. Publ. 09 /25/2012, Bull. No. 18

15. Patent for utility model No. 73407 , Ukraine , G 06F 7 /04. Device for algebraic porous numbers with class numbers No . U 2012 02150. Appl. February 24 , 2012 . Publ. 09 /25/2012, Bull. No. 18

16. Gorbenko , I.D. , Zamula , A.A. , Semenko , A.E. , Morozov , V.L. : Method for complex improvement of characteristics of orthogonal ensembles based on multiplicative combining of signals of different classes . Telecommunications and Radio Engineering , 2017 , vol. 76 ( 18 ), pp. 1581 - 1594 . ( 2017 ) doi:10.1615/TelecomRadEng.v76. i18 . 10

17. Si-ru , Z. : Application of Improved Genetic Algorithm in Optimization Computation . In: 2009 Fifth International Conference on Natural Computation, Tianjin , 2009 , pp. 144 - 148 . ( 2009 ) doi:10.1109/ICNC. 2009 .393

18. Gorbenko , I. , Zamula , A. , Morozov , V. : Methods for implementing communications in info-communication systems based on signal structures with specified properties . In: 2017