-

Methods of nulling numbers in the system of residual classes

V. N. Karazin Kharkiv National University

Svobody sq.

Kharkiv

Ukraine v.a.krasnobaev@gmail.com

kuznetsova.tatiana

@gmail.com

dr.smirnovoa@gmail.com 0 Central Ukrainian National Technical University , avenue University, 8, Kropivnitskiy, 25006 , Ukraine 1 Poltava National Technical Yuri Kondratyuk University , Poltava , Ukraine

The article presents the nullification of numbers in the system of residual classes (SRC). This method is widely used in the non-positional number system in the SRC with the need to determine positional characteristics. Two methods of nullification are presented in the article: the method of successive subtractions and the method of parallel subtractions. Based on these methods, algorithms are developed for their implementation. The essence of the method of successive subtractions is that the nullification procedure is carried out consequently from the junior foundation to the oldest. The essence of the parallel subtraction method is that the nullification procedure is carried out parallel in time for two reasons. It is advisable to use these methods in the implementation of operations of comparing numbers in the SRC, and in monitoring data presented in the SRC. The estimation of these methods by the number of equipment and by the time of implementation of the nullification procedure is made. In terms of the efficiency of the nullification procedure, a parallel subtraction method was proposed.

Methods of data control in the system of residual classes based on the principle of nulling One of the methods for determining the correctness of a number is the nulling (nullification) method, which consists in the transition from the initial number.

A  (a1, a2 , ..., an , an1) ( 1 ) to the number:

AZ  (0, 0, ..., 0, n1) ( 2 ) with the help of such a sequence of transformations in which there is no output outside the working range of the system of residual classes (SRC) [1-8].

The process of nulling a number consists in successively subtracting from this number the nulling constants of the form: (m1.1, m1.2 , ..., mn1) , where m1.1  (1, 2, ..., m1 1) ; (0, m2.2 , ..., mn1,2 ) , where m2.2  (1, 2, ..., m2 1) .

In this case, the number A  (a1, a2 , ..., an , an1) is sequentially converted to a form A  (0, a2 , ..., an , an1) , then to a number A  (0, 0, ..., an, an1) etc.

By repeating the process n times, we get:

A(Z )  (0, 0, ..., 0,  n1) .

If  n1  0 , then the original number is correct and lies in the range [0, M ) , if  n1  0 , then the number is incorrect and lies in the range [ jM , ( j 1)M ) , for j  (1, 2, ..., mn1 1) , where ( j 1) is the value of the number of the interval in which the operand A falls.

We show that an error A can transfer the correct number A , lying in the interval [0, M ) , only in one of the two intervals.

We write A  A  A , i.e.

A  (a1, a2 , ..., an , an1)  (0, 0, ..., ai , ..., 1) . ( 3 )

Obviously, A is not in the first (working) interval [0, M ) , since the first interval contains the correct number:

Let A be in the k -th interval: We write the system of two inequalities: Add up the two inequalities:

A0  (0, 0, ..., 0, 0) . (k 1)M  A  kM . 0  A  M ,  (k 1)M  A  kM .

(k 1)M  A  A  (k 1)M .

Let j  k 1 , then we can write: jM

 A  ( j  2)M , i.e. an error may cause the correct operand to be incorrect, lying only in one of two intervals [ jM , ( j  1)M ) or [( j 1)M , ( j  2)M ) . 2

Method of successive subtractions

Consider the nulling procedure in terms of the time of its implementation. The e ssence of the first (Z1), the basic in the theory of SRC, nullification procedure (the procedure of sequential nullification (SN)) consists of a sequence of operations for subtracting in form: by means of a set of NC of the form ( 5 ):

