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

Low-complexity Error Correction Algorithms for Redundant Residue Number Systems

作　　者：肖翰珅[1] 胡剑浩[2] 马上[2] 

机构地区：[1]清华大学数学科学系,北京100084 [2]电子科技大学通信抗干扰技术国家级重点实验室,成都611731

出　　处：《电子与信息学报》2015年第8期1944-1949,共6页Journal of Electronics & Information Technology

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

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

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

分 类 号：TN919.3[电子电信—通信与信息系统]