A method for error control in the modular number system (MNS) based on the use of the zeroing procedure is proposed. Error control in the MNS is a non-positional operation and requires the development of special methods, designed to increase the efficiency of this procedure. This method is designed to verify the correct implementation of the computing process of computer systems and components. It is assumed that the error in one module remainder does not affect the residual values corresponding to other modules (bases) of the MNS. The essence of the proposed method is that, when performing the procedure of zeroing in the MNS, the operation of determining is combined in time, in accordance with the digits ai(i1) and an(ii1)1 of the number A(i1) , the zeroing constant ZC (i) and the calculation operation for the values of ai(i1) and an(ii1)1 of the following digits ai(i)1 and an(i-)i of the number A(i) . This makes it possible to increase the efficiency of information control, presented in the modular number system.
The main direction of modern science and technology is the development and use of new advanced information technologies based on the extensive use of computer systems and components (CSC). Information technologies are increasingly invading our lives, penetrating all processes (social, economic, political). Scales and complexity of the tasks solved by modern computer systems impose qualitatively new requirements to their main characteristics: productivity, reliability and efficiency of systems that causes need of improvement existing and creations of new means of information processing. In modern computer systems, an improvement in one group of quality
Copyright © 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
indicators, for example, an increase in productivity, leads to a deterioration in others –
a complication of structure, an increase in cost, a decrease in reliability, etc. [
In connection with the constant complication of scientific and technical problems
of processing integer data, the trend of development of CSC is aimed at increasing the
speed (productivity) and reliability of the implementation of integer arithmetic
operations [
This is due to the main disadvantage of modern CSC, functioning in the PNS: the
presence of inter-digit relations between the processed numbers. These relations
negatively affect the architecture of the CSC and the methods of implementing arithmetic
operations, complicate the equipment, they limit the speed and reliability of
performing arithmetic operations. In this regard, in the PNS, the increase in the performance
of the CSC is achieved by increasing the clock frequency, as well as through the use
of methods and tools for parallel data processing, and also by use of different types of
reservation [
Application of the basic methods of increasing the productivity of the CSC, based on the parallelization of computations, by using some properties of solvable tasks and algorithms cannot increase the productivity of CSC in each and every case. The scope of their application is limited to a class of tasks to be solved. In addition, the process of artificial dismemberment of the algorithm itself, the determination and allocation of independent computing branches and related operations requires large labor costs, and it is not always possible to parallelize arbitrary algorithms in general. It should be noted that all existing methods of increasing productivity in PNS have a general disadvantage: the impossibility of parsing the maximum algorithms that are solved at the level of elementary operations.
However, this approach does not always solve the problem of cardinal increase in speed and reliability of performing arithmetic operations in the PNS.
To date, there has been a gap between the increasing requirements for improving the performance of real-time computer systems, on the one hand, and the impossibility of satisfying these requests based on the use of existing PNS, on the other hand.
This fact led to the need to find ways to increase productivity, for example, based on the use of new structural solutions in the creation of CSC.
Scientific researches were conducted in recent years, identify promising ways to
improve the performance of computer systems, which are based on the use of the
modular number system (MNS) [
Research methodology and analysis of results
Currently, intensive searches are underway to improve the efficiency of arithmetic operations through the development and implementation of reliable and fast real-time CSC.
The results of the studies devoted to the improvement of the characteristics of CSC
showed that one really practical direction is the approach based on the use of MNS
codes [
At present again interest in use of MNS as tool for increase in productivity, reliability, survivability and also reliability of calculations of computer systems increases. It is caused primarily by the following circumstances:
– the emergence of the numerous scientific and theoretical publications devoted to the theory and practice of the computer systems and components creating in MNS; – wide distribution of mobile processors that require high speed data processing at low energy consumption; the lack of inter-bits transfers during arithmetic operations of addition and multiplication of numbers in MNS allows to reduce energy consumption;
– strong interest to MNS is being shown by the banking structures, where it is necessary in real time to handle large amount of data safely and reliably, i.e. they are required highly-productive means for highly reliable computing with errors selfcorrection, that is typical to the MNS codes;
– the elements density increasing on a single chip doesn’t always allow to perform a complete and qualitative testing; in this case there is an increasing importance of providing failover operation of CSC;
– the need for the use of the specialized CSC to perform a large number of operations on vectors, which require high-speed performance of integer addition and multiplication operations (matrix multiplication problems, the problems of the scalar product of vectors, Fourier transformation, etc.);
– the widespread introduction of microelectronics into all spheres of human activity significantly increased relevance and importance of previously rare, and now so massive scientific and practical problems, as a digital signal and image processing, image recognition, cryptography, multi-bit data processing and storage, etc.; this circumstance requires enormous computing resources being in excess of the existing possibilities;
– the current level of microelectronics development is coming to its limits from the point of view of productive provision and reliability of existing and future computer systems and components of large data sets processing in real time;
– taking it over nanoelectronics, molecular electronics, micromechanics, bioelectronics, optical, optoelectronic and photonic computers and others are still rather far from the real industrial production and employment.
– the modern development of integrated circuit technology allows to have a fresh look at the principles of devices construction with modular arithmetic employment and provides wide opportunities to use new design techniques (such as the methodology of systems design on a chip-SoC) both in the development of individual computing units, and computer systems in general; integral technology enables more flexible design of computer systems and components and allows us to implement MNS -based devices as effectively as on the basis of the binary system; furthermore at present in order to improve the effectiveness of computer devices development, automated design systems (ADS) are widely used; in this respect, the design of computer systems and components based on MNS does not differ from the working with the help of ADS data of binary data-blocks in PNS;
– unfortunately, Ukraine today in contrast to the theoretical development,
technologically is behind the foreign microelectronics of some leading countries; in this
case, it is advisable to use the existing theoretical achievements and practical
experience in the creation of effective computer systems and components in MNS [
One of the disadvantages of MNS is that there are no simple signs of the output of the result of operations outside the operating range [0, М), where: n M mi
i1 – operating range; mi i -th MNS base; n – number of operating bases of MNS. This requires additional time to implement the error correction process. This circumstance reduces the effectiveness of the use of MNS in the CSC.
At the heart of the majority of control methods of data are based on the analysis of
information, that is on comparison of data. Therefore researches and development of
mathematical models, methods and algorithms of comparison of numbers in MNS is
an important and relevant task. Now it is possible to allocate three groups of methods
of comparison of numbers in MNS [
The first group includes methods of direct comparison, based on the conversion of numbers AMNS and BMNS from a code MNS at PNS: and АPNS 1 2... 0 ВPNS 1 2... 0 ( – digits number (number length) AMNS and BMNS ) and their further comparison on the basis of use of binary position adders.
The second group of methods includes methods based on the principle of zeroing. The procedure for the zeroing process consists in transition from initial number:
AMNS (a1, a2 ,..., ai1, ai , ai1,..., an ) presented to MNS to the number of species:
AM(zN)S (0, 0,..., 0, n(А) ).
Then, on value (A) the interval [ jmi , ( j 1)mi ) of hit of number is defined AMNS .
n The number zeroing is performed in the same way:
BMNS (b1, b2 ,..., bi1, bi , bi1,..., bn )
from where we receive values n(B) . Position comparison of the received values
(A) and n(B) defines result of comparison of numbers AMNS and BMNS [
To the third group of methods, we will assign the methods based on the definition (allocation) or the formation of special features, the so-called positional features of the non-positional code.
To detect errors in MNS, the most commonly used procedure is zeroing. The essence of the procedure consists in the successive subtraction from the initial number: of certain minimum numbers ZC(i) – zeroing constants such that the number A is successively transformed into a number of type: А (а1, а2 ,,аn , аn1)
An (0,0,,0, n1)
in n cycles. If the obtained value of the remainder on the control basis n1 0,
then it is assumed that the number A is erroneous. In this case, the zeroing constants
must be chosen in such a way that in the subtractions such as А ZC(i) the output of
the number outside the operating [0, М) range [
The purpose of this article is the development and research of the error control method in MNS based on the application of the zeroing procedure. 2.2
In general, the essence of the procedure of the process of zeroing consists of the sequence of the following operations.
Stage 1. Initial checked number:
A A(0) (a1(0) , a2(0) ,...ai(0) , ai(01) ,...an(0) , an(0)1) (1) Expression (1) is successively reduced to the form:
A(H ) (0, 0,..., 0, 0, n1) by means of a subtraction operation sequence that does not result in the output of a numerical value of the А0 number outside of the operating range [0, M) of MNS. As noted earlier, this operation in MNS is called zeroing, and consists from successive subtraction (from one of the MNS bases) from the initial number А0 of minimum numbers, the so-called zeroing constants (ZC(i) ) of the form:
ZC(1) (t1,1, t2,1, t3,1,..., tn,1, tn1,1), t1,1 1, m1 1; ZC(2) (0, t2,2 , t3,2 ,..., tn,2 , tn1,2 ), t2,2 1, m2 1;
ZC(3) (0, 0, t3,3,..., tn,3 , tn1,3 ), t3,3 1, m3 1;
ZC(n) (0, 0,..., 0, tn,n , tn1,n ), tn,n 1, mn 1.
A
A A(0) (a1(0) , a2(0) ,...ai(0) , ai(01) ,...an(0) , an(0)1) Next, the initial checked number: is successively reduced to the form A(H) , that is,
ZC(i) (0, 0,..., 0, ti,i , ti1,i ,..., tn,i , tn1,i ), ti,i 1, mi 1; (2) and so on.
A A(0) (a1(0) , a2(0) ,...ai(0) , ai(01) ,...an(0) , an(0)1)
A(1) (0, a2(1) , a3(1) ,..., an(1) , an(1)1), A(2) (0, 0, a3(2) ,..., an(2) , an(2)1),
A(3) (0, 0, 0, a4(3) ,..., an(3) , an(3)1)
Repeating the subtraction n times we get the value A(H ) (0, 0,..., 0, an(n)1) , or A(H ) (0, 0,..., 0, n1) , where n1 an(n)1 . The general scheme of subtraction А(i) А(i1) ZC(i) involving zeroing constants (2) is presented in the following form: where: (i-1) ,..., an(i-1) , an(i-11) )
A(i-1) (0, 0,..., 0, ai(i-1) , ai1
ZC(i) (0, 0,..., 0, ai(i-1) ,ti1,i ,..., tn,i , tn1,i ) A(i) [0,..., 0,[ai(i-1) ai(i-1) ]mod mi , [ai(i-11) - ti1,i ]mod mi1,..., [an(i-11) tn1,i ]mod mn1],
ai(i)1 (ai(i-11) tt1,i ) mod mi1.
Denoting the sampling time ZC from the corresponding zeroing block (ZB) CSC as t1 , and the subtraction time from the number А(i1) of constant ZCi , that is, performing operation А(i) А(i1) ZC(i) – after t2 , we get the total time for performing the operation of zeroing in the form Т Н1 n(t1 t2 ) . When presenting ZB in the tabular form, we can assume that practically t1 t2 add . In this case, the zeroing time is equal to the value Т Н1 2n add , where: add – subtraction time from number А(i1) of zeroing constant КН (i) ; n – number of information bases of MNS.
Stage 2. After finding the value n1 in the first step, the second stage compares n1 with zero. If n1 0 (number A is in range [0, M)), then the conclusion is drawn that the number A
is not distorted (correct), i.e. there are no errors. If n1 0 (number A isn’t in range [0, M) ), then the conclusion is drawn that the number A is distorted (wrong), i.e. there is an error on one of the bases (modules) mi of MNS. Total time Т1 of error detection is defined as T1 TZ1 Тс1 , where Тс1 – time of comparing n1 with zero. Practically time Тс1 comparison is performed in one clock cycle, in this case it can be assumed that T1 TZ1 2n add .
The essence of the method of information error detection in MNS proposed in the article is based on the implementation of the procedure of pair number zeroing with preliminary selection of digits (PNZPSD). The PNZPSD procedure is that the zeroing operation in the ZB is combined in time with the BZC selection operation by digits аі(i1) and аn(iі1)1 of number А(i1) of the constant ZC(i) and creation operation on values аі(i1) and аn(iі1)1 of numbers ai(i)1 and an(i-)i . At the same time, the subtraction operation from the number А(i1) of the zeroing constant ZC(i) (i.e., operation А(i1) ZC(і) ) and the operation of selecting the next zeroing constant:
ZC(i1) (0,, 0, ti1,i1, ti2,i1,, tn1,i1, 0,0, tn1,i1) .
According to the values of ai(i)1 and an(i-)i in the next stage of zeroing, on the bases of mi1 and mni , we will refer to the BZC for the next zeroing constant:
ZC(i1) (0,, 0, ti1,i1, ti2,i1, ..., tn1,i1, 0,0, tn1,i1) .
Indeed, the values of аi1 and аni , which will be subtracted from ai(i)1 and an(i)i , respectively, in order to obtain ai(i11) and an(ii1)1 , are determined only by the values of аі(i1) and аn(iі1)1 . The number of clock cycles that are free from addition, during which the reference is made to the BZC CSC and the formation of the next address is equal to the value n 1 / 2 , ([x] is the integer closest to x, but not exceeding it). At the same time, zeroing is carried out simultaneously on two information bases of MNS a1, an ; a2 , an1 , etc. After every two subtractions, one additional time step is required to form the next address and access the accumulator of zeroing constants. In this regard, for every two addition clock cycles ( add 0 ) there is one clock cycle that is free from addition. Let's compare the effectiveness of the method of error detection in the MNS proposed in the article with the existing method based on the procedure of ordinary zeroing.
To quantify the effectiveness of the proposed method, we introduce the notion of an efficiency coefficient:
K (jne)f TZ1 add TZj add 100%
TZ1 add where j – number of the zeroing method ( j 2 , for pairwise zeroing; j 3 , for pairwise zeroing with prefetching of digits; j 4 , for pairwise number zeroing with prefetching of digits).
Expression (3) can also be represented in the form (4): In accordance with the expression (4), we define the quantitative value K (jne)f for j 2, 4 while n 4 , n 6 , n 8 , n 10 and n 16 , i.e. for l-byte machine words ( l 1, 2, 3, 4, 8 ) of CSC.
The resulting calculated data will be placed in Table 1.
K (jne)f TZ1 - TZj 100% .
TZ1 (3) (4) l(n) Kef K (enf) ,[%] 1(4) 62 3(8) 62 4(10) 65 8(16) 62 mation bases of the MNS n 1,16 provides a range of representation of numbers in modern CSC, which makes it possible to use the data obtained when designing them.
Here is an example of a specific technical implementation of the error detection operation in the CSC, which functions in the MNS. Let MNS be given by the bases m1 3 , m2 4 , m3 5 , m4 7 , m5 11 (n 4) , i.e. one-byte (l = 1) CSC is considered.
In this case, the working numerical range is: and the full range is:
Suppose it is necessary to carry out a control (check the fact of presence or absence of an error) of the number:
A A(0) (a1(0) , a2(0) , a3(0) , a4(0) , a5(0) ) (1, 0, 0,1, 4) ,
ZC(1) t1,1, t2,1, t3,1, t4,1, t5,1 , where t1,1 a1(0) 1 and t4,1 a(40) 1 . In this case with ZB we choose ZC(1) 1,1,1,1,1 , Table 3.
Further, in accordance with the proposed method of PNZPSD, we perform an operation А(1) А(0) ZC(1) : and, simultaneously, for number: with ZB we choose:
ZC(2) 0, t2,2 , t3,2 , 0, t5,2 , of form a2(1) t2,2 3 and a3(1) t3,2 4 . In this case (see Table 4) ZC(2) is defined as:
А(0) 1, 0, 0,1, 4 ZC(1) 1, 1, 1, 1, 1
A1 0, 3, 4, 0, 3 А(1) 0, 3, 4, 0, 3 ZC(2) 0, 3, 4, 0, 3 .
А(1) 0, 3, 4, 0,3 ZC(2) 0, 3, 4, 0,3
A(2) 0, 0, 0, 0, 0.
Next, we define the difference А(1) ZC (2) :
A(2) A(Z ) (0, 0,..., 0,..., 0, n1) (0, 0, 0, 0, 5 ), where 5 0 . Conclusion: the number А(0) 1, 0, 0,1, 4 has no errors (see Table 2).
Verification: the number А(0) in the PNS is А(0) 400 , i.e. is within the working numerical range [0, 419). In the modern world rapid growth of volumes of information and increase in complexity of the set scientific and technical tasks, connected with achievement of appropriate level of quality and reliability of transmitted data is observed. Therefore, the main objective of scientists in the field is development of theoretical bases for construction of high-speed and reliable CSC.
In PNS the problem of increase in reliability and productivity can't be effectively solved without deterioration some key technical and economic indicators of CSC. At the same time, there are positive results of researches which have shown efficiency of application of MNS for increase in speed of realization of integer arithmetic operations, reduction of time of error detection and as a result increase the productivity and reliability of CSC. The methodological basis for building a CSC in the MNS involves a comprehensive solution to the problem of increasing the productivity and integrity of the processing of integer data, as well as providing information security, impedance, performance and durability of the functioning of CSC. Existing data comparison method in MNS don't provide the maximum accuracy of comparison of numbers. Thus, there is a problem of improvement of a method of the fast comparison of data based on the application of the zeroing procedure.
It is known that considerable time of control of data reduces overall effectiveness of application of CSC in MNS, at realization of integer arithmetic and other modular operations. Results of a research of control methods of the data in MNS which are carried out in article have shown that the existing control methods of data in MNS based on use of application of the zeroing procedure reduce control time.
Applications of this method provides obtaining reliable result of control of data in MNS. By the accuracy of the control data in the MNS, we understand the probability of obtaining the true result of the control operation data presented in the MNS.
The essence of the method of error control is to use the procedure of pair number zeroing with the preliminary selection of digits. This makes it possible to increase the efficiency of the procedure for data zeroing in comparison with other control methods up to 30%. The practical significance of the results obtained is that, in comparison with the existing methods of error control in MNS, the error detection time is more than halved. This circumstance makes it possible to increase the overall efficiency of the use of MNS in the creation of CSC [19-24]. 18. Kasianchuk, M., Yakymenko, I., Pazdriy, I., Zastavnyy, O.: Algorithms of findings of perfect shape modules of remaining classes system. In: The Experience of Designing and Application of CAD Systems in Microelectronics. IEEE (2015) 19. Chornei, R.K., Daduna V.M., H., Knopov, P.S.: Controlled Markov Fields with Finite State Space on Graphs. Stochastic Models. 21, 847–874 (2005). doi:10.1080/15326340500294520 20. Ponochovniy, Y., Bulba, E., Yanko, A., Hozbenko, E.: Influence of diagnostics errors on safety: Indicators and requirements. In: 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT). IEEE (2018). doi:10.1109/dessert.2018.8409098 21. Runovski, K., Schmeisser, H.: On the convergence of fourier means and interpolation means. Journal of Computational Analysis and Applications. 6(3), 211-227 (2004) 22. Tkach, B.P., Urmancheva, L.B.: Numerical-analytic method for finding solutions of systems with distributed parameters and integral condition. Nonlinear Oscillations. 12, 113– 122 (2009). doi:10.1007/s11072-009-0064-6 23. Bondarenko, S., Liliya, B., Oksana, K., & Inna, G.: Modelling instruments in risk management. International Journal of Civil Engineering and Technology. 10(1), 1561-1568 (2019) 24. Krasnobayev, V., Koshman, S., Yanko, A., Martynenko, A.: Method of Error Control of the Information Presented in the Modular Number System. In: 2018 International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T). IEEE (2018). doi:10.1109/infocommst.2018.8632049