Method of Diagnostic of Non-Positional Code Structures in the System of Residue Classes Basing on the Usage of an Alternative Number Set Informativeness

Abstract

A method of diagnosis of data represented in the system of residue classes (SRC) is suggested in the article. It is shown, that the main disadvantage of existing methods of diagnosis data in SRC is a significant time of data diagnosis while the necessity of entering heavy informational redundancy to non-positional code structure (NCS) in SRC. The considered in the article method of diagnosis data in SRC allows increasing operability of a diagnosis procedure while entering minimal informational redundancy. The time of data diagnostic, compared to known methods, is decreasing firstly due to excluding the procedure of transforming numbers in SRC to positional notation as in known methods, i. e. eliminating a positional operation of numbers comparing. Secondly, the time of data diagnostic is decreased by reducing the quantity of SRC bases, which are giving the possibility of mistakes. Thirdly, the time of data diagnostic is decreased due to the usage of tabular sample value of an alternative set (AS) of numbers in SRC in one beat. The quantity of additionally entered informational redundancy is decrease by effective usage of inner informational redundancy existing in NCS. A specific example of the usage of the suggested method of diagnosis data in SRC is given. Therefore, the suggested method allows reducing the time of diagnosis of data errors in NCS, represented in SRC, which is increasing the diagnostic operability while entering minimal informational redundancy.

Keywords

• 1 Non-positional code structures
• system informativeness

1. Introduction

i.e. set AS:

On the other hand, a necessity of providing fault-tolerant functioning of CS in SRC requires the development and deployment of methods of quick control, diagnostic, and data error correction, which are different from methods, used in regular binary positional notations (PN) [15–17].

Thus, researches, devoted to the development and improvement of quick (operative) methods of diagnostic of errors of data in CS, functioning in SRC, are important and relevant.

The aim of the article is the development of the method of quick diagnostic of data in SRC while entering minimal informational redundancy.

In the general case, the diagnosis of data in SRC is being understood as a process of defining distorted residues in NCS as

ASRC  (a1 || a2 || ... || ai1 || ai || ai1 || ... || an || ... || ank ) , where n and k are quantity of informational and control bases mi (i  1, n  k ) in ordered ( mi  mi1 )

SRC, correspondingly.

The diagnostic of NCS is being performed after the data control for further probable error correction. In the article, the method of data diagnostic in the case of entering minimal ( k  1 ) informational redundancy is considered. The minimal code distance equals two. The method is based on the concept of an alternative number set and the usage of features of NCS in SRC [10,14]. Due to those the procedure of increasing informativeness of AS in SRC is developed. 2. The Method of Diagnostic of Non-Positional Code Structures in the System of Residue Classes

Consider the method of NCS diagnostic, based on obtaining additional information about probably distorted residues of incorrect number A . This information is contained in all possible AS of number

Let SRC is specified by ordered ( mi  mi1 ) bases m1,..., mn1 . And let an incorrect number A is defined in the process of calculations.

For increasing informativeness about placement and error measures, it is suggested to additionally define AS of number as

Tentatively calculate the value of the interval ( j  1) of the number A occurrence in order to define Wki  A  mk1 , mk2 , ... , mki  , W1  A  m11, m12 , ... , m1  ;

1 1 W2  A  m21, m22 , ... , m2  ;

2 2 . . . . . . . . . . .

Wn1n1  A  mn11, mn12 , ... , mn1n1  .

jk  mk  k  mod mk  ,

Wn1n1  A  W  A . ( 1 ) ( 2 ) the set of values ( 1 ) for k  1, n  1 .

Also, due to value k  n  1 the Wn1n1  A equals

According to ( 2 ) the formation of k tables is performed, where values  k are matched against ai . After defining AS Wki  A , which called primary ASs, the secondary ASs are defined as vectors, components of which are possible values of errors ai as:

W 1  A  a11 , a21 ,..., an11 ,

1 and so on to the value of vectors in the form of: and completely to value of vector as: … … W 1  A  a11 , a21 ,..., an11 ; 1

W22  A  a12 , a22 ,..., an21 , W  2   A  a1 2  , a2 2  ,..., an12 ;

2 W  n   A  a1 n  , a2 n  ,..., an1n , n

Wn+1(Ã) = {a1, a2, …, an+1}.

Components of the vector Wn1(A) are compared to according components of all vectors Wi i   A for i  1, n . The matching the measure components of vectors are chosen and the bases of SRC are defined, and their set defines resulted AS in the form of

W  A  mz1 , mz2 , ... , mz  .

Indeed, among AS Wk  A there is always a basis mi , which gives an error ai , and that basis can be only among bases, which are common for the set ( 1 )

