A Method of Control and Operational Diagnostics of Data Errors Presented in a Non-positional Number System in Residual Classes

Abstract

The basis of modern infocommunication systems is computer means of data transmission and processing. Therefore, one of the alternative means of achieving maximum efficiency in the functioning of the infocommunication systems when processing data in real time is to improve, first of all, such characteristics of computer data processing systems (CDPS) as the reliability and performance of information processing, as well as the fault tolerance of its functioning. Currently, the quality of implementation of information processing procedures is largely determined by the selected mathematical model for organizing the information processing process in the CDPS. Therefore, research and finding ways to solve the problem of increasing the reliability of real-time CDPS, without reducing the productivity of processing large data arrays based on new mathematical models, is an urgent task. One of the possible innovative ways of solving the formulated problem is the usage of a non-positional number system in residual classes (NPNSRC) to create CDPS. The versatility of NPNSRC codes is explained not only by their high correcting abilities, arithmetic and the ability to fight against error packets, but also by their adaptability to flexible changes in correcting properties, without changing the coding method. The article discusses issues related to the control and diagnosis of data errors in the CDPS operating in the NPNSRC. The main attention is paid to the consideration of a method for quickly diagnosing data errors in the NPNSRC. Reducing diagnostic time increases the efficiency of diagnosing solitary errors in a non-positional code structure in the NPNSR. A specific example of the implementation of a method for diagnosing data errors in the NPNSRC is given.

Keywords

• eol>Computer data processing system
• diagnosing data errors
• non-positional code structure
• nonpositional number system in residual classes
• number projection
• orthogonal basis
• 1

1. Introduction

An analysis of existing methods for increasing fault tolerance has shown that the best and most widely used in practice today are two methods: redundancy and control, diagnostics with further restoration of the CDPS functionality. When choosing control and diagnostics methods, the main attention should be paid to the ability of this control and diagnostics method to detect errors, as well as the amount of equipment and time spent on control [1-3].

The principles of control of non-positional code structures in the NPNSRC are the same as the principles of control in the positional number system (PNS), while taking into account the principles of formation of the NPNSRC and the influence of properties of the NPNSRC on the structure of the CDPS [4], let us note, in a general way, the principles of data control in nonpositional code structures: the principle of reliability of control; the principle of continuity of control; the principle of operational control.

The most effectiveness from the usage of the NPNSRC is accomplished in cases when the realized algorithms comprise arithmetic operations such as addition, multiplication and subtraction [5]. However, in a CDPS operating in the NPNSRC, in addition to the above arithmetic operations, it is necessary to carry out so-called non-modular (positional) operations [6-8]. Such operations include control operations and correction (diagnosis and correction) of 0000-0003-2876-9316 (A. Yanko); 0000-0001-5192-9918 (V. Krasnobayev); 0009-0004-4241-2676 (O. Kruk) © 2024 Copyright for this paper by its authors.

Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). data errors. Data control, diagnosis and correction operations, compared to arithmetic operations in the NPNSRC, require significant time for their implementation. The need to implement control (monitoring) operations, diagnosis and correction of data reduce the overall effectiveness of the usage of the NPNSRC in real-time CDPS. When processing data in real time, the considerable time required for the implementation of control, diagnostic, and error correction procedures calls into question the feasibility of using NPNSRC as a general-purpose CDPS. The need to ensure the high efficiency of the functioning of the CDPS in the NPNSRC requires the development and implementation of methods of operational data control, diagnostics and correction, other than methods employed in ordinary binary PNS [9].

Within the framework of the concept of development of fast-acting and reliable CDPS presented in the NPNSRC, the urgent task is the development and application of methods and means of operational data control, diagnosis and error correction. In the article, the main focus is devoted to data diagnostics process in the NPNSRC.

The purpose of the research is to develop a method for controlling (monitoring) and operational diagnostics errors in data presented in the NPNSRC, using the orthogonal basis of partial sets of bases (modules). 2. Data correction process in the non-positional number system in residual classes The correction process (detection and correction) of errors in the information code structure D of data consists of the following main stages [4, 9]:  data control (monitoring) (the process of detecting the presence of an error in D  (d 1 ||d 2 || ...||d j || ...||dk ) , presented in the NPNSRC);  data diagnostics (localization of error locations with a given diagnostic depth);  error correction in the non-positional code structure (recovery of distorted residues {d j } (j  1,k ) of the incorrect number D and obtaining the correct number D ).

