冗余余數(shù)系統(tǒng)低復(fù)雜度快速糾錯(cuò)算法設(shè)計(jì)

肖翰珅 胡劍浩 馬 上

?

冗余余數(shù)系統(tǒng)低復(fù)雜度快速糾錯(cuò)算法設(shè)計(jì)

肖翰珅①胡劍浩*②馬 上②

①(清華大學(xué)數(shù)學(xué)科學(xué)系 北京 100084)②(電子科技大學(xué)通信抗干擾技術(shù)國家級(jí)重點(diǎn)實(shí)驗(yàn)室 成都 611731)

余數(shù)系統(tǒng)由于具有增強(qiáng)傳輸信息在并行系統(tǒng)中魯棒性的優(yōu)勢(shì)，已被廣泛應(yīng)用在無線局域網(wǎng)(WLAN)以及碼分多址通信技術(shù)(CDMA)等領(lǐng)域。而余數(shù)系統(tǒng)中的糾錯(cuò)檢錯(cuò)是保證傳輸數(shù)據(jù)可靠性和高效性的關(guān)鍵問題。該文根據(jù)有限環(huán)上剩余類的性質(zhì)提出溢出判定定理，不重復(fù)判斷定理和唯一性區(qū)間搜索定理，并在此基礎(chǔ)上進(jìn)一步提出采用模運(yùn)算代替?zhèn)鹘y(tǒng)中國剩余定理進(jìn)行快速恢復(fù)的單錯(cuò)誤糾錯(cuò)算法，將復(fù)雜度降低為；提出不重復(fù)判定糾錯(cuò)算法；并對(duì)于一般錯(cuò)誤情形，設(shè)計(jì)通過比較算子實(shí)現(xiàn)的搜索糾錯(cuò)算法。其中搜索糾錯(cuò)算法能直接實(shí)現(xiàn)系統(tǒng)最大糾錯(cuò)能力，且避免依靠復(fù)雜模運(yùn)算算子實(shí)現(xiàn)，系統(tǒng)吞吐率得以提高；與傳統(tǒng)算法相比，計(jì)算復(fù)雜度由多項(xiàng)式級(jí)降低至對(duì)數(shù)級(jí)。

編碼理論；中國剩余定理；冗余余數(shù)系統(tǒng)；糾錯(cuò)檢錯(cuò)

1 引言

現(xiàn)代通信、雷達(dá)、多媒體技術(shù)的發(fā)展對(duì)數(shù)字信號(hào)處理(Digital Signal Processing, DSP)的要求日益增加。其主要表現(xiàn)在DSP算法復(fù)雜度增加的同時(shí)要求更高的處理速度、系統(tǒng)吞吐率和可靠性，更低的單位功耗和成本。這些需求在機(jī)載、移動(dòng)和衛(wèi)星等設(shè)備中的數(shù)字信號(hào)處理芯片設(shè)計(jì)上表現(xiàn)得尤為突出。研究表明，在未來的集成電路設(shè)計(jì)里，大規(guī)模的并行處理技術(shù)將取代傳統(tǒng)的串行處理方式，以滿足對(duì)集成電路處理能力和處理速度日益提高的要求。DSP算法的并行處理目前主要有兩個(gè)研究領(lǐng)域：一是通過增加處理單元的數(shù)量并輔以相關(guān)調(diào)度機(jī)制實(shí)現(xiàn)高速大容量的計(jì)算和處理，例如用兩個(gè)解碼器并行工作可以使解碼速度提高1倍；二是采用并行數(shù)值表征系統(tǒng)代替?zhèn)鹘y(tǒng)的數(shù)值表征系統(tǒng)，從算法前端入手解決VLSI的速度、功耗和面積問題。后者利用數(shù)值表征系統(tǒng)的并行性，在算法的最前端考慮DSP系統(tǒng)的并行實(shí)現(xiàn)，而余數(shù)系統(tǒng)(Residue Number System, RNS)就是一個(gè)并行數(shù)值表征系統(tǒng)。RNS是一個(gè)古老的無權(quán)重?cái)?shù)字表征系統(tǒng)，源于中國剩余定理(Chinese Remainder Theorem, CRT)，它將傳統(tǒng)的多位數(shù)復(fù)雜運(yùn)算用多個(gè)并行的較少位數(shù)的簡單運(yùn)算單元來實(shí)現(xiàn)；并且在進(jìn)行乘、加運(yùn)算時(shí)，各通道完全獨(dú)立，只使用數(shù)據(jù)的余數(shù)表征向量的對(duì)應(yīng)分量進(jìn)行乘、加運(yùn)算。這一并行的數(shù)值表征計(jì)算形式不僅可以有效地降低面積功耗，也決定了余數(shù)系統(tǒng)潛在的高速度。由于其高速、低復(fù)雜度和低功耗的特性，RNS已被研究證明適用于如無線局域網(wǎng)[1]、碼分多址通信技術(shù)、卷積和快速傅里葉變換等數(shù)字信號(hào)處理領(lǐng)域[2]。

