Method of Tabular Implementation for Diagnostics of Non- Positional Code Structures in the System of Residual Classes

Abstract

In the article is proposed a method of the tabular implementation of the procedure for diagnosing data that are presented in the system of residual class (SRC). It is shown that the main disadvantage of the existing methods for diagnosing data in SRC is the considerable time of diagnosing data. The method of the tabular implementation of the procedure for diagnosing data in the SRC presented in the article makes it possible to reduce the time of the diagnostic procedure. Compared with the known methods the data diagnosis time is reduced due to the following factors. Firstly, due to the exceptions of the procedure of converting numbers from the SRC to the positional binary numeral system, i.e. exceptions from the chain of operations of positional comparison of numbers. Secondly, the data diagnostics time is reduced on the decrease of the number of SRC bases which сan cause an error. Finally, thirdly, the data diagnostics time is reduced due to the use of a tabular sample of the value of an alternative set of numbers in the SRC, practically in one machine cycle. It is given a geometric interpretation of the proposed method of tabular implementation of the procedure for diagnosing data, which is presented in the SRC. Also, we gave the examples of using the proposed method for diagnosing data for a specific SRC. Thus, the proposed method makes it possible to reduce the time for diagnosing data errors presented in the SRC, which increases the efficiency of diagnosing non-positional code structures. Residue number system, non-positional code structure, tabular implementation.

1. Introduction

It is known that correcting codes in the system of residual class system (SRC) are a kind of arithmetic codes [1,2]. From the principle of constructing the correcting code in the SRC, its complete arithmetic is visible, the introduced control bases, in addition to the informational ones, are included in the general system of SRC bases [ 3,4 ]. Besides, the numbers contained in the residues of the information and control bases of the SRC are involved in any arithmetic operation [ 5–7 ]. The processing of information and control residues of numbers in the SRC is carried out equally, without any difference. This leads to the fact that data processing in the SRC can be carried out without monitoring each obtained intermediate result [ 8–10 ]. The value of the duration of the data control stage is determined in each individual case of calculations. The duration of the data control stage is determined either by the completed processing cycle of the data array, or in accordance with the calculated error probability. The reliability of the final result of calculations of each stage of the program confirms the correctness of all operations of this stage [ 6,11 ].

2022 Copyright for this paper by its authors.

We note that the introduction of only one control base in the non -positional code structure (NCS) in the SRC allows to detect not only any single error (an error in one of the residues of a number in the SRC), as well as in a positional numeral system (PNS) (an error in one of the binary digits of a number), but also most of the double ones [ 12–14 ].

A distinctive feature of the SRC, in contrast to the PNS, is a significant manifestation of primary information redundancy (primary information redundancy manifests i tself only due to the presence of SRC information bases) with the introduction of a secondary one (secondary information redundancy is manifested only due to the presence of SRC control bases) [ 15–17 ].

The specificity of the representation of numbers in the SRC allows in some cases not only to detect the fact of distortion of the NCS, but also to find the place of its occurrence (one specific residue of the NCS) using only one control base of the SRC. The presence of one control base provides the NCS in the SRC with the minimum code distance dmin  2 . This effect cannot be realized by the existing control methods in the PNS, for example, with control by modulus. It is possible to diagnose errors in the SRC with dmin  2 by the projection method, or by a method based on the use of the concept of an alternative set (AS) of numbers W ( A)  ml1 , ml2 ,..., ml  [ 6,13,18 ].

It is known that the projection method in the SRC requires the calculation of all projections Ai of the distorted number A , which leads to the execution of a large number of operations for each correction of the result. The hardware and especially the software implementation of the projection method is time consuming [ 19–22 ]. In addition, this method fundamentally doesn`t allow to unambiguously diagnose the place of occurrence of any single (the method doesn`t allow to unambiguously diagnose the distorted residue in the NCS) errors [ 3,23–25 ].

Thus, studies devoted to the development and improvement of fast (operational) methods for diagnosing data errors based on the use of the concept of AS numbers in SRC are important and relevant.