The number D  (d 1 ||d 2 || ... ||d j 1 ||d j ||d j 1 || ... ||dk ) in without redundant NPNSRC is represented by a set of residues {d j } (j  1,k ) according to the selected system of information k bases (modules) {f j } in the numerical interval 0, L  , where L   f j is overall amount of j 1 information code words [9]. In this case, the greatest common divisor of any two NPNSRC bases is equal to (di ,d j )  1 ; i ,j  1,k (i  j ) .

In order for the non-positional code structure in the NPNSRC to have the necessary corrective abilities, it is required that it contain sufficient information redundancy. First, the extant information redundancy in the original structure of the non-positional code should be determined and quantified [10]. Secondly, when tasked with providing data with additional corrective capabilities, introduce additional (artificial) information redundancy (apply the information redundancy method) by introducing additional (control) bases {f c } NPNSRCS [11].

Without loss of generality of reasoning, when tasked with providing data in the NPNSRCS with additional corrective capabilities, we will assume that only one additional control bases fc  f k 1 is added to the k information bases, which is coprime with any of the k existing information bases [4, 9]. In this case, the non-positional code structure D  (d 1 ||d 2 || ... ||d j || ... ||dk ||dk 1) in the NPNSRC is represented by a set of {f i } (i  1,k  1) bases in the full (working) numerical interval 0, L1  , where L1 L f k 1 is the overall amount of code words for this NPNSRC with one control base [9].

It is known [4, 12] that for non-positional code structure in the NPNSRC the minimum code distance is defined by the expression V min c  1 , where c is the number of control bases used in the non-positional code structure in the NPNSRC, i.e. minimum code distance depends both on the number of control bases and on the size of each of it.

g

If for the control bases {f z j } the condition j1f z j  fc is satisfied, then the introduction into the system of the NPNSRC bases of one control base fc  f k 1 is equivalent to the presence of g control bases f z 1 ,f z 2 ,...,f z g . Taking into account the fact that all numbers taking part in data processing in the CDPS, along with outcome of the operation are in the interval 0, L  , then it is clearly that if as outcome of data processing the final outcome D is obtained and at the same time D L , this means that the resulting number D is distorted (incorrect). Thus, if D L , then the conclusion is that the number D is correct, and if D L , then the number D is incorrect. In this case, only solitary errors (only in one {d j } of the number D ) are assumed, or a packet of errors no longer than s  [log2(f j  1)]  1 binary digits in one residue modulo f j .

All existing methods for monitoring data in the NPNSRC are based on this principle of comparing the value of the number D with the value 0, L  of the information numerical interval. Note that the comparison principle is also used in the development of diagnostic and error correction methods. In the future, in this article, we will consider the method of operational (quick) diagnosis. 3. Control and diagnostics of data in the non-positional number system in residual classes In [4] there are a number of scientific statements, the outcomes of the proof of which underlie for methods for controlling and diagnosing data errors presented in the NPNSRC. It should be reminded that in what follows only a solitary error is assumed (in one residue d j (j  1,k  1) of the number D  (d 1 ||d 2 || ... ||d j || ... ||dk ||dk 1) presented in the NPNSRC).

Let the number D  (d 1 ||d 2 || ... ||d j || ... ||dk ||dk 1) being checked be given in the NPNSRC with informational {f j } (j  1,k ) and one control base fc  f k 1 . It is necessary, firstly, to control (determine the correctness) of the number D , and, secondly, to diagnose the residues {d j } (j  1,k  1) of the number D , i.e. determine distorted (or undistorted) residues.

Data controlling and diagnostics are carried out sequentially in two stages.

First stage. Method for controlling (monitoring) data of non-positional code structure D  (d 1 ||d 2 || ... ||d j 1 ||d j ||d j 1 || ... ||dk ||dk 1) , which from the following algorithm of actions: 1. Determine the values of the orthogonal basis B j (j  1,k  1) for the complete system of bases (modules) {f j } NPNSRC:

B j  e j L1 ,

f j k 1 DPNS  (  d j B j ) modL1 .