冗余余數(shù)系統(tǒng)(Redundant Residue Number System, RRNS)通過向余數(shù)系統(tǒng)引入冗余的余數(shù)基，使得其表征的計(jì)算系統(tǒng)具有冗余性。具體體現(xiàn)為RRNS中各運(yùn)算通道是互為冗余的，而且各通道計(jì)算是相互獨(dú)立的；當(dāng)部分余數(shù)分量出現(xiàn)錯(cuò)誤時(shí)，該錯(cuò)誤不會(huì)在各分量間擴(kuò)散，此時(shí)仍可以通過余數(shù)分量間的冗余關(guān)系獲得正確的運(yùn)算結(jié)果。RRNS中所有余數(shù)分量(含冗余分量)可以同等地參與數(shù)據(jù)通道的相關(guān)計(jì)算和檢錯(cuò)、糾錯(cuò)計(jì)算，而普通的糾錯(cuò)編碼，需要在各級(jí)計(jì)算后重新進(jìn)行編譯碼的操作。作為具有糾錯(cuò)能力的并行數(shù)值表征和計(jì)算系統(tǒng)，RRNS被廣泛應(yīng)用于正交信號(hào)處理[3,4]以及自適應(yīng)多載波調(diào)制[5]等領(lǐng)域。

在現(xiàn)有工作中，基于RRNS的糾錯(cuò)編碼一般有以下兩種策略。第1種是基于計(jì)算余數(shù)向量特征值與設(shè)定值比對(duì)來完成：Yang等人[6]通過迭代增加冗余基，并利用中國剩余定理在低可靠度無線信道中進(jìn)行數(shù)據(jù)還原以解決糾錯(cuò)問題；但是由于每一次增加冗余基的操作均需通過CRT還原數(shù)據(jù)，復(fù)雜度較高。文獻(xiàn)[7,8]引入Hamming重量以及最小距離概念，提出了通過找出錯(cuò)誤位并糾正，最終實(shí)現(xiàn)糾錯(cuò)檢錯(cuò)的算法。但從文獻(xiàn)[7]的單錯(cuò)誤糾正算法到文獻(xiàn)[8]雙錯(cuò)誤和單突發(fā)錯(cuò)誤糾正算法的改進(jìn)是較復(fù)雜的。第2種策略是通過還原數(shù)據(jù)比對(duì)來完成：文獻(xiàn)[9]基于連分?jǐn)?shù)以及歐幾里得方法[10]，通過冗余校驗(yàn)基和信息基的組合有效地確定了余數(shù)向量的錯(cuò)誤位，糾正后還原得到正確數(shù)據(jù)。文獻(xiàn)[11]在文獻(xiàn)[9,10]的基礎(chǔ)上通過引入最大似然碼(Maximum Likelihood Decoding, MLD)理論對(duì)算法進(jìn)行了改進(jìn)，不再遍歷提取基的組合，但在計(jì)算碼距時(shí)也引入了不少計(jì)算量。隨后文獻(xiàn)[12,13]設(shè)計(jì)了基于RRNS的高效集成電路數(shù)據(jù)通道抗輻照保護(hù)方法，使得RRNS的糾錯(cuò)算法更為廣泛地用于解決通信可靠性問題，但是糾錯(cuò)的速度和高復(fù)雜度仍是現(xiàn)有RRNS糾錯(cuò)的瓶頸。

