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

肖翰珅 胡剑浩 马 上



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

肖翰珅①胡剑浩*②马 上②

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

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

编码理论；中国剩余定理；冗余余数系统；纠错检错

1 引言

现代通信、雷达、多媒体技术的发展对数字信号处理(Digital Signal Processing, DSP)的要求日益增加。其主要表现在DSP算法复杂度增加的同时要求更高的处理速度、系统吞吐率和可靠性，更低的单位功耗和成本。这些需求在机载、移动和卫星等设备中的数字信号处理芯片设计上表现得尤为突出。研究表明，在未来的集成电路设计里，大规模的并行处理技术将取代传统的串行处理方式，以满足对集成电路处理能力和处理速度日益提高的要求。DSP算法的并行处理目前主要有两个研究领域：一是通过增加处理单元的数量并辅以相关调度机制实现高速大容量的计算和处理，例如用两个解码器并行工作可以使解码速度提高1倍；二是采用并行数值表征系统代替传统的数值表征系统，从算法前端入手解决VLSI的速度、功耗和面积问题。后者利用数值表征系统的并行性，在算法的最前端考虑DSP系统的并行实现，而余数系统(Residue Number System, RNS)就是一个并行数值表征系统。RNS是一个古老的无权重数字表征系统，源于中国剩余定理(Chinese Remainder Theorem, CRT)，它将传统的多位数复杂运算用多个并行的较少位数的简单运算单元来实现；并且在进行乘、加运算时，各通道完全独立，只使用数据的余数表征向量的对应分量进行乘、加运算。这一并行的数值表征计算形式不仅可以有效地降低面积功耗，也决定了余数系统潜在的高速度。由于其高速、低复杂度和低功耗的特性，RNS已被研究证明适用于如无线局域网[1]、码分多址通信技术、卷积和快速傅里叶变换等数字信号处理领域[2]。

冗余余数系统(Redundant Residue Number System, RRNS)通过向余数系统引入冗余的余数基，使得其表征的计算系统具有冗余性。具体体现为RRNS中各运算通道是互为冗余的，而且各通道计算是相互独立的；当部分余数分量出现错误时，该错误不会在各分量间扩散，此时仍可以通过余数分量间的冗余关系获得正确的运算结果。RRNS中所有余数分量(含冗余分量)可以同等地参与数据通道的相关计算和检错、纠错计算，而普通的纠错编码，需要在各级计算后重新进行编译码的操作。作为具有纠错能力的并行数值表征和计算系统，RRNS被广泛应用于正交信号处理[3,4]以及自适应多载波调制[5]等领域。

在现有工作中，基于RRNS的纠错编码一般有以下两种策略。第1种是基于计算余数向量特征值与设定值比对来完成：Yang等人[6]通过迭代增加冗余基，并利用中国剩余定理在低可靠度无线信道中进行数据还原以解决纠错问题；但是由于每一次增加冗余基的操作均需通过CRT还原数据，复杂度较高。文献[7,8]引入Hamming重量以及最小距离概念，提出了通过找出错误位并纠正，最终实现纠错检错的算法。但从文献[7]的单错误纠正算法到文献[8]双错误和单突发错误纠正算法的改进是较复杂的。第2种策略是通过还原数据比对来完成：文献[9]基于连分数以及欧几里得方法[10]，通过冗余校验基和信息基的组合有效地确定了余数向量的错误位，纠正后还原得到正确数据。文献[11]在文献[9,10]的基础上通过引入最大似然码(Maximum Likelihood Decoding, MLD)理论对算法进行了改进，不再遍历提取基的组合，但在计算码距时也引入了不少计算量。随后文献[12,13]设计了基于RRNS的高效集成电路数据通道抗辐照保护方法，使得RRNS的纠错算法更为广泛地用于解决通信可靠性问题，但是纠错的速度和高复杂度仍是现有RRNS纠错的瓶颈。

