Low-complexity Error Correction Algorithms for Redundant Residue Number Systems
Xiao Han-shen① Hu Jian-hao② Ma Shang②
①(Department of Mathematics, Tsinghua University, Beijing 100084, China) ②(National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China, Chengdu 611731, China)
Redundant Residue Number System (RRNS) is widely used in communication systems for WLAN (Wireless LAN) and CDMA (Code Division Multiple Access) etc. due to its strong ability to enhance robustness of information in parallel processing environments. Error detection and correction of RRNS is an important guarantee for information reliability in communication systems. The overflow detection theorem, the unique theorem, and the searching theorem are proposed and proved in the paper based on properties of residue classes in finite rings. With the theorems, a single-error-correction algorithm using modular operations with reduced complexity O(k,r) is proposed. The uniqueness test algorithm is proposed. Furthermore, for any general types of errors, the searching multiple-error-correction algorithm is proposed. The computational complexity of the searching multiple-error- correction algorithm is reduced from polynomial order to logarithmic order according to the analysis, and the method can reach the extreme correction capability efficiently with only comparison operations instead of complex modular arithmetic.
Madhukumar A S, Chin F, and Premkumar A B. Incremental redundancy and link adaptation in wireless local area networks using residue number systems[J]. Wireless Personal Communication, 2003, 55(27): 321-336.
[2]
Pham Duc-Minh, Premkumar A B, and Madhukumar A S. Error detection and correction in communication channels using inverse gray RSNS Codes[J]. IEEE Transactions on Communications, 2011, 59(4): 975-986.
[3]
Yang L L and Hanzo L. A residue number system based parallel communication scheme using orthogonal signaling- part I: system outline[J]. IEEE Transactions on Vehicular Technology, 2002, 51(6): 1534-1546.
[4]
Yang L L and Hanzo L. A residue number system based parallel communication scheme using orthogonal signaling- part II: multipath fading channels[J]. IEEE Transactions on Vehicular Technology, 2002, 51(6): 1547-1559.
[5]
Keller T, Liew T H, and Hanzo L. Adaptive redundant residue number system coded multicarrier modulation[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(11): 2292-2301.
[6]
Yang Lie-liang and Hanzo L. Redundant residue number system based error correction codes[C]. IEEE 54th Vehicular Technology Conference, Atlantic, USA, 2001, 3: 1472-1476.
[7]
Krishna H, Lin K Y, and Sun Jenn-dong. A coding theory approach to error control in redundant residue number systems. I. theory and single error correction[J]. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1992, 39(1): 8-17.
[8]
Sun Jenn-dong and Krishna H. A coding theory approach to error control in redundant residue number systems. II. Multiple error detection and correction[J]. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1992, 39(1): 18-34.
[9]
Goldreich O, Ron D, and Sudan M. Chinese remaindering with errors[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1330-1338.
[10]
Mandelbaum D M. On a class of arithmetic codes and a decoding algorithm (Corresp.)[J]. IEEE Transactions on Information Theory, 1976, 22 (1): 85-88.
[11]
Goh V T and Siddiqi M U. Multiple error detection and correction based on redundant residue number systems[J]. IEEE Transactions on Communications, 2008, 56(3): 325-330.
[12]
Lei Li and Hu-Jian-hao. Joint redundant residue number systems and module isolation for mitigating single event multiple bit upsets in datapath[J]. IEEE Transactions on Nuclear Science, 2010, 57(6): 3779-3786.
[13]
Lei Li and Hu-Jian-hao. Redundant residue number systems based radiation gardening for datapath[J]. IEEE Transactions on Nuclear Science, 2010, 57(4): 2332-2343.
[14]
Pontarelli S, Cardarilli G C, Re M, et al.. A novel error detection and correction technique for RNS based FIR filters[C]. IEEE International Symposium on Defect and Fault Tolerance of VLSI Systems (DFTVS), Boston, USA, 2008: 436-444.