針對(duì)傳統(tǒng)RRNS糾錯(cuò)算法復(fù)雜度高的問題，本文在CRT的基礎(chǔ)上，利用有限環(huán)剩余類的性質(zhì)，提出并證明了溢出判定定理、不重復(fù)判定定理和唯一性區(qū)間搜索定理，并在此基礎(chǔ)上提出了3種分別針對(duì)單錯(cuò)誤和多錯(cuò)誤的低復(fù)雜度RRNS糾錯(cuò)算法，避免了枚舉帶來的算法復(fù)雜度隨基的個(gè)數(shù)增加而指數(shù)上升的問題。實(shí)驗(yàn)證明：本文提出的單錯(cuò)誤糾錯(cuò)算法利用模運(yùn)算來避免多次運(yùn)用CRT還原數(shù)據(jù)，并基于余數(shù)系統(tǒng)中基的無權(quán)重性，提出基的整體代換思想，將計(jì)算復(fù)雜度降低至；基于定理2提出的不重復(fù)檢測(cè)糾錯(cuò)算法在大型RRNS內(nèi)具有優(yōu)勢(shì)；基于定理3提出的多錯(cuò)誤搜索糾錯(cuò)算法只依靠比較算子實(shí)現(xiàn)，避免了傳統(tǒng)算法中的復(fù)雜模運(yùn)算，其計(jì)算復(fù)雜度從已有工作的降低至。

本文結(jié)構(gòu)安排如下：在第2節(jié)中，介紹RNS和RRNS的定義，給出并證明支持所提出算法的必要定理及推論；在第3節(jié)中建立了3種RRNS糾錯(cuò)算法；在第4節(jié)中，對(duì)本文算法和已有的多種常用算法進(jìn)行了復(fù)雜度比較與性能分析；最后給出了結(jié)論。

2 基本概念與數(shù)學(xué)推證

2.1 余數(shù)系統(tǒng)與中國剩余定理

余數(shù)系統(tǒng)(RNS)由一組兩兩互質(zhì)的余數(shù)基定義。一個(gè)整數(shù)可由它對(duì)應(yīng)的余數(shù)向量表示, 記為，其中。此余數(shù)系統(tǒng)所能表示的整數(shù)的范圍為，其中，稱為該余數(shù)系統(tǒng)(RNS)的動(dòng)態(tài)范圍。例如：在一個(gè)RNS中選取{2,3,5,7}作為基，則該RNS的動(dòng)態(tài)范圍為210，數(shù)19對(duì)應(yīng)的余數(shù)表征向量為(1,1,4,5)。而可以由下式(1)確定：

根據(jù)高斯模運(yùn)算準(zhǔn)則，任取[0,]范圍內(nèi)的整數(shù)，其對(duì)應(yīng)余數(shù)基的余數(shù)向量分別為：和，定義符號(hào)“”表示加、減及乘法運(yùn)算。則的計(jì)算在余數(shù)系統(tǒng)的表征下變?yōu)?。因此在進(jìn)行乘加運(yùn)算時(shí)可將傳統(tǒng)的多位數(shù)(bit)的復(fù)雜運(yùn)算用多個(gè)并行的較少位數(shù)的簡單運(yùn)算來實(shí)現(xiàn)。

2.2冗余余數(shù)系統(tǒng)

含有冗余校驗(yàn)基的余數(shù)系統(tǒng)稱為冗余余數(shù)系統(tǒng)(RRNS)。檢錯(cuò)和糾錯(cuò)過程通常是基于冗余余數(shù)系統(tǒng)來實(shí)現(xiàn)的。設(shè)為RRNS的基，其中，稱為信息基，為冗余校驗(yàn)基。此冗余余數(shù)系統(tǒng)的動(dòng)態(tài)范圍為，其中。記,，定義為此冗余余數(shù)系統(tǒng)的非法范圍。定義RRNS(,)為一個(gè)共含有個(gè)基，其中有個(gè)信息基，個(gè)冗余校驗(yàn)基的冗余余數(shù)系統(tǒng)。后文內(nèi)容均在RRNS(,)上討論。

2.3 數(shù)學(xué)推證