针对传统RRNS纠错算法复杂度高的问题，本文在CRT的基础上，利用有限环剩余类的性质，提出并证明了溢出判定定理、不重复判定定理和唯一性区间搜索定理，并在此基础上提出了3种分别针对单错误和多错误的低复杂度RRNS纠错算法，避免了枚举带来的算法复杂度随基的个数增加而指数上升的问题。实验证明：本文提出的单错误纠错算法利用模运算来避免多次运用CRT还原数据，并基于余数系统中基的无权重性，提出基的整体代换思想，将计算复杂度降低至；基于定理2提出的不重复检测纠错算法在大型RRNS内具有优势；基于定理3提出的多错误搜索纠错算法只依靠比较算子实现，避免了传统算法中的复杂模运算，其计算复杂度从已有工作的降低至。

本文结构安排如下：在第2节中，介绍RNS和RRNS的定义，给出并证明支持所提出算法的必要定理及推论；在第3节中建立了3种RRNS纠错算法；在第4节中，对本文算法和已有的多种常用算法进行了复杂度比较与性能分析；最后给出了结论。

2 基本概念与数学推证

2.1 余数系统与中国剩余定理

余数系统(RNS)由一组两两互质的余数基定义。一个整数可由它对应的余数向量表示, 记为，其中。此余数系统所能表示的整数的范围为，其中，称为该余数系统(RNS)的动态范围。例如：在一个RNS中选取{2,3,5,7}作为基，则该RNS的动态范围为210，数19对应的余数表征向量为(1,1,4,5)。而可以由下式(1)确定：

根据高斯模运算准则，任取[0,]范围内的整数，其对应余数基的余数向量分别为：和，定义符号“”表示加、减及乘法运算。则的计算在余数系统的表征下变为。因此在进行乘加运算时可将传统的多位数(bit)的复杂运算用多个并行的较少位数的简单运算来实现。

2.2冗余余数系统

含有冗余校验基的余数系统称为冗余余数系统(RRNS)。检错和纠错过程通常是基于冗余余数系统来实现的。设为RRNS的基，其中，称为信息基，为冗余校验基。此冗余余数系统的动态范围为，其中。记,，定义为此冗余余数系统的非法范围。定义RRNS(,)为一个共含有个基，其中有个信息基，个冗余校验基的冗余余数系统。后文内容均在RRNS(,)上讨论。

2.3 数学推证

一般地，每个余数向量代表一个剩余类，即集合内的所有整数。但在RNS中，限定余数向量一一对应于模的简系；任意选取一组余数基，如果这组基的乘积大于整数，则可由在这组基意义下的余数向量唯一表示。因此，整数在不同余数基的组合下可能对应不同的余数向量。下面从有限环上剩余类的角度给出本文算法的必要定理与证明。设为原始余数向量对应的正确数据，为由接收向量还原的数据。

证明

故

证毕

定理1为检错算法提供了依据，基于定理1，可以构建定理2和定理3。首先定义合成运算：任取两组余数基1和2,在1和2下对应的两个余数向量分别为和，记=为在余数基=12下的余数向量，即为合成运算。

定义一个余数向量中非零分量的总数为此向量的重量。还原RRNS(,)中所有向量重量不超过[/2]的非零维余数向量，记录其对应的整数于集合，则共有种基的组合方式。每种组合方式里，不妨记选中的基为，令其余基对应分量均为0,对应分量任意取值，则一共可产生个非零维余数向量。中元素个数记为||。当所有基之间相对差距较小时，可得到如式(6)||的估计式：

下面举一例来说明中元素的选取。

例1 设定RRNS(4,2) 中的信息基为{2,3} 而冗余基为{5,7}，则所有中所包含的数值及其对应的表征向量为：105(1,0,0,0); 70(0,1,0,0); 140(0,2,0,0); 126(0,0,1,0); 42(0,0,2,0); 168(0,0,3,0); 84(0,0,4,0); 120(0,0,0,1); 30(0,0,0,2); 150(0,0,0,3); 60(0,0,0,4); 180(0,0,0,5); 90(0,0,0,6)。此时||=13。