The purpose of the article is to develop a method for fast diagnostics of data in the SRC, using the concept of an alternative set of numbers W ( A)  ml1 , ml2 ,..., ml  in the SRC, with the using the minimum dmin  2 information-code redundancy in NCS

ASRC  (a1 || a2 || ... || ai1 || ai || ai1 || ... || an || an1) .

2. Diagnostics of Non-Positional Code Structures in the System of Residual

Classes

In the general case, the diagnosis of NCS in SRC is the process of detecting the location of the distorted residuals of the number. Alternative set of numbers W ( A)  ml1 , ml2 ,..., ml  consists of a set of SRC bases for which the residuals may be distorted.

The initial AS contains an excess amount of bases. The existence of an excessive number of bases in the AS leads to the need to involve and use additional time and hardware resources to implement the necessary stages of determining the intermediate AS. This circumstance, first of all, determines the significant time for diagnosing data in the SRC. Thus, in order to improve the efficiency of diagnosing the data presented in the SRC, it is necessary to get rid of some of the excess bases contained in the AS.

The essence of the proposed method for increasing the promptness of diagnosing data in the SRC is that the AS is determined not in the entire interval [ jM , ( j 1)M ) containing the wrong number ASRC , but only in a smaller numerical interval where ASRC(H )  (0 0 ... 0  n1) is the nullified number in the SRC.

The essence of the nullification methods in SRC is to move from an initial number to a number

ASRC  (a1 || a2 || ... || ai1 || ai || ai1 || ... || an || an1)

