Error-Correction Coding Using Polynomial Residue Number System
Source abstract
Abstract
There has been a tendency to use the theory of finite Galois fields, or GF(2n), in cryptographic ciphers (AES, Kuznyechik) and digital signal processing (DSP) systems. It is advisable to use modular codes of the polynomial residue number system (PRNS). Modular codes of PRNS are arithmetic codes in which addition, subtraction and multiplication operations are performed in parallel on the bases of the code, which are irreducible polynomials. In this case, the operands are small-bit residues. However, the independence of calculations on the bases of the code and the lack of data exchange between the residues can serve as the basis for constructing codes of PRNS capable of detecting and correcting errors that occur during calculations. The article will consider the principles of constructing redundant codes of the polynomial residue number system. The results of the study of codes of PRNS with minimal redundancy are presented. It is shown that these codes are only able to detect an error in the code combination of PRNS. It is proposed to use two control bases, the use of which allows us to correct an error in any residue of the code combination, in order to increase the error-correction abilities of the code of the polynomial residue number system. Therefore, the development of an algorithm for detecting and correcting errors in the code of the polynomial residue number system, which allows for performing this procedure based on modular operations that are effectively implemented in codes of PRNS, is an urgent task.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Coding theory and cryptography · Cryptography and Residue Arithmetic · Cryptographic Implementations and Security
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Information Security of Automated Systems, North-Caucasus Federal University Stavropol, 1 Pushkina Str., 355017 Stavropol, Russia
Information Technologies, Mathematics and Natural Sciences, Ufa State Petroleum Technological University, 1 Kosmonavtov St., 450064 Ufa, Russia
Stavropol State Pedagogical Institute, 417 Lenina Str., 355009 Stavropol, Russia
Funding
Russian Foundation for Basic Research
References (65)
Show source-provided references
1. Szabo, N.S., and Tanaka, R.I. (1967). Residue Arithmetic and Its Applications to Computer Technology, Mc-Graw Hill.
2. Mohan, P.V. (2002). Residue Number Systems. Algorithms and Architectures, Springer.10.1007/978-1-4615-0997-4 ↗
3. Omondi, A., and Premkumar, B. (2007). Residue Number Systems: Theory and Implementation, Imperial College.10.1142/9781860948671 ↗
4. Mohan, A. (2016). Residue Number Systems. Theory and Applications, Springer International Publishing.10.1007/978-3-319-41385-3 ↗
5. A unifying approach for weighted and diminished-1 modulo (2n + 1) addition
6. Fast Parallel-Prefix Architectures for Modulo 2n − 1 Addition with a Single Representation of Zero10.1109/TC.2007.70750 ↗
7. Improved Area-Efficient Weighted Modulo 2n + 1 Adder Design With Simple Correction Schemes
8. Bajard, J.-C., Eynard, J., and Gandino, F. (2013, January 7–10). Fault Detection in RNS Montgomery Modular Multiplication. Proceedings of the 2013 IEEE 21st Symposium on Computer Arithmetic, Austin, TX, USA.10.1109/ARITH.2013.31 ↗
9. An Algorithmic and Architectural Study on Montgomery Exponentiation in RNS10.1109/TC.2012.84 ↗
10. Efficient Word Size Modular Arithmetic10.1109/TETC.2021.3073475 ↗
11. Shahana, T.K., Jose, B.R., James, R.K., Jacob, K.P., and Sasi, S. (2008, January 12–14). RRNS-Convolutional encoded concatenated code for OFDM based wireless communication. Proceedings of the 2008 16th IEEE International Conference on Networks, New Delhi, India.10.1109/ICON.2008.4772571 ↗
12. Albicocco, P., Cardarilli, G.C., Nannarelli, A., and Re, M. (2014, January 10–12). Twenty years of research on RNS for DSP: Lessons learned and future perspectives. Proceedings of the 2014 International Symposium on Integrated Circuits (ISIC), Singapore.10.1109/ISICIR.2014.7029575 ↗
13. Khalifa, M.A., Emam, A.E., and Youssef, M.I. (2020, January 7–9). A Comparative Study for RNS Coding Scheme Performance in OFDM and SC-FDMA Systems. Proceedings of the 2020 12th International Conference on Electrical Engineering (ICEENG), Cairo, Egypt.10.1109/ICEENG45378.2020.9171754 ↗
14. VLSI implementation of residue number system based efficient digital signal processor architecture for wireless sensor nodes
15. Design Space Exploration based Methodology for Residue Number System Digital Filters Implementation10.1109/TETC.2020.2997067 ↗
16. An approach for fixed coefficient RNS-based FIR filter
17. Simplified fault-tolerant FIR filter architecture based on redundant residue number system10.1049/el.2014.3508 ↗
18. Bernocchi, G.L., Cardarilli, G.C., Re, A.D., Nannarelli, A., and Re, M. (2007, January 27–30). Low-power adaptive filter based on RNS components. Proceedings of the 2007 IEEE International Symposium on Circuits and Systems, New Orleans, LA, USA.10.1109/ISCAS.2007.378155 ↗
19. Efficient Techniques for FIR Filter Designing
20. High Speed and Area Efficient Pipelined Distributed Arithmetic Technique based Adaptive Filter
21. Technique to Adjust Adaptive Digital Filter Coefficients in Residue Number System Based Filters10.1109/ACCESS.2021.3085704 ↗
22. Olsen, E.B. (2018, January 27–30). RNS Hardware Matrix Multiplier for High Precision Neural Network Acceleration: “RNS TPU”. Proceedings of the 2018 IEEE International Symposium on Circuits and Systems (ISCAS), Florence, Italy.10.1109/ISCAS.2018.8351352 ↗
23. Nakahara, H., and Sasao, T. (2018, January 27–30). A High-speed Low-power Deep Neural Network on an FPGA based on the Nested RNS: Applied to an Object Detector. Proceedings of the 2018 IEEE International Symposium on Circuits and Systems (ISCAS), Florence, Italy.10.1109/ISCAS.2018.8351850 ↗
24. Salamat, S., Imani, M., Gupta, S., and Rosing, T. (2018, January 7–9). RNSnet: In-Memory Neural Network Acceleration Using Residue Number System. Proceedings of the 2018 IEEE International Conference on Rebooting Computing (ICRC), McLean, VA, USA.10.1109/ICRC.2018.8638592 ↗
25. Ciet, M., Neve, M., Peeters, E., and Quisquater, J.-J. (2003, January 27–30). Parallel FPGA implementation of RSA with residue number systems—Can side-channel threats be avoided?. Proceedings of the 2003 46th Midwest Symposium on Circuits and Systems, Cairo, Egypt.
26. Practical Evaluation of Protected Residue Number System Scalar Multiplication10.46586/tches.v2019.i1.259-282 ↗
27. Noordam, L. (2019). VHDL Implementation of 4096-bit RNS Montgomery Modular Exponentiation for RSA Encryption. TU Delft Electr. Eng. Math. Comput. Sci.
28. Wu, T. (2020). WITHDRAWN: Fast RNS elliptic curve point multiplication on FPGAs. Microprocess. Microsyst.10.1016/j.micpro.2020.103442 ↗
29. Leelavathi, G., Shaila, K., and Venugopal, K.R. (2016, January 22–25). Elliptic Curve Cryptography implementation on FPGA using Montgomery multiplication for equal key and data size over GF(2m) for Wireless Sensor Networks. Proceedings of the 2016 IEEE Region 10 Conference (TENCON), Singapore.10.1109/TENCON.2016.7848043 ↗
30. A Fault Tolerant Scheme for Detecting Overflow in Residue Number Microprocessors
31. Tay, T.F., and Chang, C.-H. (2017). Fault-Tolerant Computing in Redundant Residue Number System. Embedded Systems Design with Special Arithmetic and Number Systems, Springer.10.1007/978-3-319-49742-6_4 ↗
32. Popov, D.I., and Gapochkin, A.V. (2018, January 9–16). Development of Algorithm for Control and Correction of Errors of Digital Signals, Represented in System of Residual Classes. Proceedings of the 2018 International Russian Automation Conference (RusAutoCon), Sochi, Russia.10.1109/RUSAUTOCON.2018.8501826 ↗
33. A Novel Exploitation of Errors in Redundant Residue Number System Architecture10.3844/ajassp.2021.96.106 ↗
34. A method of paired zeroing of numbers in a residue system10.1088/1742-6596/1333/2/022015 ↗
35. Pontarelli, S., Cardarilli, G.C., Re, M., and Salsano, A. (2008, January 1–3). A Novel Error Detection and Correction Technique for RNS Based FIR Filters. Proceedings of the 2008 IEEE International Symposium on Defect and Fault Tolerance of VLSI Systems, Cambridge, MA, USA.10.1109/DFT.2008.32 ↗
36. Fault Tolerant Parallel Filters Based on Error Correction Codes10.1109/TVLSI.2014.2308322 ↗
37. Redundant Modular Codes for Development of Fault-Tolerant Systems of Satellite Identification10.30534/ijeter/2020/47872020 ↗
38. Increasing the Data Transmission Robustness in Wsn Using the Modified Error Correction Codes on Residue Number System10.5755/j01.eee.21.1.6657 ↗
39. 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, VIC, Australia.10.1109/ISCAS.2014.6865493 ↗
40. Tang, Y., Boutillon, E., Jégo, C., and Jézéquel, 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.
41. The Huffman’s Method of Secured Data Encoding and Error Correction using Residue Number System (RNS)10.5120/cae2015651844 ↗
42. Zhu, D., and Natarajan, B. (2010, January 21–23). Residue number system arithmetic inspired hopping pilot pattern design for cellular downlink OFDMA. Proceedings of the 2010 Wireless Telecommunications Symposium (WTS), Tampa, FL, USA.10.1109/WTS.2010.5479666 ↗
43. Generalised fault-tolerant stored-unibit-transfer residue number system multiplier for moduli set {2n − 1, 2n, 2n + 1}10.1049/iet-cdt.2011.0075 ↗
44. Multiple Bits Error Detection and Correction in RRNS Architecture using the MRC and HD Techniques
45. James, J., and Pe, A. (2015, January 10–11). Error correction based on redundant Residue Number System. Proceedings of the 2015 IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT), Bangalore, India.10.1109/CONECCT.2015.7383940 ↗
46. On the polynomial residue number system (digital signal processing)10.1109/78.80821 ↗
47. Polynomial residue complex signal processing10.1109/82.227375 ↗
48. A new interpretation of “polynomial residue number system”10.1109/78.301857 ↗
49. Paliouras, V., Skavantzos, A., and Stouraitis, T. (2002, January 18). Multi-voltage low power convolvers using the polynomial residue number system. Proceedings of the GLSVLSI ’02: Proceedings of the 12th ACM Great Lakes Symposium on VLSI, New York, NY, USA.10.1145/505307.505309 ↗
50. The multipolynomial channel polynomial residue arithmetic system10.1109/82.752946 ↗
51. Parallel modular technologies in digital signal processing
52. Chu, J., and Benaissa, M. (December, January 30). GF(2m) multiplier using Polynomial Residue Number System. Proceedings of the APCCAS 2008—2008 IEEE Asia Pacific Conference on Circuits and Systems, Macao, China.10.1109/APCCAS.2008.4746320 ↗
53. Kalimoldayev, M., Tynymbaev, S., Magzom, M., Ibraimov, M., Khokhlov, S., Abisheva, A., and Sydorenko, V. (2021, January 15). Polynomials Multiplier under Irreducible Polynomial Module for High-Performance Cryptographic Hardware Tools. Available online: http://ceur-ws.org/Vol-2393/paper_363.pdf.
54. Matrix multiplier of polynomials modulo analysis starting with the lower order digits of the multiplier
55. The device for multiplying polynomials modulo an irreducible polynomial
56. Biyashev, R.G., Nyssanbayeva, S.E., Begimbayeva, Y.Y., and Magzom, M.M. (2015, January 15–17). Modification of the cryptographic algorithms, developed on the basis of nonpositional polynomial notations. Proceedings of the International Conference on Circuits, Systems, Signal Processing, Communications and Computers (CSSCC 2015), Vienna, Austria.
57. Security analysis of an encryption scheme based on nonpositional polynomial notations10.1515/eng-2016-0034 ↗
58. Biyashev, R., Nyssanbayeva, S., and Kapalova, N. (2014). Secret Keys for Nonpositional Cryptosystems. Development, Investigation and Implementation, Lambert Academic Publishing.
59. Very small FPGA application-specific instruction processor for AES10.1109/TCSI.2006.875179 ↗
60. A highly regular and scalable AES hardware architecture10.1109/TC.2003.1190589 ↗
61. Hodjat, A., and Verbauwhede, I. (2004). Minimum area cost for a 30 to 70 Gbits/s AES processor. IEEE Comput. Soc. Annu. Symp. VLSI, 83–88.10.1109/ISVLSI.2004.1339512 ↗
62. Controlling and Restoring the Integrity of Multi-Dimensional Data Arrays through Cryptocode Constructs10.1134/S0361768821060049 ↗
63. A method of providing the integrity of information in the group of robotic engineering complexes based on crypt-code constructions10.3103/S0146411617080181 ↗
64. Sum-Rank BCH Codes and Cyclic-Skew-Cyclic Codes10.1109/TIT.2021.3088712 ↗
65. On Two Classes of Primitive BCH Codes and Some Related Codes10.1109/TIT.2018.2883615 ↗