j 1 where e j is weight of the orthogonal basis B j . 2. Using the system of orthogonal basis B j , the original number D in the NPNSRC is represented in the PNS [13]: 3. Carry out positional comparison operations between the values of DPNS and L . If the comparison result showed that DPNS  L , then number D is correct. If DPNS  L , then the ( 1 ) ( 2 ) number D is considered incorrect if only one of the residues {d j } of the number D is distorted.

Second stage. Method for diagnosing the residues {d j } (j  1,k 1) of the code structure D of data, based on the use of the obtained results of the following statement.

Statement. Let in an ordered (f j  f j 1) NPNSRC with k information and one control base fc  f k 1 the number D  (d 1 ||d 2 || ... ||d j || ... ||dk ||dk 1) satisfy the following condition: L  L1 Lk 1 D Li , f k 1 ( 3 ) k where L   f j is overall amount of information code words in the NPNSRC (including only j 1 information bases);

k 1 L1   f j is overall amount of all code words in the NPNSRC (including information bases and j 1 control base); Lk 1 is overall amount code words with one control base fc  f k 1 ;

k 1 Li   f p is overall amount of code words for excluding the base f i , that is p 1, p i .

Li f 1f 2...f i 1f i 1...f k 1.

Then the residues of the number D are not distorted (correct) if only a solitary error (in one residue d j ) is possible. The second stage of the developed method will be considered in more detail using a specific example. 4. An example of the application of the control and operational diagnostics method Let's consider an example of using the control and diagnostic method in the NPNSRC for a onebyte (l = 1) machine word (8 binary digits) CDPS. In this case, a complete NPNSRC with one control base is specified by information f 1 3, f 2  4, f 3 5, f 4 7 and control fc  f k 1  f 5  11 bases. At the same time, the requirements for unambiguous representation of code words in a given information numeric 0, L  range are ensured.

k 1 For a given NPNSRC we can calculate: L1   f j  f 1  f 2  f 3 f 4 f k 1  3 4 57 11  4620 j 1 k – overall amount of code words in this NPNSRC; L   f j  f 1  f 2  f 3 f 4  3 4 57  420 – j 1 overall amount of information code words in this NPNSRC. In this case, the full (working) 0, L1  and informational 0, L  numerical ranges of numbers are defined, respectively, as 0, 4620 and 0, 420 . All possible partial sets of the NPNSRC bases for a one-byte (l = 1)

L CDPS are presented in Table 1, where Li  f 1 , f i is a base that is not included in the given i complete system of the NPNSRC bases.

For example, consider the process of finding Li , since the complete system of bases of the considered NPNSRC consists of five bases: f 1 3, f 2  4, f 3 5, f 4 7 and f 5  11, the base that is not included in the first line (i  1) of Table 1 is f i  3, so we divide overall amount of code 3 f3 multiplying all sets of bases NPNSRC in the first line (i  1) of Table 1: L1  45711  1540.

Let, in the process of data processing, in lieu the correct D  (1 ||0|| 0|| 2|| 1) (DPNS  100 L  420) result of the operation a number of the form D  (0||0|| 0|| 2|| 1), where DPNS  3180 L  420. It is necessary to verify the correctness of the number D and diagnose its residues {d j } (j  1,5).

First stage. 1. Let's define all possible orthogonal basis B j (j  1,5) using formula ( 1 ) for the complete system of bases f 1 3, f 2  4, f 3 5, f 4 7 and f 5  11 NPNSRC [14]: B1  ( 1,0,0,0,0 )  1540, e1  1, B 2  ( 0,1,0,0,0 )  3465, e2  3, B3  ( 0,0,1,0,0 )  3696, e3  4, B 4  ( 0,0,0,1,0 )  2640, e 4  4, B5  ( 0,0,0,0,1 )  2520, e5  6. 2. Using the values of orthogonal basis B j (j  1,5), let's determine the value of number D in the NPNSRC is represented in the PNS according to formula ( 2 ):

DPNS  (01540  03465 03696  22640  12520)modL1  7800mod4620  3180. 3. Let's compare the obtained number of DPNS and the value L  420. Since DPNS  3180 L  420, we make conclusion that the received D is incorrect by {d j } of the correct number D  (1 ||0 || 0 || 2|| 1).

