No Access

An Efficient Implementation of the CRT Algorithm Based on an Interval-Index Characteristic and Minimum-Redundancy Residue Code

Faculty of Science & Technology, Jan Dlugosz University in Czestochowa, Armii Krajowej 13/15, Czestochowa, 42-200, Poland

E-mail Address: m.selianinau@ujd.edu.pl

Search for more papers by this author

https://doi.org/10.1142/S0219876220500048Cited by:2 (Source: Crossref)

Abstract

The Chinese remainder theorem (CRT), which appeared in ancient China, is widely used in many modern computer applications. This paper presents the CRT implementation by using the interval-index characteristic and minimum redundancy residue code. The proposed algorithm does not use large modulo addition operations and provides low computational complexity compared to conventional non-redundant RNS. The efficiency factors of using the minimally redundant RNS increase with the number $k$ of non-redundant moduli, asymptotically approaching the threshold $k / 2$ . The new approach presented here will have a significant impact on many non-modular operations in RNS arithmetic, which currently use the CRT.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in finite element methods!

References

Abtahi, M. [2005] “ Core function of an RNS number with no ambiguity,” Comput. Math. Appl. 50, 459–470. Crossref, Web of Science, Google Scholar
Akkal, M. and Siy, P. [2007] “ A new mixed radix conversion algorithm MRC-II,” J. Syst. Archit. 53, 577–586. Crossref, Web of Science, Google Scholar
Akushskii, I. Ya, Burcev, V. M. and Pak, I. T. [1977] “ A new positional characteristic of non-positional codes and its application,” Coding Theory and the Optimization of Complex Systems, Nauka, Alma-Ata, Kazakh. SSR, pp. 8–16. Google Scholar
Akushskii, I. Ya. and Juditskii, D. I. [1968] Machine Arithmetic in Residue Classes (Sov. Radio, Moscow). Google Scholar
Amerbayev, V. M. [1976] Theoretical Foundations of Machine Arithmetic (Nauka, Alma-Ata, Kazakh, SSR). Google Scholar
Aremu, I. A. and Gbolagade, K. A. [2017] “ Redundant residue number system based multiple error detection and correction using Chinese remainder theorem (CRT),” Soft. Eng. 5, 72–80. Crossref, Google Scholar
Burton, D. M. [1980] Elementary Number Theory (Allyn and Bacon, Boston). Google Scholar
Chen, J., Takeyama, T., O-Tani, H. et al. [2019] “ Using high performance computing for liquefaction hazard assessment with statistical soil models,” Int. J. Comput. Methods 16, 1840005. Link, Web of Science, Google Scholar
Chen, X. and Wan, D. [2019] “ Numerical simulation of three-dimensional violent free surface flows by GPU-based MPS method,” Int. J. Comput. Methods 16, 1843012. Link, Web of Science, Google Scholar
Chervyakov, N., Babenko, M., Tschernych, A. et al. [2019] “ AR-RRNS: Configurable reliable distributed data storage systems for Internet of Things to ensure security,” Future Gener. Comput. Syst. 92, 1080–1092. Crossref, Web of Science, Google Scholar
Conte, D., D’Ambrosio, R. and Paternoster, B. [2016] “ GPU-acceleration of waveform relaxation methods for large differential systems,” Numer. Algorithms 71, 293–310. Crossref, Web of Science, Google Scholar
Dimauro, G., Impedovo, S., Modugno, R. et al. [2003] “ Residue-to-binary conversion by the quotient function, IEEE Trans. Circuits Syst. II Analog Digital Signal Process 50, 488–493. Crossref, Google Scholar
Dimauro, G., Impedovo, S. and Pirlo, G. [1992] “ A new magnitude function for fast numbers comparison in the residue number system,” Microprocess. Microprogr. 35, 97–104. Crossref, Web of Science, Google Scholar
Dimauro, G., Impedovo, S., Pirlo, G. and Salzo, A. [2000] “ RNS architectures for the implementation of the ‘diagonal function’,” Inf. Process. Lett. 73, 189–198. Crossref, Web of Science, Google Scholar
Ding, C., Pei, D. and Salomaa, A. [1996] Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography (World Scientific Publishing Co. Inc., River Edge, NJ). Link, Google Scholar
Ferlin, E. P., Lopes, H. S., Lima, C. R. E. and Perretto, M. [2011] “ A FPGA-based reconfigurable architecture for high-performance numerical computation,” J. Circuits Syst. Comput. 20, 849–865. Link, Web of Science, Google Scholar
Goh, V. and Siddiqi, M. U. [2008] “ Multiple error detection and correction based on redundant residue number systems,” IEEE Trans. Commun. 56, 325–330. Crossref, Web of Science, Google Scholar
Gonnella, J. [1991] “ The application of core functions to residue number system,” IEEE Trans. Signal Process. 39, 69–75. Crossref, Web of Science, Google Scholar
Hardy, G. H. and Wright, E. M. [2008] An Introduction to the Theory of Numbers, 6th edition (Oxford University Press, Ely House, London). Crossref, Google Scholar
He, G., Wang, Hu., Huang, G. et al. [2017] “ A parallel elastoplastic reanalysis based on GPU platform,” Int. J. Comput. Methods 14, 1750051. Link, Web of Science, Google Scholar
He, J. and Lei, J. [2019] “ A GPU-accelerated TLSPH algorithm for 3D geometrical nonlinear structural analysis,” Int. J. Comput. Methods 16, 1850114. Link, Web of Science, Google Scholar
Huang, C. H. [1983] “ Fully parallel mixed-radix conversion algorithm for residue number applications,” IEEE Trans. Comput. 32, 398–402. Crossref, Web of Science, Google Scholar
Jenkins, W. K. and Etzel, M. H. [1981] “ Special properties of complement codes for redundant residue number system,” Proc. IEEE 69, 132–133. Crossref, Web of Science, Google Scholar
Knuth, D. E. [1997] The Art of Computer Programming, Seminumerical Algorithms, Vol. 2, 3rd ed. (Addison-Wesley Longman Publishing Co., Boston). Google Scholar
Kolyada, A. A. and Selyaninov, M. Yu. [1986] “ Generation of integral characteristics of symmetric-range residue codes,” Cybern. Syst. Anal. 22, 431–437. Crossref, Google Scholar
Kong, Y., Asif, S. and Khan, M. A. U. [2016] “ Modular multiplication using the core function in the residue number system,” Appl. Algebra Eng. Commun. Comput. 27, 1–16. Crossref, Web of Science, Google Scholar
Lo, H. H. and Lin, T. [2013] “ Parallel algorithms for residue scaling and error correction in residue arithmetic,” Wirel. Eng. Techn. 4, 198–213. Crossref, Google Scholar
Miller, D. D., Altschul, R. E., King, J. R. and Polky, J. N. [1986] “ Analysis of the residue class core function of Akushskii, Burcev, and Pak,” Residue Number System Arithmetic: Modern Applications in Digital Signal Processing (IEEE Press, Piscataway, NJ), pp. 390–401. Google Scholar
Mohan, P. V. A. [2016] Residue Number Systems: Theory and Applications (Springer, Cham, Switzerland). Crossref, Google Scholar
Molahosseini, A., Sousa, L. and Chang, C. H. [2017] Embedded Systems Design with Special Arithmetic and Number Systems (Springer, Cham, Switzerland). Crossref, Google Scholar
Nagel, W. E., Kröner, D. H. and Resch, M. M. [2018] “ High performance computing in science and engineering’17,” Transaction of the High Performance Computing Center, Stuttgart (HLRS) 2017 (Springer, Cham, Switzerland). Crossref, Google Scholar
Nagel, W. E., Kröner, D. H. and Resch, M. M. [2019] “ High performance computing in science and engineering’17,” Transaction of the High Performance Computing Center, Stuttgart (HLRS) 2018 (Springer, Cham, Switzerland). Crossref, Google Scholar
Omondi, A. R. and Premkumar, B. [2007] Residue Number Systems: Theory and Implementation (Imperial College Press, London). Link, Google Scholar
Orlandi, G., Di Claudio, E. and Piazza, F. [1993] “ A systolic redundant residue arithmetic error correction circuit,” IEEE Trans. Comput. 42, 427–432. Crossref, Web of Science, Google Scholar
Pirlo, G. and Impedovo, D. [2013] “ A new class of monotone functions of the residue number system,” Int. J. Math. Models Meth. Appl. Sci. 7, 802–809. Google Scholar
Rao, T. R. N. and Trehan, A. K. [1970] “ Binary logic for residue arithmetic using magnitude index,” IEEE Trans. Comput. 19, 752–757. Crossref, Web of Science, Google Scholar
Sengupta, A. and Natarajan, B. [2014] “ Redundant residue number system based space-time block codes,” Phys. Commun. 12, 1–15. Crossref, Web of Science, Google Scholar
Shenoy, M. A. P. and Kumaresan, R. [1989] “ A fast and accurate RNS scaling technique for high speed signal processing,” IEEE Trans. Acoust. Speech Signal Process. 37, 929–937. Crossref, Google Scholar
Shenoy, A. P. and Kumaresan, R. [1989] “ Fast base extension using a redundant modulus in RNS,” IEEE Trans. Comput. 38, 292–297. Crossref, Web of Science, Google Scholar
Shoup, V. [2005] A Computational Introduction to Number Theory and Algebra, 2nd edition (Cambridge University Press, UK). Crossref, Google Scholar
Soderstrand, M. A., Jenkins, W. K., Jullien, G. A. and Taylor, F. J. [1986] Residue Number System Arithmetic: Modern Applications in Digital Signal Processing (IEEE Press, Piscataway, NJ). Google Scholar
Szabo, N. S. and Tanaka, R. I. [1967] Residue Arithmetic and its Application to Computer Technology (McGraw-Hill, New York). Google Scholar
Tai, L. C. and Chen, C. F. [1984] “ Technical note, Overflow detection in a redundant residue number system,” IEE Proc. E (Comput. Digit. Tech.) 131, 97–98. Crossref, Google Scholar
Tang, Y., Zhou, Z., Shi, X. and Fan, J. [2016] “ Parallel computing of texture-optimization-based flow visualization on CUDA,” Int. J. High Perform. Comput. Netw. 9, 258–270. Crossref, Google Scholar
Tay, T. F. and Chang, C. H. [2016] “ A non-iterative multiple residue digit error detection and correction algorithm in RRNS,” IEEE Trans. Comput. 65, 396–408. Crossref, Web of Science, Google Scholar
Tchernykh, A., Babenko, M., Chervyakov, N. et al. [2018] “ AC-RRNS: Anti-collusion secured data sharing scheme for cloud storage,” Int. J. Approx. Reason. 102, 60–73. Crossref, Web of Science, Google Scholar
Yassine, H. M. and Moore, W. R. [1991] “ Improved mixed-radix conversion for residue number architectures,” IEEE Proc. G — Circuits, Dev. Syst. 138, 120–124. Crossref, Google Scholar
Zhang, Y., Pan, G. and Huang, Q. [2019] “ The implementation of two-dimensional multi-block lattice Boltzmann method on GPU,” Int. J. Comput. Methods 16, 18400002. Link, Web of Science, Google Scholar