一般地，每個(gè)余數(shù)向量代表一個(gè)剩余類，即集合內(nèi)的所有整數(shù)。但在RNS中，限定余數(shù)向量一一對(duì)應(yīng)于模的簡系；任意選取一組余數(shù)基，如果這組基的乘積大于整數(shù)，則可由在這組基意義下的余數(shù)向量唯一表示。因此，整數(shù)在不同余數(shù)基的組合下可能對(duì)應(yīng)不同的余數(shù)向量。下面從有限環(huán)上剩余類的角度給出本文算法的必要定理與證明。設(shè)為原始余數(shù)向量對(duì)應(yīng)的正確數(shù)據(jù)，為由接收向量還原的數(shù)據(jù)。

證明

故

證畢

定理1為檢錯(cuò)算法提供了依據(jù)，基于定理1，可以構(gòu)建定理2和定理3。首先定義合成運(yùn)算：任取兩組余數(shù)基1和2,在1和2下對(duì)應(yīng)的兩個(gè)余數(shù)向量分別為和，記=為在余數(shù)基=12下的余數(shù)向量，即為合成運(yùn)算。

定義一個(gè)余數(shù)向量中非零分量的總數(shù)為此向量的重量。還原RRNS(,)中所有向量重量不超過[/2]的非零維余數(shù)向量，記錄其對(duì)應(yīng)的整數(shù)于集合，則共有種基的組合方式。每種組合方式里，不妨記選中的基為，令其余基對(duì)應(yīng)分量均為0,對(duì)應(yīng)分量任意取值，則一共可產(chǎn)生個(gè)非零維余數(shù)向量。中元素個(gè)數(shù)記為||。當(dāng)所有基之間相對(duì)差距較小時(shí)，可得到如式(6)||的估計(jì)式：

下面舉一例來說明中元素的選取。

例1 設(shè)定RRNS(4,2) 中的信息基為{2,3} 而冗余基為{5,7}，則所有中所包含的數(shù)值及其對(duì)應(yīng)的表征向量為：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)。此時(shí)||=13。

3 算法描述

3.1 檢錯(cuò)算法

3.2.1基替換單錯(cuò)誤糾錯(cuò)算法步驟 對(duì)于存在一個(gè)錯(cuò)誤的情形，糾錯(cuò)算法如下：

步驟1 利用CRT，還原出接收到的元余數(shù)向量對(duì)應(yīng)數(shù)；

步驟4 從步驟2中的+1個(gè)基中任意剔除個(gè)基，再將替換基與剩下的個(gè)基合并成一個(gè)新的+1元基的組合，其乘積記為，再用模，得到余數(shù)：若在動(dòng)態(tài)范圍內(nèi)，該數(shù)為所求；若不然，則表明步驟2中從+1個(gè)基中剔除的個(gè)基的對(duì)應(yīng)分量是正確的，因此又將此個(gè)基加入替換基。以此類推，則至多重復(fù)次即可完成糾錯(cuò)過程。

例2 在RRNS中，信息基為{2,3,5}，校驗(yàn)基為{7,11}。=13，其對(duì)應(yīng)的余數(shù)表示向量為。假設(shè)基3對(duì)應(yīng)的分量發(fā)生錯(cuò)誤，接收向量，根據(jù)CRT還原出=783。任意選取4個(gè)基{2,3,5,7}計(jì)算其乘積為：210。=783模210得余數(shù)153，超過動(dòng)態(tài)范圍，說明{2,3,5,7}中存在基對(duì)應(yīng)錯(cuò)誤分量，而基11對(duì)應(yīng)的分量是正確的。從{2,3,5,7}中選取一個(gè)基2用基11替換，得到一組新的4個(gè)基的組合{11,3,5,7}，其乘積為1155。用=783模1155，得到余數(shù)783超過動(dòng)態(tài)范圍，說明上一次選擇的4個(gè)基中仍有基對(duì)應(yīng)錯(cuò)誤分量，于是再從中選取一個(gè)未作過替換基的元素3用2替換，又得到一組新的4個(gè)基的組合{2,5,7,11}，其乘積為770，用=783模770得到余數(shù)13，在動(dòng)態(tài)范圍內(nèi)，停止糾錯(cuò)過程，輸出正確的數(shù)據(jù)為13。