Second stage. 1. Let's determine the values of partial orthogonal basis B ji for each of the 5 possible sets of the NPNSRC bases [15]. In general, the value of partial orthogonal basis B ji is determined based on the following comparison [16, 17]: ( 4 ) where e ji  1,f j  1 – weight of the orthogonal basis B ji .

So, for j  4 and i  5 we have:

B ji  Li e ji  1(modf j ), f j B1i  ( 1,0,0,0 ), B 2i  ( 0,1,0,0 ), B3i  ( 0,0,1,0 ), B 4i  ( 0,0,0,1 ).

L f 1 4 depending on possible e 11 : Let's determine the values of B j 1 for the first (i  1) set of bases: f 1  4, f 2 5, f 3 7 and 4 f 4  11 (see Table 1). In this case L1   f j  45711  1540 ( L  420 ). We determine the j 1 values of the partial orthogonal basis based on the known relationship [18-20].  385, e11  1,f 1  1  1, 4  1  1, 3. Let's compose possible values of B 11

In this case, to fulfill the condition ( 4 ) we have that B 11  1 385  385.

Let's determine the value of B 21  L1fe221 . In this case f 2  5, e21  1,f 2  1  1, 5  1  1, 4. Let's make a set of comparisons:  1308  3(mod5), 2308  1(mod5),  3308  4(mod5), 4 308  2(mod5).

In this case, B 21  2308  616.

Let's determine the value of B 31  L1fe331 . In this case f 3  7, e31  1,f 3  1  1, 7  1  1, 6. Let's make a set of comparisons: 1220  3(mod7), 2220  6(mod7), 3220  2(mod7), 4 220  5(mod7),  5220  1(mod7), 6 220  4(mod7).

In this case, B31  5220  1100.

Let's determine the value of B 41  L1fe4 41 . In this case f 4  11, e 41  1,f 4  1  1, 11  1  1, 10. Let's make a set of comparisons:

 220, L 1  1540 11

Let's determine the values of B j 2 for the second (i  2) set of bases: f 1 3, f 2 5, f 3 7 and Let's determine the value of B12  L2f1e12 . In this case f 1  3, e12  1,f 1  1  1, 3  1  1, 2. Let's make a set of comparisons: L

Let's determine the value of B 22  L2 e22 . In this case f 2  5,

f 2 e22  1,f 2  1  1, 5  1  1, 4. Let's make a set of comparisons:  1231  1(mod5), 2231  2(mod5),  3231  3(mod5), 4 231  4(mod5).

In this case, B 22  1231  231.

Let's determine the value of B32  L2 e32 . In this case f 3  7, f 3 L2  1155  165, 7 e32  1,f 3  1  1, 7  1  1, 6. Let's make a set of comparisons:

Let's determine the values of B j 3 for the third (i  3) set of bases: f 1 3, f 2  4, f 3 7 and e13  1,f 1  1  1, 3  1  1, 2. Let's make a set of comparisons: L3  924  308, 3 In this case, B13  2308  616.

Let's determine the value of B 23  L2 e23 . In this case f 2  4, f 2 e23  1,f 2  1  1, 4  1  1, 3. Let's make a set of comparisons:  1308  2(mod3),

2308  1(mod3). 1231  3(mod 4), 2231  2(mod 4), 3231  1(mod 4).

In this case, B 23  3231  693.

Let's determine the value of B33  L2 e33 . In this case f 3  7,

f 3 e33  1,f 3  1  1, 7  1  1, 6. Let's make a set of comparisons: 4 132  3(mod7),  5132  2(mod7), 6 132  1(mod7).

Let's determine the value of B 43  L2 e 43 . In this case f 4  11,

f 4 e 43  1,f 4  1  1, 11  1  1, 10. Let's make a set of comparisons: L

Let's determine the values of B j 4 for the fourth (i  4) set of bases: f 1 3, f 2  4, f 3 5 and e14  1,f 1  1  1, 3  1  1, 2. Let's make a set of comparisons: L 4  660 3 In this case, B14  1 220  220.

Let's determine the value of B 24  L4 e24 . In this case f 2  4, f 2

L

Let's determine the value of B34  L4 e34 . In this case f 3  5, f 3

