METHODS FOR TABULAR IMPLEMENTATION OF ARITHMETIC OPERATIONS OF THE RESIDUES OF TWO NUMBERS REPRESENTED IN THE SYSTEM OF RESIDUAL CLASSES
DOI:
https://doi.org/10.15588/1607-3274-2022-4-2Keywords:
modular arithmetic operation, system of residual classes, tabular arithmetic, tabular multiplication codeAbstract
Context. Implementation of modular arithmetic operations of addition, subtraction and multiplication by a tabular method based on the use of the tabular multiplication code. The object of the study is the process of tabular implementation of basic arithmetic operations on the residues of numbers represented in the system of residual classes.
Objective. The goal of the work is to develop methods for the tabular implementation of the arithmetic operations of multiplication, addition and subtraction of the residues of two numbers based on the use of the tabular multiplication code.
Method. Tabular methods for implementing integer arithmetic modular operations of addition, subtraction and multiplication are proposed for consideration. In order to reduce the amount of equipment for a tabular operating unit of computer systems that implements modular operations of addition, subtraction and multiplication by reducing the coincidence circuits AND in the nodes of the tables for implementing arithmetic operations based on the code of table multiplication, two methods for performing arithmetic modular operations of addition and subtraction have been developed. These methods are based on the code of tabular multiplication, the use of which will reduce the amount of equipment of the tabular operating unit. Thus, despite the difference in the digital structure of the tables of modular operations of addition, subtraction and multiplication based on the use of the tabular multiplication code, two new tabular methods for implementing arithmetic modular operations of addition and subtraction have been created. Based on them, algorithms for tabular execution of modular arithmetic operations of addition and subtraction have been developed. Using these algorithms, it is possible to synthesize a structurally simple, highly reliable and fast table operating unit that operates in a system of residual classes, which is based on three separate permanent storage devices (read-only memory), each of which implements only one fourth of the corresponding complete table of values of the modular operation, what is earlier in the theory tabular arithmetic was supposed to be impossible.
Results. The developed methods are justified theoretically and studied when performing arithmetic modular operations of addition, subtraction and multiplication using tabular procedures.
Conclusions. The conducted examples of the implementation of integer arithmetic modular operations of addition and subtraction can be considered as presented experiments. The results obtained make it possible to recommend them for use in practice in the design of computer systems operating in a non-positional number system in residual classes. Prospects for further research may be to create a tabular method for implementing integer arithmetic modular division operations based on the use of the tabular multiplication code.
References
Akushskij I. Ya., Yudickij D. I. Mashinnaya arifmetika v ostatochnyx klassax. Mosсow , Sov. radio, 1968, 440 p.
Gérard B., Kammerer J.-G., Merkiche N. Contributions to the Design of Residue Number System Architectures, Proceedings 22nd IEEE International Symposium on Computer Arithmetic. France, 2015, pp. 105–112. DOI: 10.1109/ARITH.2015.25.
Bayoumi M., Jullien G. and Miller W. A VLSI implementation of residue adders, IEEE Transactions on Circuits and Systems, March 1987, Vol. 34, № 3, pp. 284–288. DOI: 10.1109/TCS.1987.1086130
Chao Huang D. Peterson, Rauch H., Teague J. and Fraser D. Implementation of a fast digital processor using the residue number system, IEEE Transactions on Circuits and Systems, January 1981, Vol. 28, No. 1, pp. 32–38. DOI: 10.1109/TCS.1981.1084905.
Ulman Z., Czyzak M. and Zurada J. Effective RNS scaling algorithm with the Chinese remainder theorem decomposition, Proceedings of IEEE Pacific Rim Conference on Communications Computers and Signal Processing, 1993, Vol. 2, pp. 528– 531 DOI: 10.1109/PACRIM.1993.407305.
Gregory R. T., Krishnamurthy E. V. Residue or Modular Arithmetic. In: Methods and Applications of Error-Free Computation, Texts and Monographs in Computer Science. New York, Springer, 1984. DOI: https://doi.org/10.1007/978-1-4612-52429_1
Safari A., Nugent J. and Kong Y. Novel implementation of full adder based scaling in Residue Number Systems, 2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS), 2013, pp. 657–660, DOI: 10.1109/MWSCAS.2013.6674734.
Wei S. Fast signed-digit arithmetic circuits for residue number systems, 2015 IEEE International Conference on Electronics, Circuits, and Systems (ICECS), December, 2015, pp. 344–347. DOI: 10.1109/ICECS.2015.7440319.
Mohan P. V. A. Residue Number Systems: Theory and Applications. Birkhäuser Basel, Springer International Publishing, Switzerland, 2016, 351 p. DOI: 10.1007/978-3-319-41385-3_2 9
Krasnobayev V., Kuznetsov A., Yanko А., Akhmetov B., Kuznetsova T. Processing of the residuals of numbers in real and complex numerical domains, Lecture Notes on Data Engineering and Communications Technologies. Berlin, Springer, 2021, pp. 529–555. DOI: 10.1007/978-3-030-43070-2_24
Piestrak S. J. Design of residue generators and multioperand modular adders using carry-save adders, Proceedings 10th IEEE Symposium on Computer Arithmetic, 26–28 June, 1991, pp. 100–107. DOI: 10.1109/ARITH.1991.145540
Gorbenko I., Hanzia R. Examination and implementation of the fast method for computing the order of elliptic curve, EasternEuropean Journal of Enterprise Technologies, 2017, Vol. 2, No. 9(86), pp. 11–21. DOI: 10.15587/1729-4061.2017.95194
Krasnobayev V., Kuznetsov A., Yanko A., Koshman S., Zamula A. and Kuznetsova T. Data processing in the system of residual classes : monograph, ASC Academic Publishing, 2019, 208 p. ISBN: 978-0-9989826-6-3 (Hardback), ISBN: 978-0-99898267-0 (Ebook).
Szabo N. S., Tanaka R. I. Residue Arithmetic and Its Applications to Computer Technology. New York, McGraw-Hill, 1967, 236 p.
Kazymyrov O., Oliynykov R., Raddum H. Influence of addition modulo 2n on algebraic attacks, Cryptography and Communications, April 2016, Vol. 8, Issue 2, pp. 277–289. DOI: https://doi.org/10.1007/s12095-015-0136-7
Krasnobayev V. A., Yanko A. S., Koshman S. A. Algorithms of data processing in the residual classes system, 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T). Kharkov, 2017, pp. 117–121. DOI: 10.1109/INFOCOMMST.2017.8246363
Arnold M. G. The Residue Logarithmic Number System: Theory and Implementation, 17th IEEE International Symposium on Computer Arithmetic, 2005, pp. 196–205 DOI: 10.1109/ARITH.2005.44
Gavrylenko S. Y., Chelak V. V., Semenov S. G. Development of method for identification the computer system state based on the decision tree with multi-dimensional nodes, Radio Electronics, Computer Science, Control, 2022, No. (2), pp. 113–121. DOI: https://doi.org/10.15588/1607-3274-2022-2-11
Wang Y., Song X., Aboulhamid M., Shen H. Adder based residue to binary number converters for (2/sup n/–1, 2/sup n/, 2/sup n/+1), IEEE Transactions on Signal Processing, July 2002, Vol. 50, № 7, pp. 1772–1779. DOI: 10.1109/TSP.2002.1011216
Wang Wei, Swamy M. N. S., Ahmad M. O., Wang Yuke A study of the residue-to-binary converters for the three-moduli sets, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, Febuary 2003, Vol. 50, No. 2, pp. 235–243. DOI: 10.1109/TCSI.2002.808191
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 V. A. Krasnobayev, A. S. Yanko, D. M. Kovalchuk
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