3 算法描述

3.1 检错算法

3.2.1基替换单错误纠错算法步骤 对于存在一个错误的情形，纠错算法如下：

步骤1 利用CRT，还原出接收到的元余数向量对应数；

步骤4 从步骤2中的+1个基中任意剔除个基，再将替换基与剩下的个基合并成一个新的+1元基的组合，其乘积记为，再用模，得到余数：若在动态范围内，该数为所求；若不然，则表明步骤2中从+1个基中剔除的个基的对应分量是正确的，因此又将此个基加入替换基。以此类推，则至多重复次即可完成纠错过程。

例2 在RRNS中，信息基为{2,3,5}，校验基为{7,11}。=13，其对应的余数表示向量为。假设基3对应的分量发生错误，接收向量，根据CRT还原出=783。任意选取4个基{2,3,5,7}计算其乘积为：210。=783模210得余数153，超过动态范围，说明{2,3,5,7}中存在基对应错误分量，而基11对应的分量是正确的。从{2,3,5,7}中选取一个基2用基11替换，得到一组新的4个基的组合{11,3,5,7}，其乘积为1155。用=783模1155，得到余数783超过动态范围，说明上一次选择的4个基中仍有基对应错误分量，于是再从中选取一个未作过替换基的元素3用2替换，又得到一组新的4个基的组合{2,5,7,11}，其乘积为770，用=783模770得到余数13，在动态范围内，停止纠错过程，输出正确的数据为13。

3.2.2不重复检测多错误纠错算法步骤 一般地，基于定理2，对错误分量个数为的情况，纠错算法如下：

步骤1 利用CRT，还原出接收到的元余数向量对应数；

步骤4 数据验证：若存在<，使得，则，输出作为恢复数据，停止；若不存在，则重新进入步骤2。

下面举一个纠正一个错误的例子。

例3 在选择{2,3,5,11,13}作为基的RRNS中，{2,3,5}为信息基，{11,13}作为冗余校验基。23，对应的余数表征向量为。假定基11对应的元素出现错误，得到错误的接收向量，根据CRT还原出。{2,3,5,11,13}中3个基的乘积分别为：30,66,78,110,130, 165,195,715。模这些乘积分别得到以下余数：23,14,23,33,23,143,23,88。当23出现两次时即可停止纠错过程，输出正确数据：23。

3.2.3未知错误个数情况下的多错误搜索纠正算法

基于定理3，算法如下：

步骤1 利用CRT，还原出接收到的元余数向量对应数；

在步骤3检索数据的过程中，采用二分法进行数据检索，那么至多进行次检索，即可确定是否存在对应误差值。

4 算法性能分析

4.1 单错误纠错算法性能分析

文献[7]首先恢复信息基分量集合所对应的数，然后判断错误分量对应基是在信息基中还是在冗余校验基中，之后利用不同的冗余校验基进行CRT还原，找到错误元素纠正并恢复达到纠错目标；文献[14]在动态范围内选取常数的所有倍数作为发送数据，因此在该系统中没有冗余基，之后通过误差范围的检验确定错误位，并进行数据还原。以下给出单错误纠错算法的性能比较，如表1所示。从表1中可以看出，本文算法在复杂度上具有明显优势。

表1单错误纠错算法计算复杂度分析

4.2 唯一性判断纠错算法性能分析

下面给出唯一性判断纠正算法在RRNS(,)中纠正一个错误的情况下算法的性能分析，唯一判断纠错算法更有利于在基较多的情况下应用，记，则运算次数的期望为

4.3 多错误搜索纠正算法性能分析