3.2.2不重復(fù)檢測(cè)多錯(cuò)誤糾錯(cuò)算法步驟 一般地，基于定理2，對(duì)錯(cuò)誤分量個(gè)數(shù)為的情況，糾錯(cuò)算法如下：

步驟1 利用CRT，還原出接收到的元余數(shù)向量對(duì)應(yīng)數(shù)；

步驟4 數(shù)據(jù)驗(yàn)證：若存在<，使得，則，輸出作為恢復(fù)數(shù)據(jù)，停止；若不存在，則重新進(jìn)入步驟2。

下面舉一個(gè)糾正一個(gè)錯(cuò)誤的例子。

例3 在選擇{2,3,5,11,13}作為基的RRNS中，{2,3,5}為信息基，{11,13}作為冗余校驗(yàn)基。23，對(duì)應(yīng)的余數(shù)表征向量為。假定基11對(duì)應(yīng)的元素出現(xiàn)錯(cuò)誤，得到錯(cuò)誤的接收向量，根據(jù)CRT還原出。{2,3,5,11,13}中3個(gè)基的乘積分別為：30,66,78,110,130, 165,195,715。模這些乘積分別得到以下余數(shù)：23,14,23,33,23,143,23,88。當(dāng)23出現(xiàn)兩次時(shí)即可停止糾錯(cuò)過程，輸出正確數(shù)據(jù)：23。

3.2.3未知錯(cuò)誤個(gè)數(shù)情況下的多錯(cuò)誤搜索糾正算法

基于定理3，算法如下：

步驟1 利用CRT，還原出接收到的元余數(shù)向量對(duì)應(yīng)數(shù)；

在步驟3檢索數(shù)據(jù)的過程中，采用二分法進(jìn)行數(shù)據(jù)檢索，那么至多進(jìn)行次檢索，即可確定是否存在對(duì)應(yīng)誤差值。

4 算法性能分析

4.1 單錯(cuò)誤糾錯(cuò)算法性能分析

文獻(xiàn)[7]首先恢復(fù)信息基分量集合所對(duì)應(yīng)的數(shù)，然后判斷錯(cuò)誤分量對(duì)應(yīng)基是在信息基中還是在冗余校驗(yàn)基中，之后利用不同的冗余校驗(yàn)基進(jìn)行CRT還原，找到錯(cuò)誤元素糾正并恢復(fù)達(dá)到糾錯(cuò)目標(biāo)；文獻(xiàn)[14]在動(dòng)態(tài)范圍內(nèi)選取常數(shù)的所有倍數(shù)作為發(fā)送數(shù)據(jù)，因此在該系統(tǒng)中沒有冗余基，之后通過誤差范圍的檢驗(yàn)確定錯(cuò)誤位，并進(jìn)行數(shù)據(jù)還原。以下給出單錯(cuò)誤糾錯(cuò)算法的性能比較，如表1所示。從表1中可以看出，本文算法在復(fù)雜度上具有明顯優(yōu)勢(shì)。

表1單錯(cuò)誤糾錯(cuò)算法計(jì)算復(fù)雜度分析

4.2 唯一性判斷糾錯(cuò)算法性能分析

下面給出唯一性判斷糾正算法在RRNS(,)中糾正一個(gè)錯(cuò)誤的情況下算法的性能分析，唯一判斷糾錯(cuò)算法更有利于在基較多的情況下應(yīng)用，記，則運(yùn)算次數(shù)的期望為

4.3 多錯(cuò)誤搜索糾正算法性能分析

文獻(xiàn)[9,11]中提出的算法是目前最主要的兩種適用于一般情形下的多錯(cuò)誤糾錯(cuò)算法。文獻(xiàn)[9]利用歐幾里德方法和連分?jǐn)?shù)理論判斷接收向量中所選擇的分量子集是否全為正確分量。其實(shí)質(zhì)上可以通過模運(yùn)算實(shí)現(xiàn)，如文獻(xiàn)[11]中所示：第1步首先驗(yàn)證接收向量中所有維分量的組合對(duì)應(yīng)的數(shù)據(jù)是否