For example: performing the first subtraction operation: ... || an(0)3 || an(0)2 || an(0)1 || an(0) || an(0)1 ]  [t1(0) || t 2(0) || t3(0) || ( 4 ) ( 5 ) performing the second subtraction: || [a(0)  t (0) ] mod m 3 3 3

with the help of a sequence of operations that does not result in the output of the numerical value of the number А(0) range [0, M) of the

SRC.

In this case, the over the working initial A( 3 )  (0, 0, 0, a4( 3 ) , ..., an( 3 ) , an(3)1 ) and so on. By repeating the subtraction n times, we get the value A(Z )  (0 || 0 || ... || 0 || an(n)1 ) , or A(Z )  (0 || 0 || ... || 0 ||  n1 ) , where  n1  an(n)1 . The SN procedure is shown in Fig. 1. [a(0)  t(0) ] mod m3 || ...

3 3 3 4 5 6

[a(0)  t (0) ] mod m i 1 i 1 [a(0) n3 || ... [a( 2 )  t ( 2 ) ] mod m n1 n1 n1   7 8 For value A(i ) the value of the remainder a ( 3 ) 4 of a || ...

[a( 3 ) n3  t ( 3 ) ] mod m n3 n3 || [a( 3 ) n2  t ( 3 ) ] mod m n2 n2 [a( 3 ) n1  t ( 3 ) ] mod m n1 n1 || [a( 3 )  t ( 3 ) ] mod m n n n || [a( 3 ) n1  t ( 3 ) ] mod m n1 n1   [0 || 0 || 0 || 0 || a( 4 ) || 5 || a( 4 ) || a( 4 ) || a( 4 ) || i1 i i1 ...

a( 4 ) || a( 4 ) || a( 4 ) n3 n2 n1 a( 4 ) || a( 4 ) ] .

n n1

Appeal by the

value

0 0 || an(n12) || an(n2) || an(n12)] in BNCn2 for the NC Performing a subtraction operation A(n1)  A(n2)  NC(n2)  [0 || 0 || 0 | 2n ...|| 0 || 0 || 0 || tn(n1) || tn(n11)] 0 || 0 0 ...|| 0 0 || 0 ||... 0 0 0 ||[an(n1) tn(n1)]modmn [an(n11) tn(n11)]modmn1 [0|| 0|| 0|| || 0|| 0|| 0|| ... 0 || 0 || 0 0 an(n)1] , где an(n)1   n1.

TZ1  2n add

Denoting the sampling time of the NC from the corresponding nullification block (NB) of the CS functioning in the SRC as t1, and the time of subtracting from the number А(i-1) the constant NC(i-1), i.e. performing the operation А(i) = А(i-1)  NC(i-1) – as t2, we get the total time ТZ1 of the nullification procedure for the first Z1 method: ТZ1 = n (t1 + t2). ( 6 )

Parallel subtraction method

Consider the following method (Z3) of operational control of data in the SRC (parallel nullification method (PNM)). The essence of the proposed control method is that the nullification procedure is carried out parallel in time for two reasons. For n -even numbers, we have аі(i–1), an(ii1)1 ( i  1, n / 2 ), namely a1(0), an`(0); a2( 1 ), an–1( 1 ); a3( 2 ), an– 2( 2 );… an(n/2/2) , an( n/2)/21) (see Fig. 2). For n -odd numbers, we have a1(0), an(0); a2( 1 ), an–1( 1 ); a3( 2 ), an(2)2 ; … a((n1)/21) (see Fig. 3). In this case, for an arbitrary value i of NC for (n1)/2 the corresponding number, have the following form: A(i)  [0|| 0|| || 0|| ai(i)1 || a(i) ||... i2 izeroes izeroes ...|| a(i)

ni1 || an(i)i || 0|||| 0|| 0|| an(i)1 ] , . . .

a(i1) i ai(i11) . . .

an(2)1 For an arbitrary value i we have that:

A(i1)  A(i)  NC(i)  [0 || 0 || ... || 0 || ti(i)1 || ti(i)2 || ti(i)3 ||

|| tn(i)i2 || tn(i)i1 || tn(i)1 || 0 ... 0 || tn(i)1 ]  ... 0 [a(i)  t (i) ] mod m i1 i1 i1 ... . . . . . .

The algorithm for performing the PNM procedure is presented in Table. 2. Before getting the value  n1  a(n/ 2) for n - even number, we have that: n1 n/ 21zeroes n/ 21zeroes A(n/ 21) n A(Z )  A(n/2)  [0 || 0 || ... || 0 || ... || 0 || 0 ||  n1  an(n/12) ] . || 0 || t((n1)/ 21) ] ,

n1

. value and || ... ... value and value A(i )

A( 2 )  A( 1 )  NC ( 1 )  [0 || a( 1 ) || a( 1 ) || 2 3 || || ... value and Appeal by the value of the remainders and a (i 1) n i 1 value A(i 1) n 1

A(i)  A(i 1)  NC (i 1)  [0 || 0 || 0 || ... ... 0 || || ... value and a(i ) ni ... Further for n even n odd numbers we get: for n even number. Appeal by the value of the remainders a ( n / 21) n / 2 and a ( n / 21) n / 21 of a number A(n/ 21)  [0 || 0 ||

For n odd number.

value of the

remainder in ((n1)/ 21) || 0 (n1)/ 2

odd numbers, we obtain the following values of the ... 0 a(n/ 2)  , where n1  n  n1

... 0 || [a((n1)/ 21)  t ((n1)/ 21) ] mod m n1 n1 n1

  [0 || 0 || ... where  n1  a((n1)/ 2) .

n1 0 ...

0 0 || a((n1)/ 2) ] ,

n1 T

Z 3

 n 

The time ТZ3 for performing the zeroing procedure for the first (Z3) method of the PNM is defined as:  n   2  i 1

When implementing the nullification procedure for the second (Z3) method in the block of nullification constants (NB) of the calculator in the SRC, it is necessary to have K

Z 3   (m  m i

 1) nullification constants. In this case, the number of NZ3 double digits

Conclusions

It is advisable to use these methods in the implementation of operations of comparing numbers in the SRC, and in monitoring data presented in the SRC [9-13]. The estimation of these methods by the number of equipment and by the time of implementation of the nullification procedure is made. In terms of the efficiency of the nullification procedure, a parallel subtraction method was proposed.

The obtained research results can be useful for various methods of increasing the reliability and fault tolerance of computer systems [14-18]. 7. V. Krasnobayev, A. Kuznetsov, M. Zub, K. Kuznetsova. Methods for comparing numbers in non-positional notation of residual classes. In Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (CMIS-2019), Zaporizhzhia, Ukraine, April 15-19, 2019., pp. 581–595. 2019. 8. V. Krasnobayev, A. Kuznetsov, I. Lokotkova and A. Dyachenko, "The Method of Single Errors Correction in the Residue Class," 2019 3rd International Conference on Advanced Information and Communications Technologies (AICT), Lviv, Ukraine, 2019, pp. 125-128. doi: 10.1109/AIACT.2019.8847845 9. E. Dubrova, "Fault-Tolerant Design: An Introduction" course notes, Royal Institute of

Technology, Stockholm, Sweden, 2013, 147 p. https://pld.ttu.ee/IAF0530/draft.pdf 10. V. Krasnobaev, A. Kuznetsov, V. Babenko, M. Denysenko, M. Zub and V. Hryhorenko, "The Method of Raising Numbers, Represented in the System of Residual Classes to an Arbitrary Power of a Natural Number," 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON), Lviv, Ukraine, 2019, pp. 1133-1138. doi: 10.1109/UKRCON.2019.8879793 11. M. Radu, "Reliability and fault tolerance analysis of FPGA platforms," IEEE Long Island Systems, Applications and Technology (LISAT) Conference 2014, Farmingdale, NY, 2014, pp. 1-4. 12. A. Yanko, S. Koshman and V. Krasnobayev, "Algorithms of data processing in the residual classes system," 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 117-121. 13. V.A. Krasnobayev, A.S. Yanko, S.A. Koshman. “A Method for arithmetic comparison of data represented in a residue number system” Cybernetics and Systems Analysis, vol. 52, issue 1, pp. 145-150, January 2016. DOI: 10.1007/s10559-016-9809-2 14. S. Shu, Y. Wang and Y. Wang, "A research of architecture-based reliability with fault propagation for software-intensive systems," 2016 Annual Reliability and Maintainability Symposium (RAMS), Tucson, AZ, 2016, pp. 1-6. 15. S. S. Gokhale, M. R. Lyu and K. S. Trivedi, "Reliability simulation of component-based software systems," Proceedings Ninth International Symposium on Software Reliability Engineering (Cat. No.98TB100257), Paderborn, Germany, 1998, pp. 192-201. 16. A. Tiwari, Karen Tomko "Enhanced Reliability of Finite State Machines in FPGA Through efficient Fault Detection and Correction", IEEE Transaction on Reliability, vol. 54, nr.3, pp. 459-467. 17. C. M. Reddy and N. Nalini, "FT2R2Cloud: Fault tolerance using time-out and retransmission of requests for cloud applications," 2014 International Conference on Advances in Electronics Computers and Communications, Bangalore, 2014, pp. 1-4. 18. C. Braun and H. Wunderlich, "Algorithm-based fault tolerance for many-core architectures," 2010 15th IEEE European Test Symposium, Praha, 2010, pp. 253-253.

D. I.

Popov and

A. V.

Gapochkin , "Development of Algorithm for Control and Correction of Errors of Digital Signals, Represented in System of Residual Classes," 2018 International Russian Automation Conference (RusAutoCon) , Sochi, 2018 , pp. 1 - 3 .

Y. N.

Kocherov ,

D. V.

Samoylenko and A. I. Koldaev , "Development of an Antinoise Method of Data Sharing Based on the Application of a Two-Step-Up System of Residual Classes," 2018 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon) , Vladivostok, 2018 , pp. 1 - 5 .

3. Krasnobayev

, Kuznetsov

, Koshman

, Moroz

( 2019 ) Improved Method of Determining the Alternative Set of Numbers in Residue Number System . In: Chertov O., Mylovanov

, Kondratenko

, Kacprzyk

, Kreinovich

, Stefanuk

. (eds) Recent Developments in Data Science and Intelligent Analysis of Information . ICDSIAI 2018. Advances in Intelligent Systems and Computing , vol 836 . Springer, Cham, pp. 319 - 328 , 05 August 2018 . DOI: 10 .1007/978-3- 319 -97885-7_ 31

Kasianchuk , I. Yakymenko , I. Pazdriy ,

Melnyk and

Ivasiev , "Rabin's modified method of encryption using various forms of system of residual classes," 2017 14th International Conference The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM) , Lviv , 2017 , pp. 222 - 224 .

Krasnobayev ,

Kuznetsov ,

Kononchenko ,

Kuznetsova . Method of data control in the residue classes . In Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (CMIS-2019) , Zaporizhzhia, Ukraine, April 15-19 , 2019 ., pp. 241 - 252 . 2019 .

Kasianchuk , I. Yakymenko ,

Pazdriy and

Zastavnyy , "Algorithms of findings of perfect shape modules of remaining classes system," The Experience of Designing and Application of CAD Systems in Microelectronics, Lviv , 2015 , pp. 316 - 318 .