Multiple Error Correction in Redundant Residue Number Systems: A Modified Modular Projection Method with Maximum Likelihood Decoding
Source abstract
Abstract
Error detection and correction codes based on redundant residue number systems are powerful tools to control and correct arithmetic processing and data transmission errors. Decoding the magnitude and location of a multiple error is a complex computational problem: it requires verifying a huge number of different possible combinations of erroneous residual digit positions in the error localization stage. This paper proposes a modified correcting method based on calculating the approximate weighted characteristics of modular projections. The new procedure for correcting errors and restoring numbers in a weighted number system involves the Chinese Remainder Theorem with fractions. This approach calculates the rank of each modular projection efficiently. The ranks are used to calculate the Hamming distances. The new method speeds up the procedure for correcting multiple errors and restoring numbers in weighted form by an average of 18% compared to state-of-the-art analogs.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Data Storage Technologies · Cryptography and Residue Arithmetic · Parallel Computing and Optimization Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
North Caucasus Center for Mathematical Research, North-Caucasus Federal University, 355017 Stavropol, Russia
Institute for System Programming of the Russian Academy of Sciences, 109004 Moscow, Russia
Computing Platform Lab, Samsung Advanced Institute of Technology, Suwon 16678, Korea
Computer Science Department, CICESE Research Center, Ensenada 22860, Mexico
School of Electrical Engineering and Computer Science, South Ural State University, 454080 Chelyabinsk, Russia
Department of Information Security, Le Quy Don Technical University, Hanoi 11917, Vietnam
Computer Science Department, National Research University “MPEI”, 111250 Moscow, Russia
Funding
Ministry of Science and Higher Education · Russian Foundation for Basic Research · Russian Federation President Grant
References (35)
Show source-provided references
1. Spark: Cluster computing with working sets
2. Li, W., Yang, Y., and Yuan, D. (2011, January 12–14). A Novel Cost-Effective Dynamic Data Replication Strategy for Reliability in Cloud Data Centres. Proceedings of the 2011 IEEE Ninth International Conference on Dependable, Autonomic and Secure Computing, Sydney, NSW, Australia.10.1109/DASC.2011.95 ↗
3. Huang, C., Simitci, H., Xu, Y., Ogus, A., Calder, B., Gopalan, P., Li, J., and Yekhanin, S. (2012, January 13–15). Erasure coding in windows azure storage. Proceedings of the 2012 USENIX Annual Technical Conference (USENIXATC 12), Boston, MA, USA.
4. Sathiamoorthy, M., Asteris, M., Papailiopoulos, D., Dimakis, A.G., Vadali, R., Chen, S., and Borthakur, D. (2013). XORing Elephants: Novel Erasure Codes for Big Data. arXiv.10.14778/2535573.2488339 ↗
5. Muralidhar, S., Lloyd, W., Roy, S., Hill, C., Lin, E., Liu, W., Pan, S., Shankar, S., Sivakumar, V., and Tang, L. (2014, January 6–8). f4: Facebook’s Warm BLOB Storage System. Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), Broomfield, CO, USA.
6. Goh, V.T., Tinauli, M., and Siddiqi, M.U. (2004, January 7). A novel error correction scheme based on the Chinese remainder theorem. Proceedings of the Ninth International Conference on Communications Systems, ICCS 2004, Singapore.
7. Ding, C., Pei, D., and Salomaa, A. (1996). Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography, World Scientific.10.1142/9789812779380 ↗
8. Wicker, S.B., and Bhargava, V.K. (1999). Reed-Solomon Codes and Their Applications, John Wiley & Sons.10.1109/9780470546345 ↗
9. Efficient dispersal of information for security, load balancing, and fault tolerance10.1145/62044.62050 ↗
10. Kshemkalyani, A.D., and Singhal, M. (2011). Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press.
11. Tel, G. (2000). Introduction to Distributed Algorithms, Cambridge University Press.10.1017/CBO9781139168724 ↗
12. Distributed systems principles and paradigms
13. Gentry, C., Halevi, S., and Smart, N.P. (2012, January 15–19). Fully Homomorphic Encryption with Polylog Overhead. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK.10.1007/978-3-642-29011-4_28 ↗
14. A coding theory approach to error control in redundant residue number systems. II. Multiple error detection and correction10.1109/82.204107 ↗
15. Tay, T.F., and Chang, C.-H. (2014, January 1–5). A new algorithm for single residue digit error correction in Redundant Residue Number System. Proceedings of the 2014 IEEE International Symposium on Circuits and Systems (ISCAS), Melbourne, Australia.10.1109/ISCAS.2014.6865493 ↗
16. Error Correction in Redundant Residue Number Systems10.1109/T-C.1973.223594 ↗
17. Error Correcting Properties of Redundant Residue Number Systems10.1109/T-C.1973.223711 ↗
18. The architecture of a fault-tolerant modular neurocomputer based on modular number projections10.1016/j.neucom.2017.06.063 ↗
19. Multiple error detection and correction based on redundant residue number systems10.1109/TCOMM.2008.050401 ↗
20. Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem10.1080/00207160.2016.1247439 ↗
21. An improved residue number system digital-to-analog converter10.1109/TCS.1983.1085311 ↗
22. Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue Decoding
23. Tang, Y., Boutillon, E., Jego, C., and Jezequel, M. (2010, January 26–28). A new single-error correction scheme based on self-diagnosis residue number arithmetic. Proceedings of the 2010 Conference on Design and Architectures for Signal and Image Processing (DASIP), Edinburgh, UK.
24. Scalable Data Storage Design for Nonstationary IoT Environment with Adaptive Security and Reliability10.1109/JIOT.2020.2981276 ↗
25. Yin, P., and Li, L. (2013, January 15–17). A new algorithm for single error correction in RRNS. Proceedings of the 2013 International Conference on Communications, Circuits and Systems (ICCCAS), Chengdu, China.10.1109/ICCCAS.2013.6765313 ↗
26. Goldreich, O., Ron, D., and Sudan, M. (1999, January 1–4). Chinese remaindering with errors. Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, Georgia.10.1145/301250.301309 ↗
27. On a class of arithmetic codes and a decoding algorithm (Corresp.)10.1109/TIT.1976.1055504 ↗
28. Self-checking properties of residue number error checkers based on mixed radix conversion10.1109/31.1717 ↗
29. Algorithm for constructing modular projections for correcting multiple errors based on a redundant residue number system using maximum likelihood decoding10.1134/S0361768821080089 ↗
30. Nazarov, A., Babenko, M., and Golimblevskaia, E. (2020, January 25–26). Efficient Hardware Implementation of forward Conversion WNS-RNS on FPGA. Proceedings of the 2020 International Conference Engineering and Telecommunication (En & T), Dolgoprudny, Russia.10.1109/EnT50437.2020.9431304 ↗
31. Nazarov, A., Babenko, M., and Golimblevskaia, E. (2020, January 25–26). Hardware Implementation of the Reverse Conversion RNS-WNS on FPGA. Proceedings of the 2020 International Conference Engineering and Telecommunication (En & T), Dolgoprudny, Russia.10.1109/EnT50437.2020.9431249 ↗
32. Ananda Mohan, P.V. (2016). Residue Number Systems: Theory and Applications, Birghauser Math.10.1007/978-3-319-41385-3 ↗
33. Omondi, A.R., and Premkumar, A.B. (2007). Residue Number Systems: Theory and Implementation, World Scientific.10.1142/9781860948671 ↗
34. Menezes, A.J., Van Oorschot, P.C., and Vanstone, S.A. (2018). Handbook of Applied Cryptography, CRC Press.10.1201/9781439821916 ↗
35. Reliability improvement of information systems by residue number system code