When an ai has such value, that number A starts to belong to the interval, then an equation is fulfilled

where and

M1  M  mn1 .

Thus, the idea of the suggested method lays in the following: all possible ASs are defined on each of the intervals of number A occurrence. After this, the common for these intervals bases which possibly give errors, are defined.

That set of bases define sought AS. The reduction of the number of bases in AS increases the informativeness of AS W  A about place and measure of error. It decreases the time of reducing AS to an incorrect basis (the amount of steps of tentatively AS defining is decreasing) and increases operability of diagnostic of data in SRC.

The structure scheme of the process of AS reduction is presented in Fig. 1.

W  A  W  A . W  A  W  A n M   mi

i1 mz1 , ... , mz , ( 3 ) ( 4 )

Defining of primary AS (j1)

Defining of secondary AS

Comparing and … …

…

Initial number

Defining of primary AS (jn)

Defining of primary AS (jn+1)

Defining of

secondary AS

Defining of secondary AS

Comparing and

. . .

Choice of the common bases of SRC

Defining of

3. Geometrical Model of the Procedure of the Increasing AS Informativeness

The geometrical model of the suggested method should be considered. The defining of the number ( j 1) of the interval of distorted number A occurrence, which is influenced by error ai , is equivalent to the shift of this number in the interval  j Mmii , j  1 Mm11  to the left to value j Mm11 . Decompose numerical sequence to corresponding intervals with length: Mm11 , Mm21 , …, mMn11 . Define the numbers of intervals ( j 1) , in which there is an operand A on each of the numerical segments as  M M 

Tj1   j1 m11 , j1  1 m11  , . . . . . . . .

 M1 , jn1  1 Tjn1   jn1 mn1 

M 

1 . mn1  ( 5 )

Defining the primary ASs ( 1 ) corresponds to defining the intervals numbers ( 5 ). Defining the secondary AS W  A geometrically correspond to defining the interval  z1, z2  , where i.e. sought interval is being defined as intersecting of intervals sets ( 5 )

Condition ( 6 ) is equivalent to condition ( 3 ). If error moves operand A to the interval

Condition (7) is equivalent to condition (4).

The suggested geometrical model confirms the correctness of the method’s mathematical description, and also more clearly demonstrates the idea of the procedure of informativeness AS increasing or the reduction of the numerical interval of distorted number A occurrence.

Consider an example of defining AS of number A according to the developed method. There is SRC with bases m1  2 , m2  3 , m3  5 . The code words of this SRC are presented in Table 1.

M  2  3  6 , M1  M  5  30 , mn1  m3  5 , A  0, 2, 2 , A  0, 2, 0 .

It is obvious, that

mn1 1, M , M1  , then

Thus,

by ith basis ( a2  2 ) there is a number

A  A  A  0, 2, 2 .

z1  max  ji Mm1 ; i

M z2  min   ji  1 1 ,

mi TW  A  Tj1  Tj2  ...  Tjn1 . In order to define the set of primary ASs it is needed to tentatively define values jk .

For this, the nuvelization of a number A accordingly to the tables of nuvelization constants (Tables

2–4) is performed.

After this there are

The set of primary ASs is defined as

m2 ( 0, 1, 0 ) ( 1, 2, 0 ) The set of secondary ASs is defined by Tables 5–7, which are formed by values jn : W3  A  1,1, 2; W21  A  1, 0, 2; W 2  A  0, 0,3;

2 W 1  A  0, 2,3;

1 W 2  A  0, 0, 4.

1

Possible values of errors none Δа2 = 1, Δа3 = 1,

Wi(Ψi)

– W3( 1 )(Ã) = {0, 1, 1},

m2 ( 0, 1, 4 ) ( 0, 2, 2 )

m3 ( 0, 0, 1 ) ( 0, 2, 2 ) ( 0, 0, 3 ) ( 0, 1, 4 )

Implementation of choice of common SRC bases is suitable in the form of tables (Tables 8–11), where sign “+” means match of the components of secondary ASs, and sign “–” means mismatch. Those tables show, that vectors components match in the bases m , m , i.e. the sought AS is as 1 3 W3  A  m1, m3 (table 8). Therefore, W  A  W  A . Thus, the increase of the informativeness about error placement in the distorted number A is guaranteed by the described method. W3( 1 )(Ã) = {1, 1, 2}, W3( 1 )(Ã) = {1, 2, 3}, W3( 1 )(Ã) = {0, 2, 4} 6 6 6 6

The geometrical interpretation example for the given SRC is represented in the following way (Fig. 2). The segment [0,30) is decomposed according to numerical intervals [15,30) , [10,15) and [12,18) . Define numbers of intervals, in which an operand A  1, 2, 2 placed.