現(xiàn)階段取模運(yùn)算通常利用試減算法實(shí)現(xiàn)，一般地，在二進(jìn)制表示下，設(shè)被模數(shù)是位長為的整數(shù)，模數(shù)是位長為的整數(shù)，則模運(yùn)算通過迭代地將進(jìn)行移位，并用不斷試減的倍數(shù)，直至結(jié)果屬于[0,]，得到余數(shù)。因此模所需減法運(yùn)算的時(shí)間復(fù)雜度為，比較運(yùn)算的時(shí)間復(fù)雜度為。

而本文提出的搜索糾錯(cuò)算法基于定理3，采用二分法搜索，僅通過比較算子實(shí)現(xiàn)，不僅避免了復(fù)雜的模運(yùn)算，提高了系統(tǒng)整體吞吐率而且復(fù)雜度為對(duì)數(shù)級(jí)，遠(yuǎn)低于文獻(xiàn)[9,11]所需的運(yùn)算次數(shù)。因此在最開始即可只付出極小代價(jià)而直接達(dá)到糾錯(cuò)系統(tǒng)的最大糾錯(cuò)能力。具體計(jì)算復(fù)雜度如表2所示，從表2中看出，本文算法在復(fù)雜度上遠(yuǎn)低于文獻(xiàn)[9,11]的多項(xiàng)式級(jí)。為了進(jìn)一步分析本文算法的性能，本文分別對(duì)=4, 6和8，即分別具有2, 3, 4個(gè)錯(cuò)誤糾錯(cuò)能力的余數(shù)系統(tǒng)的糾錯(cuò)性能進(jìn)行實(shí)驗(yàn)。對(duì)=4,，設(shè)定，計(jì)算復(fù)雜度對(duì)比如圖1(a)所示；對(duì)，設(shè)定，計(jì)算復(fù)雜度對(duì)比如圖1(b)所示；對(duì)=8,，設(shè)定，計(jì)算復(fù)雜度對(duì)比如圖1(c)所示。從圖1中可以看出本文算法復(fù)雜度不僅明顯小于文獻(xiàn)[9,11]中的算法，并且隨著的增大而優(yōu)勢(shì)更加顯著。

表2搜索算法與傳統(tǒng)算法計(jì)算復(fù)雜度對(duì)比

圖1 與傳統(tǒng)算法計(jì)算復(fù)雜度對(duì)比

5 結(jié)束語

本文基于中國剩余定理和有限環(huán)上剩余類的觀點(diǎn)提出了溢出判定定理，不重復(fù)判斷定理和唯一性區(qū)間搜索定理，構(gòu)建了3種適用于不同情況的易于硬件實(shí)現(xiàn)的低復(fù)雜度糾錯(cuò)算法，解決了傳統(tǒng)算法中反復(fù)利用CRT進(jìn)行數(shù)據(jù)還原而引入大量復(fù)雜的乘，加算子的問題。其中多錯(cuò)誤搜索糾錯(cuò)算法僅依靠比較算子和二分法搜索實(shí)現(xiàn)，避免了復(fù)雜的大數(shù)取模運(yùn)算，將計(jì)算復(fù)雜度由傳統(tǒng)算法的多項(xiàng)式級(jí)降低為對(duì)數(shù)級(jí)，且通過實(shí)驗(yàn)證明只需付出極小代價(jià)即可達(dá)到算法環(huán)境下的最大糾錯(cuò)能力，糾錯(cuò)性能遠(yuǎn)高于傳統(tǒng)算法。

參考文獻(xiàn)

[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網(wǎng)絡(luò)優(yōu)先出版

國家自然科學(xué)基金(61101033, 61076096)，國家863計(jì)劃項(xiàng)目(2011AA010201)，清華大學(xué)自主科研計(jì)劃(20141081231)和國家高科技中央高校基本科研業(yè)務(wù)費(fèi)(ZYGX 2011J118)資助課題

肖翰珅： 男，1995年生，博士生，研究方向?yàn)橥ㄐ啪幋a理論、數(shù)學(xué)模型.

胡劍浩： 男，1971年生，教授，博士生導(dǎo)師，研究方向?yàn)橛鄶?shù)系統(tǒng)、Internet無線接入技術(shù)、擁塞控制、流量控制.

馬 上： 男，1978年生，副教授，研究方向?yàn)閂LSI設(shè)計(jì)和無線通信.