L e34  1,f 3  1  1, 5  1  1, 4. Let's make a set of comparisons:  1132  2(mod5), 2132  4(mod5),  3132  1(mod5), 4 132  3(mod5).

In this case, B 34  3132  396.

Let's determine the value of B 44  L4 e 44 . In this case f 4  11,

f 4 e 44  1,f 4  1  1, 11  1  1, 10. Let's make a set of comparisons: L 1  60  5(mod11), 260  10(mod11), 360  4(mod11), 4 60  9(mod11), 560  3(mod11), 6 60  8(mod11), 7 60  2(mod11), 8 60  7(mod11), 9  60  1(mod11), 10  60  6(mod11).

In this case, B 44  9  60  540.

Let's determine the values of B j 5 for the fifth (i  5) set of bases: f 1 3, f 2  4, f 3 5 and 4 f 4  7 (see Table 1). In this case L5   f j  3457  420 (L  420 ).

j 1 e25  1,f 2  1  1, 4  1  1, 3. Let's make a set of comparisons:  1140  2(mod3),

2140  1(mod3). e35  1,f 3  1  1, 5  1  1, 4. Let's make a set of comparisons:  1 84  4(mod5), 2 84  3(mod5),  3 84  2(mod5), 4  84  1(mod5).

In this case, B35  4  84  336.

Let's determine the value of B 45  L5 e 45 . In this case f 4  7, f 4 e 45  1,f 4  1  1, 7  1  1, 6. Let's make a set of comparisons:

The set of calculated partial orthogonal basis B ji is given in Table 2. 2. Let's determine the correctness of the residues of the number D . First, let’s compose all possible projections Di of the number D  (0 ||0 || 0 || 2|| 1) :

2 D5  ( 0, 0, 0, 2 ).

3 L L L

4 3. Let's represent the values of the projections Di in the PNS [14]:

Thus, of all the received projections Di of the number D  (0||0|| 0|| 2|| 1) the projections D1, D3, D5 L  420 and the projections D2, D4 L  420. Therefore, the results of controlling and diagnosing the incorrect D number state that among all five residues of the number it is the residues d 1, d 3 and d 5 may be erroneous, but the residues d 2 and d 4 are definitely not distorted.

5. Conclusions

This article improves the method of control and operational diagnostics of data errors presented in the NPNSRC, using the orthogonal basis B ji of partial sets of bases (modules) NPNSRC. The values of orthogonal basis B ji are formed from the complete system of bases {f i } (i  1,k  1) , and it usage provides an opportunity to organize the parallel processing of projections Di of numbers D of a non-positional code structure in the NPNSRC. This circumstance makes it possible to enhance efficiency of controlling and diagnosing data in the CDPS operating in the NPNSRC.

Examples of specific realization of the process of controlling (monitoring) and diagnosing errors are given. It is established that the use of the proposed method will improve the efficiency of controlling and diagnosing data errors in the data processing system operating in the NPNSRC, and will also technically simplify the procedure for processing non-positional code structures. International Conference on Dependable Systems, Services and Technologies (DESSERT), Athens, Greece, 2023, pp. 1–6. doi:10.1109/DESSERT61349.2023.10416508. [6] G. Sobczyk, Modular Number Systems, New Foundations in Mathematics, Birkhäuser,

Boston, MA, 2013, pp. 1–21. doi:10.1007/978-0-8176-8385-6_1. [7] V. Yatskiv, T. Tsavolyk, Two-dimensional corrective codes based on modular arithmetic, in: The Experience of Designing and Application of CAD Systems in Microelectronics, Lviv, 2015, pp. 291–294. doi:10.1109/CADSM.2015.7230860. [8] N.I. Chervyakov, A.V. Veligosha, K.T. Tyncherov, S. A. Velikikh, Use of modular coding for high-speed digital filter design, Cybernetics and Systems Analysis 34 (1998) 254–260. doi:10.1007/BF02742075. [9] V. Krasnobayev, A. Yanko, D. Kovalchuk, Control, Diagnostics and Error Correction in the Modular Number System, in: The Sixth International Workshop on Computer Modeling and Intelligent Systems (CMIS 2023), Zaporizhzhia, Ukraine, 2023, pp. 199–213. doi:10.32782/cmis/3392-17. [10] P. V. A. Mohan, Residue Number Systems: Theory and Applications, Birkhäuser Basel,

