THE CONCEPT OF PERFORMING THE ADDITION OPERATION IN THE SYSTEM OF RESIDUAL CLASSES
Article Sidebar
Main Article Content
Abstract
The subject of the article is the development of a method for implementing the arithmetic operation of adding the residuals of numbers, which are represented in the system of residual classes (RNS). This method is based on the use of positional binary adders. The purpose of the article is to improve the performance of computer systems (CS) and their components by introducing new ways of organizing calculations based on the use of RNS. Tasks: to analyze and identify the shortcomings of the existing number systems that are used in the construction of computer systems and components; explore possible ways to eliminate the identified deficiencies; explore the structure of binary positional adders, taking into account the scheme for adding two residues of numbers modulo RNS; to develop a method for constructing adders modulo RNS, which is based on the use of a set of binary single-digit positional adders. Research methods: methods of analysis and synthesis of computer systems, number theory, coding theory in RNS. The following results are obtained. The paper shows that one of the promising ways to improve the performance of the CS is the use of RNS. The mathematical basis of RNS is the Chinese remainder theorem, which states that an integer operation on one large modulus can be replaced by a set of operations on coprime small modules. This opens up broad prospects for optimizing calculations. On the one hand, it is possible to significantly simplify the performance of complex and cumbersome calculations, including on low-resource computing platforms. On the other hand, calculations for different modules can be performed in parallel, which increases the performance of the CS. Conclusions. The article considers the operation of adding two numbers. This operation is the basis for both traditional positional number systems and RNS, i.e. forms the computational basis of all existing CS components. A new method for calculating the sum of the residuals of numbers modulo an arbitrary is proposed, and examples are given that clearly demonstrate the effectiveness of the proposed method. This method can be used in various computer applications, including for improving computing performance, ensuring fault tolerance, etc.
Article Details
References
R.S. Alford, "Computer Systems Engineering Management", CRC Press, 2018. https://doi.org/10.1201/9781351070829.
P.V. Ananda Mohan, "Residue Number Systems", Springer International Publishing, Cham, 2016. https://doi.org/10.1007/978-3-319-41385-3.
P.V. Mohan, CDAC, Bangalore, "Implementation of Residue Number System Based Digital Filters", A Quarterly Publication of ACCS, (n.d.). https://journal.accsindia.org/implementation-of-residue-number-system-based-digital-filters/ (accessed August 16, 2020).
J.O. Tuazon, "Residue number system in computer arithmetic", Doctor of Philosophy, Iowa State University, Digital Repository, 1969. https://doi.org/10.31274/rtd-180816-2270.
F. Barsi, P. Maestrini, "Error Correcting Properties of Redundant Residue Number Systems", IEEE Transactions on Computers. (1973) 307–315. https://doi.org/10.1109/T-C.1973.223711.
M.G. Arnold, "The residue logarithmic number system: theory and implementation", in: 17th IEEE Symposium on Computer Arithmetic (ARITH’05), 2005: pp. 196–205. https://doi.org/10.1109/ARITH.2005.44.
M.Z. Garaev, A.A. Karatsuba, "The representation of residue classes by products of small integers", Proceedings of the Edinburgh Mathematical Society. 50 (2007) 363–375. https://doi.org/10.1017/S0013091505000969.
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.
P.V. Ananda Mohan, "Error Detection, Correction and Fault Tolerance in RNS-Based Designs", in: P.V. A. Mohan (Ed.), Residue Number Systems: Theory and Applications, Springer International Publishing, Cham, 2016: pp. 163–175. https://doi.org/10.1007/978-3-319-41385-3_7.
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.
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.
V. Krasnobayev, A. Kuznetsov, A. Yanko, K. Kuznetsova, "Correction Codes in the System of Residual Classes", in: 2019 IEEE International Scientific-Practical Conference Problems of Infocommunications, Science and Technology (PIC&ST), 2019: pp. 488–492. https://doi.org/10.1109/PICST47496.2019.9061253.
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.
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.
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.
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.