冗余余数系统低复杂度快速纠错算法设计

肖翰珅; 胡剑浩; 马上

doi:10.11999/JEIT141454

冗余余数系统低复杂度快速纠错算法设计

doi: 10.11999/JEIT141454

1.
(清华大学数学科学系北京 100084) ②(电子科技大学通信抗干扰技术国家级重点实验室成都 611731)

基金项目:

国家自然科学基金(61101033, 61076096)，国家863计划项目(2011AA010201)，清华大学自主科研计划(20141081231)和国家高科技中央高校基本科研业务费(ZYGX 2011J118)

计量
- 文章访问数: 1419
- HTML全文浏览量: 130
- PDF下载量: 667
- 被引次数: 0
出版历程
- 收稿日期: 2014-11-20
- 修回日期: 2015-04-08
- 刊出日期: 2015-08-19

Low-complexity Error Correction Algorithms for Redundant Residue Number Systems

1.
(Department of Mathematics, Tsinghua University, Beijing 100084, China)
2.
(National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China, Chengdu 611731, China)

摘要

摘要: 余数系统由于具有增强传输信息在并行系统中鲁棒性的优势，已被广泛应用在无线局域网(WLAN)以及码分多址通信技术(CDMA)等领域。而余数系统中的纠错检错是保证传输数据可靠性和高效性的关键问题。该文根据有限环上剩余类的性质提出溢出判定定理，不重复判断定理和唯一性区间搜索定理，并在此基础上进一步提出采用模运算代替传统中国剩余定理进行快速恢复的单错误纠错算法，将复杂度降低为O(k,r)；提出不重复判定纠错算法；并对于一般错误情形，设计通过比较算子实现的搜索纠错算法。其中搜索纠错算法能直接实现系统最大纠错能力，且避免依靠复杂模运算算子实现，系统吞吐率得以提高；与传统算法相比，计算复杂度由多项式级降低至对数级。
- 信息传输 /
- 编码理论 /
- 中国剩余定理 /
- 冗余余数系统 /
- 纠错检错
Abstract: 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 complexityO(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.
- Coding theory /
- Chinese remainder theorem /
- Redundant Residue Number System (RRNS) /
- Error detection and correction /

HTML全文

参考文献(14)

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.

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.

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.

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.

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.

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.

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.

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.

Goldreich O, Ron D, and Sudan M. Chinese remaindering with errors[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1330-1338.

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.

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.

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.

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.

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.

施引文献

资源附件(0)

访问统计