Switzerland, 2016. [11] R. Liu, L. Li, Y. Yang, Performance Residual Based Fault Detection for Feedback Control Systems, IEEE Transactions on Circuits and Systems II: Express Briefs 68 (2021) 3291– 3295. doi:10.1109/TCSII.2021.3062718. [12] S. Onyshchenko, A. Yanko, A. Hlushko, Improving the efficiency of diagnosing errors in computer devices for processing economic data functioning in the class of residuals, Eastern-European Journal of Enterprise Technologies 5, 4 (125) 63–73. doi:https://doi.org/10.15587/1729-4061.2023.289185. [13] M. Zaharchenko, M. Hadzhyiev, A. Nazarenko, N. Salmanov, N. Shvets, Comparison of Positional and Timer Coding in the System of Residual Classes, in: 2022 IEEE 16th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET), pp. 414–418. doi:10.1109/TCSET55632.2022.9766866. [14] A. Moskalenko, V. Krasnobayev, S. Koshman, The concept of diagnostic data errors of computing systems witch functioning in the system of residue classes, Computer science and cybersecurity (CS&CS) 2 (6) (2017) 39–46. URL: https://periodicals.karazin.ua/cscs/article/download/8733/9891. [15] V. Krasnobayev, A. Yanko, A. Hlushko, Information Security of the National Economy Based on an Effective Data Control Method, Journal of International Commerce, Economics and Policy 14 ( 3 ) (2023). doi:10.1142/S1793993323500217. [16] J. James, A. Pe, A novel method for error correction using Redundant Residue Number System in digital communication systems, in: 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Kochi, 2015, pp. 1793–1798. doi:10.1109/ICACCI.2015.7275875. [17] Z. Wang, E. Zheng, J. Liu, T. Guo, Adaptive Orthogonal Basis Function Detection Method for Unknown Magnetic Target Motion State, Applied Sciences 14 ( 2 ):902 (2024). doi:10.3390/app14020902. [18] O. Laktionov, L. Lievi, A. Tretiak, M. Movin, Investigation of combined ensemble methods for diagnostics of the quality of interaction of human-machine systems, Naukovyi Visnyk Natsionalnoho Hirnychoho Universytetu 4 (2023) 138–143. doi:10.33271/nvngu/20234/138. [19] L. Mu, X. Liu and L.-L. Yang, Redundant Residue Number System Coded Diffusive Molecular Communications, in: 10th International Conference on Wireless Communications and Signal Processing (WCSP), Hangzhou, China, 2018, pp. 1–6, doi:10.1109/WCSP.2018.8555582. [20] Y. Jia, S. Wang, J. Jin, H. Long, Hang, Adaptive Orthogonal Basis Scheme for OTFS, in: Proceedings of the 17th International Conference on Communications and Networking, volume 500 of Lecture Notes of the Institute for Computer Sciences, Springer, Switzerland, 2023. doi:10.1007/978-3-031-34790-0_5.

References

[1] R. Wilmhof , F. Taylor , On hard errors in RNS architectures , IEEE Transactions on Acoustics, Speech, and Signal Processing 31 ( 1983 ) 772 - 774 . doi: 10 .1109/TASSP. 1983 . 1164105 .

[2] H. Krishna , K.- Y. Lin , J.-D. Sun , A coding theory approach to error control in redundant residue number systems. I. Theory and single error correction , IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 39 ( 1992 ) 8 - 17 . doi: 10 .1109/82.204106.

[3] Lie-Liang Yang , L. Hanzo , Redundant residue number system based error correction codes , in: IEEE 54th Vehicular Technology Conference , Atlantic City, NJ, 2001 , pp. 1472 - 1476 . doi: 10 .1109/VTC. 2001 . 956442 .

[4] I. Ya. Akushskii , D.I. Yuditskii , Machine Arithmetic in Residual Classes, Sov. Radio, Moscow, 1968 .

[5] V. Krasnobayev , A. Yanko , D. Kovalchuk , Control, An Improved Method for Performing the Arithmetic Operations of Modulo Addition of the Remainders of Numbers , in: 2023 13th