文献[9,11]中提出的算法是目前最主要的两种适用于一般情形下的多错误纠错算法。文献[9]利用欧几里德方法和连分数理论判断接收向量中所选择的分量子集是否全为正确分量。其实质上可以通过模运算实现，如文献[11]中所示：第1步首先验证接收向量中所有维分量的组合对应的数据是否

现阶段取模运算通常利用试减算法实现，一般地，在二进制表示下，设被模数是位长为的整数，模数是位长为的整数，则模运算通过迭代地将进行移位，并用不断试减的倍数，直至结果属于[0,]，得到余数。因此模所需减法运算的时间复杂度为，比较运算的时间复杂度为。

而本文提出的搜索纠错算法基于定理3，采用二分法搜索，仅通过比较算子实现，不仅避免了复杂的模运算，提高了系统整体吞吐率而且复杂度为对数级，远低于文献[9,11]所需的运算次数。因此在最开始即可只付出极小代价而直接达到纠错系统的最大纠错能力。具体计算复杂度如表2所示，从表2中看出，本文算法在复杂度上远低于文献[9,11]的多项式级。为了进一步分析本文算法的性能，本文分别对=4, 6和8，即分别具有2, 3, 4个错误纠错能力的余数系统的纠错性能进行实验。对=4,，设定，计算复杂度对比如图1(a)所示；对，设定，计算复杂度对比如图1(b)所示；对=8,，设定，计算复杂度对比如图1(c)所示。从图1中可以看出本文算法复杂度不仅明显小于文献[9,11]中的算法，并且随着的增大而优势更加显著。

表2搜索算法与传统算法计算复杂度对比

图1 与传统算法计算复杂度对比

5 结束语

本文基于中国剩余定理和有限环上剩余类的观点提出了溢出判定定理，不重复判断定理和唯一性区间搜索定理，构建了3种适用于不同情况的易于硬件实现的低复杂度纠错算法，解决了传统算法中反复利用CRT进行数据还原而引入大量复杂的乘，加算子的问题。其中多错误搜索纠错算法仅依靠比较算子和二分法搜索实现，避免了复杂的大数取模运算，将计算复杂度由传统算法的多项式级降低为对数级，且通过实验证明只需付出极小代价即可达到算法环境下的最大纠错能力，纠错性能远高于传统算法。

参考文献

[1] Madhukumar A S, Chin F, and Premkumar A B. Incremental redundancy and link adaptation in wireless local area networks using residue number systems[J]., 2003, 55(27): 321-336.

[2] Pham Duc-Minh, Premkumar AB, and MadhukumarAS. Error detection and correction in communication channels using inverse gray RSNS Codes[J].,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]., 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]., 2002, 51(6): 1547-1559.

[5] Keller T, Liew T H, and Hanzo L. Adaptive redundant residue number system coded multicarrier modulation[J]., 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]., 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]., 1992, 39(1): 18-34.

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

[10] Mandelbaum D M. On a class of arithmetic codes and a decoding algorithm(Corresp.)[J]., 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]., 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]., 2010, 57(6): 3779-3786.

[13] Lei Li and Hu-Jian-hao. Redundant residue number systems based radiation gardening for datapath[J]., 2010, 57(4): 2332-2343.

[14] Pontarelli S, Cardarilli G C, Re M,.. 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.

Low-complexity Error Correction Algorithms for Redundant Residue Number Systems

Xiao Han-shen①Hu Jian-hao②Ma Shang②

①(,,100084,)②(,,611731,)

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 complexityis 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

TN919.3

A

1009-5896(2015)08-1944-06

10.11999/JEIT141454

胡剑浩 jhhu@uestc.edu.cn

2014-11-20收到，2015-04-08改回，2015-06-09网络优先出版

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

肖翰珅： 男，1995年生，博士生，研究方向为通信编码理论、数学模型.

胡剑浩： 男，1971年生，教授，博士生导师，研究方向为余数系统、Internet无线接入技术、拥塞控制、流量控制.

马 上： 男，1978年生，副教授，研究方向为VLSI设计和无线通信.