A(H )  (0 0 ... 0  n1) using a sequence of conversions in which there isn`t any coming out of intermediate number outside the working range 0  M  1 .

The essence of the nullification methods is to sequentially subtract from the initial number some minimal numbers CN(i) (i - the number of stages (iterations) of nullification) called constants of nullification (CN) such that the number ASRC is converted to a number A(H )  (0 0 ... 0  n1) , without the number value ASRC coming out of the numeric range [0, M ) .

Geometrically, the nullification operation corresponds to displacement of the original number

ASRC  (a1 || a2 || ... || ai1 || ai || ai1 || ... || an || an1) to the left edge j  M of the numerical interval [ jM , ( j 1)M ) of its finding.

Thus, to eliminate the redundancy of AS W ( A) , by reducing the length of the interval of finding the number proposed to determine the values and

ASRC , it is A(H )  ( A  A(H ) ) . According to the distribution of errors over the working range intervals [0, M ) , preliminarily for each interval [ jM , ( j 1)M ) is formed the two-input correspondence tables W ( A)  ( n1, A(H ) ) . In this case, AS W ( A) is not determined in the entire interval [ jM , ( j 1)M ) A(H )  (0 0 ... 0  n1) containing the wrong number A , but only in the numerical interval A(H ) . The developed method of operational diagnosis of the data presented in the SRC is shown in Fig. 1.

Making a two-entry (two-coordinate) table W (A)  ( n1, A(H ) )

from the contents of the AS values Determining the value  n1 , which is the first coordinate of the table W (A)  ( n1, A(H ) ) .

Conversion of an initial number

ASRC  (a1 || a2 || ... || ai1 || ai || ai1 || ... || an || an1) , by performing nullification into a number A(H )  (0 0 ... 0  n1) .

Defining the value A(H ) , which is the second coordinate of the correspondence table

A(H )  (0 0 ... 0  n1) .

Determining the subtraction A(H )  A  A (H ) .

Appealing to the two-entry correspondence table W (A)  ( n1, A(H ) ) according to the coordinate values  n1 and A(H ) .

Defining the AS values W (A)  ml1 , ml2 ,..., ml  of the wrong number

Let’s consider examples of the implementation of the proposed method of NCS diagnostics for SRC, given by bases m1  2, m2  3, m3  mn1  5 ;

M  2  3  6 ;

M0  2  3 5  30.

For a given SRC, Table 1 shows the code words in PNS and in SRC. m1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 m2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 3. Examples 3.1. Example 1

The number ASRC  (1 2 3) in the SRC is given. For the purpose of diagnostics (determining the location of the remnants of the number in the SRC, according to which distortions are possible) of the number ASRC  (1 2 3) , we define the AS like W ( A)  ml1 , ml2 ,..., ml  . For this, in accordance with the nullification procedure [1] the value A(H ) of the nullified number ASRC  (1 2 3) defined by using the constants of nullification CN (1) ( i  1, 2 ) (for i  1 , the data in Table 2 are used, and for i  2 , the data in Table 3 are used).

Initially, by means of the first constant of nullification CN (1)  (1 1 1) (Table 2), the first ( i  1 ) stage (first iteration) of nullification procedure is carried over the initial number ASRC  (1 2 3) in the form

ASRC - CN (1)  (1 2 3) - (1 1 1) = (0 1 2) .

To determine the final result A(H ) of nullification over the initial number ASRC  (1 2 3) , the second ( i  2 ) stage (second iteration) of the nullification procedure is carried out by means of the second nullification constant CN (2)  (0 1 4) (Table 3) for the obtained value (0 1 2) of the first result of the nullification procedure. Thus, we get that

A(H ) = (0 1 2) - CN (2)  (0 1 2) - (0 1 4) = (0 0 3) .

To get the value W ( A)  ( n1, A(H ) ) from table 4 the first coordinate  3  3 ( n1  3 ) is determined from the expression A(H ) = (0 0 3) . The second coordinate A(H ) is determined from the expression

A(H )  ( A  A(H ) )  (1 2 3) - (0 0 3) = (1 2 0) .

In the PNS the value of the second coordinate A

(H ) is equal to five, i.e. A(H ) = 5 (Table 1).

According to the obtained values (by two coordinates) A(H ) = 5 and  n1  3 in Table 4 we define the AS W ( A)  {m2 , m3} .

Considering that, for a given SRC, the maximum value of AS is equal toW ( A)  {m1, m2 , m3} , the following inequality is obvious W ( A)  {m2 , m3} .

Thus, the number of bases in the AS W ( A)  {m2 , m3} is reduced by 30% in comparison with the maximum possible W ( A)  {m1, m2 , m3}.

This circumstance makes possible to reduce the number of checks of the SRC bases for determining the location of distorted residues in the number ASRC  (1 2 3) , which reduces the time for diagnosing SRC, increasing the efficiency of diagnosing data in SRC. 3.2.

Example 2

Let it is necessary to define an alternative set W ( A)  {ml1 , ml2 ,..., ml } for a number ASRC  (0 1 0) in the SRC. An alternative set W ( A) of number ASRC  (0 1 0) is defined as follows. For this number ASRC  (0 1 0) , there is no need to calculate the first stage of the nullification procedure. The second ( i  2 ) stage (second iteration) of the nullification procedure is carried out directly by means of the second nullification constant CN (2)  (0 1 4) (Table 3). Thus, we get that

A(H ) = (0 1 0) - СN (2)  (0 1 0) - (0 1 4) = (0 0 1) .

The first coordinate of table 4 is equal to one or  n1  1 . The second coordinate is determined from the expression

A(H )  ( A  A(H ) )  (0 1 0) - (0 0 1) = (0 1 4) .

In the PNS, the value of the second coordinate A(H ) is equal to four, i.e. A(H ) = 4 (Table 1). W ( A)  {m2 , m3} .

Considering that for a given SRC the maximum value of AC is equal to W ( A)  {m1, m2 , m3} , so the following inequality is obvious W ( A)  W ( A) .

Thus, the number of bases in the AS W ( A)  {m2 , m3} is reduced by  25%, in comparison with the maximum possibleW ( A)  {m1, m2 , m3}.

This circumstance makes it possible to reduce the number of checks of the bases of the SRC for determining the distorted remainder in the number ASRC  (1 2 3) , which reduces the time for diagnosing the NCS, increasing the efficiency of diagnosing data in the SRC. 3.3.

Example 3

Let the number ASRC  (0 0 2) in the SRC be given. For this example, it is not necessary to carry out the nullification procedure. The first coordinate is  3  2 . The second coordinate A(H ) is determined from the expression

A(H )  ( A  A(H ) )  (0 0 2) - (0 0 2) = (0 0 0) .

In the PNS, the value of the second coordinate A(H ) is zero, i.e. A(H ) = 0 (Table 1).

Based on the obtained values (two coordinates) A(H )  0 and  n1  2 in Table 4, we define the AS W ( A)  {m2 , m3} . Considering that, for a given SRC, the maximum value of AS is equal to W ( A)  {m1, m2 , m3}, the following inequality is obvious W ( A)  W ( A) . Thus, the number of bases in the AS W ( A)  {m2 , m3} is reduced by  30% in comparison with the maximum possible W ( A)  {m1, m2 , m3}. This circumstance makes it possible to reduce the number of checks of the SRC bases for determining the location in the number of distorted residues, which reduces the time for diagnosing NCS, increasing the efficiency of data diagnostics in SRC. 3.4.

Example 4

Let the number ASRC  (1 1 2) in the SRC be given. For the purpose of diagnostics (determining the location of the residues of the number in the SRC, according to which distortions are possible) of the number, we define the AS W ( A)  ml1 , ml2 ,..., ml  . For this, in accordance with the nullification procedure [1], by using the constants of nullification CN (1) ( i  1, 2 ) (for i  1 , the data in Table 2 are used, and for i  2 , data from Table 3 are used), we define the value A(H ) of a nullified number ASRC  (1 1 2) as follows.

Initially, by means of the first constant of nullification CN (1)  (1 1 1) (Table 2), the first ( i  1 ) stage (first iteration) of the initial number nullification procedure is carried out in the form ASRC - CN (1)  (1 1 2) - (1 1 1) = (0 0 1) .

For the obtained result, there is no need to carry out the second stage of nullification. To get the value W ( A)  ( n1, A(H ) ) from table 4, the first coordinate  3  1 is determined from the expression A (H ) = (0 0 1) . The second coordinate A(H ) is determined from the expression A(H )  ( A  A(H )

)  (1 1 2) - (0 0 1) = (1 1 1) .

In the PNS, the value of the second coordinate A(H ) is equal to one, i.e. A(H ) = 1 (Table 1).

Based on the obtained values (two coordinates) A(H )  1 and  n1  1 in Table 4, we define the AS W ( A)  {m3} . Considering that, for a given SRC, the maximum value of AS is equal to W ( A)  {m1, m2 , m3} , the following inequality is obvious W ( A)  W ( A) . Thus, the number of bases in the

AS

W ( A)  {m3} is reduced by  60% in comparison with the maximum possible W ( A)  {m1, m2 , m3} . This circumstance makes it possible to reduce the number of checks of the SRC bases for determining the location in the number of distorted residues, which reduces the time for diagnosing NCS, increasing the efficiency of data diagnostics in SRC.

4. Conclusion

Thus, the considered method of the tabular implementation of diagnostics of non-positional code structures in the system of residual classes allows reducing the time for diagnosing data errors presented in the SRC, which increases the efficiency of the diagnostic procedure. Reducing the number of bases in the AS increases the information content of W ( A) about the place of the erroneous residue in the NCS. So, the number of steps for preliminary determination of AS is reduced. The use of the proposed method of on-line diagnostics of data increases the overall efficiency and expediency of using nonpositional code structures in SRC in computing systems. The data diagnostics time is reduced in comparison with the known methods, firstly, due to the exclusion from the known methods the procedure of transferring numbers from the SRC to the positional number system, i.e. elimination the positional comparison of numbers. Secondly, the data diagnostics time is decreased by reducing the number of SRC bases for which an error is possible.

Finally, the data diagnostics time is reduced due to the use of a tabular sample of the value from an alternative set of numbers in the SRC practically in one cycle. Thus, the proposed method makes it possible to reduce the time for diagnosing errors in the data presented in the SRC, which increases the diagnostic efficiency. Examples of data diagnostics are given in the article, which confirm the technical feasibility of the considered method. A device has been developed based on the proposed method implementation and a Ukrainian patent for an invention has been obtained.

5. Acknowledgements

This work was supported in part by the National Research Foundation of Ukraine under Grant 2020.01/0351.

6. References

S. Wei, Fast signed-digit arithmetic circuits for residue number systems, in: 2015 IEEE International Conference on Electronics, Circuits, and Systems (ICECS), 2015: pp. 344–347. https://doi.org/10.1109/ICECS.2015.7440319.

A. Safari, J. Nugent, Y. Kong, Novel implementation of full adder based scaling in Residue Number Systems, in: 2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS), 2013: pp. 657–660. https://doi.org/10.1109/MWSCAS.2013.6674734.

References

[3] I. Koren, THE RESIDUE NUMBER SYSTEM , Computer Arithmetic Algorithms. ( 2018 ) 275 - 292 . https://doi.org/10.1201/ 9781315275567 - 18 .

[4] P.V.A. Mohan , Residue Number Systems , Springer International Publishing, Cham, 2016 . https://doi.org/10.1007/978-3- 319 -41385-3.

[5] P.V. Ananda Mohan , Specialized Residue Number Systems , in: P.V.A. Mohan (Ed.), Residue Number Systems: Theory and Applications , Springer International Publishing, Cham, 2016 : pp. 177 - 193 . https://doi.org/10.1007/978-3- 319 -41385- 3 _ 8 .

[6] V. Krasnobaev , M. Zub , T. Kuznetsova , I. Perevozova , O. Maliy , Mathematical Model of the Process of Tabular's Implementation of the Operation Algebraic Multiplication in the Residues Class , in: 2019 International Conference on Information and Telecommunication Technologies and Radio Electronics (UkrMiCo) , 2019 : pp. 1 - 6 . https://doi.org/10.1109/UkrMiCo47782. 2019 . 9165400 .

[7] V.A. Krasnobayev , A.A. Kuznetsov , S.A. Koshman , K.O. Kuznetsova , A Method for Implementing the Operation of Modulo Addition of the Residues of Two Numbers in the Residue Number System, Cybern Syst Anal . ( 2020 ). https://doi.org/10.1007/s10559-020-00323-9.

[8] V. Krasnobayev , A. Kuznetsov , A. Yanko , T. Kuznetsova, The analysis of the methods of data diagnostic in a residue number system , in: S. Subbotin (Ed.), Proceedings of The Third International Workshop on Computer Modeling and Intelligent Systems (CMIS-2020) , Zaporizhzhia, Ukraine, April 27-May 1, 2020 , CEUR-WS.org, 2020 : pp. 594 - 609 . http://ceurws.org/Vol- 2608 /paper46.pdf ( accessed July 2 , 2020 ).

[9] V. Krasnobayev , A. Kuznetsov , A. Yanko , K. Kuznetsova , The data errors control in the modular number system based on the nullification procedure , in: S. Subbotin (Ed.), Proceedings of The Third International Workshop on Computer Modeling and Intelligent Systems (CMIS-2020) , Zaporizhzhia, Ukraine, April 27-May 1, 2020 , CEUR-WS.org, 2020 : pp. 580 - 593 . http://ceurws.org/Vol- 2608 /paper45.pdf ( accessed July 2 , 2020 ).

[10] V. Krasnobayev , A. Kuznetsov , I. Lokotkova , A. Kiian , T. Kuznetsova, Techniques for Raising the Remainder to a Power in the System of Residual Classes , in: 2020 IEEE 11th International Conference on Dependable Systems, Services and Technologies (DESSERT) , 2020 : pp. 145 - 150 . https://doi.org/10.1109/DESSERT50317. 2020 . 9125049 .

[11] V. Krasnobaev , A. Kuznetsov , V. Babenko , M. Denysenko , M. Zub , V. Hryhorenko , The Method of Raising Numbers, Represented in the System of Residual Classes to an Arbitrary Power of a Natural Number , in: 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON) , 2019 : pp. 1133 - 1138 . https://doi.org/10.1109/UKRCON. 2019 . 8879793 .

[12] K. Phalakarn , A. Surarerks , Alternative Redundant Residue Number System Construction with Redundant Residue Representations , in: 2018 3rd International Conference on Computer and Communication Systems (ICCCS) , 2018 : pp. 457 - 461 . https://doi.org/10.1109/CCOMS. 2018 . 8463305 .

[13] V.M. Amerbaev , R.A. Solovyev , A.L. Stempkovskiy , D.V. Telpukhov , Efficient calculation of cyclic convolution by means of fast Fourier transform in a finite field , in: Proceedings of IEEE East-West Design Test Symposium (EWDTS 2014 ), 2014 : pp. 1 - 4 . https://doi.org/10.1109/EWDTS. 2014 . 7027043 .

[14] F. Barsi , P. Maestrini , Error Correcting Properties of Redundant Residue Number Systems , IEEE Transactions on Computers. C- 22 ( 1973 ) 307 - 315 . https://doi.org/10.1109/T-C. 1973 . 223711 .

[15] S. Timarchi , K. Navi , Efficient Class of Redundant Residue Number System , in: 2007 IEEE International Symposium on Intelligent Signal Processing , 2007 : pp. 1 - 6 . https://doi.org/10.1109/WISP. 2007 . 4447506 .

[16] L. Yang , L. Hanzo , Coding theory and performance of redundant residue number system codes , Ieee Trans. Inform. Theory . ( 1999 ).

[17] A. Meier , M. Pollet , V. Sorge , Comparing Approaches to the Exploration of the Domain of Residue Classes , Journal of Symbolic Computation . 34 ( 2002 ) 287 - 306 . https://doi.org/10.1006/jsco. 2002 . 0550 .

[18] V. Krasnobaev , O. Reshetniak , T. Kuznetsova , S. Florov , Y. Kotukh , Data Control Method, which Presented By Code of Non-Positioning System of Deduction Class Calculation , in: 2019 International Conference on Information and Telecommunication Technologies and Radio Electronics (UkrMiCo) , 2019 : pp. 1 - 5 . https://doi.org/10.1109/UkrMiCo47782. 2019 . 9165528 .

[19] Y. Zhang, An FPGA implementation of redundant residue number system for low-cost fast speed fault-tolerant computations , Thesis , 2018 . https://doi.org/10.32657/10220/47113.

[20] M. Karpinski , S. Ivasiev , I. Yakymenko, M. Kasianchuk , T. Gancarczyk, Advanced method of factorization of multi-bit numbers based on Fermat's theorem in the system of residual classes , in: 2016 16th International Conference on Control, Automation and Systems (ICCAS) , 2016 : pp. 1484 - 1486 . https://doi.org/10.1109/ICCAS. 2016 . 7832500 .

[21] Y.N. Kocherov , D.V. Samoylenko , A.I. Koldaev , Development of an Antinoise Method of Data Sharing Based on the Application of a Two-Step-Up System of Residual Classes , in: 2018 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon) , 2018 : pp. 1 - 5 . https://doi.org/10.1109/FarEastCon. 2018 . 8602764 .

[22] D.I. Popov , A.V. Gapochkin , Development of Algorithm for Control and Correction of Errors of Digital Signals, Represented in System of Residual Classes , in: 2018 International Russian Automation Conference (RusAutoCon) , 2018 : pp. 1 - 3 . https://doi.org/10.1109/RUSAUTOCON. 2018 . 8501826 .

[23] T.-C. Huang , Self-Checking Residue Number System for Low-Power Reliable Neural Network , in: 2019 IEEE 28th Asian Test Symposium (ATS) , 2019 : pp. 37 - 375 . https://doi.org/10.1109/ATS47505. 2019 . 000 - 3 .

[24] C.A. Gayoso , L. Arnone , C. González , J.C. Moreira , A general construction method for PseudoRandom Number Generators based on the Residue Number System , in: 2019 XVIII Workshop on Information Processing and Control (RPIC) , 2019 : pp. 25 - 30 . https://doi.org/10.1109/RPIC. 2019 . 8882147 .

[25] C. Fan , G. Ge, A Unified Approach to Whiteman's and Ding-Helleseth's Generalized Cyclotomy Over Residue Class Rings , IEEE Transactions on Information Theory . 60 ( 2014 ) 1326 - 1336 . https://doi.org/10.1109/TIT. 2013 . 2290694 .