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

来源：电子与信息学报杂志2015年第8期北京时间：

作者：肖翰珅, 胡剑浩, 马上

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

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

关键词：信息传输, 编码理论, 中国剩余定理, 冗余余数系统, 纠错检错

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