Tj1  15,30 , Tj2  10, 20 , Tj3  12,18 .

4. Conclusion

Thus, the suggested method allows decreasing the time of diagnostic of errors of data, represented in SRC, which increases diagnostic operability. A reduction of the number of bases in AS increases informativeness AS about error placement and measure. It decreases the time of AS reduction to incorrect bases (the number of steps of tentatively AS defining is decreasing). The usage of the suggested method of operative diagnostic of data increases the total effectiveness and feasibility of using non-positional code structures in SRC in computing systems.

The time of data diagnostic, compared to known methods, is decreasing firstly due to excluding the procedure of transforming numbers in SRC to positional notation as in known methods, i. e. eliminating a positional operation of numbers comparing. Secondly, the time of data diagnostic is decreased by reducing the quantity of SRC bases, which are giving the possibility of mistakes. Thirdly, the time of data diagnostic is decreased due to the usage of tabular sample value of an alternative set (AS) of numbers in SRC in one beat.

Therefore, the suggested method allows reducing the time of diagnosis of data errors in NCS, represented in SRC, which is increasing the diagnostic operability while entering minimal informational redundancy. The geometric model of the procedure of AS informativeness increasing and specific examples of usage of the suggested method of diagnostic of data in SRC confirms its practical feasibility.

The most effective way of the method used is in the computational chain, which does not allow perform all planned procedures to AS reduction to the incorrect basis, i.e. in a quite long chain of calculations of CS.

5. Acknowledgments

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

6. References

[11] 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: International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon), 2018, pp. 1–5. doi:10.1109/FarEastCon.2018.8602764.

[12] G. Harman, I. E. Shparlinski, Products of Small Integers in Residue Classes and Additive Properties of Fermat Quotients, International Mathematics Research Notices 5 (2016) 1424–1446. doi: 10.1093/imrn/rnv182.

[13] 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, Cybernetics and Systems Analysis 56 (2020) 1029–1038. doi:10.1007/s10559-02000323-9.

[14] 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: International Conference on Information and Telecommunication Technologies and Radio Electronics (UkrMiCo), 2019, pp. 1–6. doi:10.1109/UkrMiCo47782.2019.9165400.

[15] Y.Zhang, An FPGA implementation of redundant residue number system for low-cost fast speed fault-tolerant computations, Master's thesis, Nanyang Technological University, Singapore, 2018. doi: 10.32657/10220/47113.

[16] K. Tao, L. Peng, K. Liang, B. Zhuo, Irregular repeat accumulate low-density parity-check codes based on residue class pair, in: IEEE 9th International Conference on Communication Software and Networks (ICCSN), 2017, pp. 127–131. doi: 10.1109/ICCSN.2017.8230092.

[17] 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: International Russian Automation Conference (RusAutoCon), 2018, pp. 1–3. doi:10.1109/RUSAUTOCON.2018.8501826.

References

[1] P. V. A. Mohan , Residue Number Systems , Springer International Publishing, Cham, 2016 . doi: 10 .1007/978-3- 319 -41385-3.

[2] I. Koren , The residue number system , in: Computer Arithmetic Algorithms, A K Peters/CRC Press, 2002 . doi: 10 .1201/ 9781315275567 - 18 .

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

[4] P. V. A. 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 . doi: 10 .1007/978-3- 319 -41385- 3 _ 8 .

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

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

[7] V. Krasnobayev , A. Kuznetsov , A. Yanko , K. Kuznetsova , Correction Codes in the System of Residual Classes , in: IEEE International Scientific-Practical Conference Problems of Infocommunications, Science and Technology (PIC S T) , 2019 , pp. 488 - 492 . doi: 10 .1109/PICST47496. 2019 . 9061253 .

[8] 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: International Conference on Information and Telecommunication Technologies and Radio Electronics (UkrMiCo) , 2019 , pp. 1 - 5 . doi: 10 .1109/UkrMiCo47782. 2019 . 9165528 .

[9] M. G. Arnold, The residue logarithmic number system: theory and implementation , in: 17th IEEE Symposium on Computer Arithmetic (ARITH'05) , 2005 , pp. 196 - 205 . doi: 10 .1109/ARITH. 2005 . 44 .

[10] V. Krasnobayev , A. Kuznetsov , A. Yanko , B. Akhmetov , T. Kuznetsova, Processing of the Residuals of Numbers in Real and Complex Numerical Domains , in: T. Radivilova , D. Ageyev , N. Kryvinska (Eds.), Data-Centric Business and Applications , Springer International Publishing, Cham, 2021 , pp. 529 - 555 . doi: 10 .1007/978-3- 030 -43070-2_ 24 .