冗余余數系統低復雜度快速糾錯算法設計

肖翰珅 胡劍浩 馬 上

?

冗余余數系統低復雜度快速糾錯算法設計

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

①(清華大學數學科學系 北京 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設計和無線通信.