RS編譯碼電路的可重構性研究

譚思煒, 潘紅兵, 龍宏波

(海軍工程大學電子工程學院,武漢 430033)

0 引言

可重構性是指同一系統的硬件或軟件模塊根據數據流或控制流的輸入重新配置,改變電路結構或模塊功能,滿足新的任務需求。目前可編程集成芯片大規模運用在通信系統設計領域,給可重構電路的實現帶來可能。本文根據集成芯片的可編程特點,以可重構的思想對傳統的編譯碼電路進行修改,使其能依據不同通信系統RS(Reed-Solomon)碼標準的配置信息,實現對應的編譯碼過程。

RS碼是定義在伽羅華有限域G(2m)上的一種多進制BCH碼,具有較強的糾錯能力,構造方便,易于實現。但針對于不同的通信系統,RS碼的標準不盡一致。常用到的RS碼標準有：數據系統顧問委員會(CCSDS)的RS(255,233)、數字電視傳輸系統(DVBS)的RS(255,239)或RS(204,188)、光存儲技術中DVD的RS(208,192)或RS(182,172)以及高清晰電視(HDTV)RS(255,235)或RS(207,187)。因而實際工程應用中需要根據對應的編碼標準設計RS編譯碼器。顯然,如果需要編譯碼電路具有可重構性,滿足以上幾種常用的編碼標準,則只要編譯碼器的碼長滿足最大值255,可糾正錯誤符號位數為最大值11即可。

1 可重構RS編碼電路

得其具有較強的突發糾錯能力。定義2t=n-k,t表示RS碼是由生成多項式G(x)定義的一組線性循環碼RS(n,k),k表示數據符號碼長,n表示包括數據符號和校驗符號在內的碼長。RS碼非二進制的屬性使RS碼的糾錯能力,即最多糾正t個符號的錯誤。

RS編碼過程一般可以表示為：C(x)=I(x)+(I(x)?x2t)mod G(x)[1],其中C(x)表示碼字多項式,I(x)表示數據符號多項式。顯然一組RS碼是由兩部分組成,前面k位是符號碼,后面的n-k位是校驗碼,校驗碼是通過數據符號與生成多項式通過多項式的長除求余得到的。因而校驗碼的計算就是編碼的主要過程。

硬件上一般采用線性反饋位移寄存器(LFSR)實現以上計算過程。如圖1所示,向LFSR依次輸入信息碼,同時信息碼流向輸出端,經過k次位移,信息碼輸入完畢,多項式的長除也計算完成,寄存器內得到余數,即校驗碼。最后依次輸出寄存器內的校驗碼,輸出端即可得到碼長為n的RS碼。這里涉及到的運算都是有限域內的乘法和加法。

由圖1可知,LFSR中寄存器個數N是由RS的糾錯能力t決定的,N=n-k=2t。設法改變N值,即可滿足不同t值的RS編碼標準。通過配置信息將N值輸入到可重構RS編碼電路,從而得到相應標準的編碼器。由于討論的標準中2tmax=22,故設置22個寄存器的RS編碼電路。其可重構電路如圖2所示。

圖1 RS編碼電路Fig.1 RSencoding circuit

圖2 可重構RS編碼電路Fig.2 A configurable RS encoding circuit

如果需要配置的寄存器個數小于22個,則配置信息逐位設置0或1從左往右通過依次關掉與門來關掉不需要的寄存器,直到剩下的寄存器組可以構成對應標準所需的LFSR為止。

2 可重構RS譯碼電路

RS碼的譯碼過程主要包括伴隨式的計算、解關鍵方程以及糾錯。其中最關鍵的步驟在于解關鍵方程。目前解關鍵方程的算法很多,本文采用改進的歐幾里德算法,求得錯誤位置多項式和錯誤值多項式,利用錢氏搜索得到錯誤位置,然后運用Forney算法計算錯誤值,最后求和糾錯,從而完成整個譯碼過程。

2.1 可重構伴隨多項式計算

設譯碼端接收到的碼字多項式為R(x),則有R(x)=C(x)+E(x),其中E(x)表示信息在信道中由于噪聲干擾或衰落產生的誤碼,同樣以誤碼多項式表示。伴隨多項式S(x)可以直接從接收碼字多項式中計算得到,定義伴隨多項式見式(1),其系數個數為

由式(2)可知,求伴隨多項式符號Si的過程可以通過有限域內的乘法和加法迭代運算實現,如圖3所示。將Si的計算設為若干相同的獨立模塊,并行執行,即可得到各個伴隨多項式的系數。這里同樣設置伴隨多項式符號個數最大值2tmax=22,根據編碼標準,輸入配置信息打開相應個數的伴隨多項式符號計算模塊,輸入接收碼字和與各Si模塊對應的符號αi,完成伴隨多項式系數的計算,如圖4所示,即可滿足任意標準RS(n,k),n-k≤22的伴隨多項式計算。

圖3 Si迭代計算模塊Fig.3 Siiterative computation block

圖4 可重構伴隨多項式計算電路Fig.4 Reconfigurable syndrome computation circuit

2.2 關鍵方程求解

定義錯誤位置多項式：

其中：v表示錯誤個數。錯誤多項式是用來定義某位接收碼字上的錯誤,顯然v≤t,表示錯誤個數應該在RS碼的糾錯范圍內。如果rk上發生錯誤,則有σ(α-k)=0。

定義錯位值多項式：

錯誤位置多項式σ(x)和錯誤值多項式ω(x)可由伴隨多項式S(x)通過如下方程求得：

方程(5)稱為關鍵方程。改進歐幾里德算法[2]的迭代過程如下所示。

1)初始化。

其中：ai-1,bi-1分別表示Ri-1(x),Qi-1(x)的首項系數。顯然式(7)、式(8)的迭代運算相同,因此可用圖5所示的運算模塊實現,每迭代一次就需要一個運算模塊,迭代次數i≤v,v為錯誤個數。所以可在譯碼器電路里預先設置t個迭代運算模塊,以滿足不同標準的RS碼譯碼運算,實現其可重構功能。解關鍵方程的可重構電路結構如圖6所示。

圖5 改進歐幾里德迭代運算模塊Fig.5 Iterative computation block of modified Euclidean algorithm

圖6 解關鍵方程的可重構電路結構Fig.6 Reconfigurable key equation circuit

2.3 錢氏搜索與糾錯

由錯誤位置多項式的定義可知,只要逐位判斷σ(α-k)=0,k=0,1,…,n-1是否成立,即可知道接收碼字的正誤。所以需要逐位計算σ(α-k),這就是錢氏搜索[3]。

碼字的糾錯使用的是Forney算法[6],利用關鍵方程求解得到的錯誤位置多項式σ(x)和錯誤值多項式ω(x)計算并糾正錯誤。其算法如下[5-10]：

即求出σ(α-k)的偶數項,用其倒數與ω(α-k)相乘,完成Forney算法中的除法運算。倒數運算可以用查表法實現。顯然σ(α-k),oddσ(α-k)和ω(α-k)都是多項式的運算,因而可以用與式(2)相同的方法迭代實現。迭代模塊與圖3的伴隨多項式迭代計算模塊相同,這里不再復述。需要指出的是oddσ(α-k)的計算需要依次向迭代模塊輸入錯誤位置多項式σ(x)的奇數項系數,奇數項系數的獲得可以通過選擇器在σ(x)系數輸入的同時選擇其奇數項系數,輸入到oddσ(α-k)的迭代模塊,具體實現方法如圖7所示。

圖7 σ(α-k)和oddσ(α-k)計算模塊Fig.7 σ(α-k)and oddσ(α-k)computation block

錯誤值計算模塊如圖8所示,判斷計算得到的σ(α-k)是否為0。如果發生錯誤,則選擇用Forney算法計算的錯誤值,否則多路復用器輸出0。最后將錯誤值與緩存中的接收碼求和即可糾正錯誤。

圖8 錯誤值計算Fig.8 Error value computation

錯誤值計算的可重構結構如圖9所示,設錯誤值計算模塊個數為255,并行計算n位接收碼的錯誤值,提高計算速度。根據不同RS碼標準,輸入配置信息,選擇相應數量的錯誤值計算模塊。

圖9 錯誤值計算的可重構結構Fig.9 Reconfigurable error value computation structure

3 結論

本文介紹了RS碼的編譯碼原理與過程,討論了編譯碼電路結構,并提出了具有可重構特性的硬件實現電路。該可重構結構以RS(255,233)標準為參考對象,并向下兼容所有碼長小于等于255,可糾錯的符號位小于等于11的RS編碼標準,應用范圍廣。但RS(n,k)的n及n-k值越小,電路硬件的使用率越低,因而適合n,n-k值較大的RS編碼標準。電路中使用的多項式迭代計算模塊相同,如Si,σ(α-k),oddσ(α-k)和ω(α-k)的計算,因而適合RS編譯碼電路的大規模集成。在計算速度方面,編譯碼電路中的迭代模塊以一組RS碼輸入時間為一個計算周期,并行計算的伴隨多項式系數和錯誤值,將傳統的編譯碼電路的對應模塊計算時間分別縮短為1/2t和1/n。相對于傳統的編譯器,本文提出的可重構編譯碼電路只是在其基礎上增加了4t+n個與門,加法器乘法器的開銷增加了2t+n-2,但其可重構性使其可成為常用RS標準的通用編譯碼器。

[1]王新梅,肖國鎮.糾錯碼—原理與方法[M].西安：西安電子科技大學出版社,2006.

[2]LEE M H,CHOI S B,CHANG J S.A high speed Reed-Solomon decoder[J].IEEE Transactions on Consumer Electronics,1995,41(4)：1142-1148.

[3]HSU H Y,YEO J C,WU A Y.Multi-symbol sliced dynamically reconfigurable Reed-Solomon decoder design based on unified finite field processing element[J].IEEE Transactions on Very Large Scale Integration Systems,2006,14(5)：489-499.

[4]McELIECE R.The theory of information and coding[M].2nd ed UK：Cambridge University Press,2002.

[5]HSU H Y,WANG SF,WUA Y.A novel low-cost multimode Reed-Solomon decoder design based on Peterson-Gorenstein-Zierler algorithm[J].Journal of VLSI Signal Processing,2003,34：251-259.

[6]CHAARI L,FOURATI M,MASMOUD N,et al.A reconfigurable FEC system based on Reed-Solomon codec for DVBand 802.16 network[J].WSEAS transaction on circuits and systems,2009,8(8)：729-744.

[7]SONG Leilei,YU Meilin,SHAFFER M S.10and 40Gb/s forward error correction devices for optical communications[J].IEEE Journal of Solid-State Circuits,2002,37(11)：1565-1572.

[8]李偉.面向序列密碼的反饋位移寄存器可重構并行化設計技術研究[D].鄭州：解放軍信息工程大學,2009.

[9]張天喻.基于改進型歐幾里德算法的RS譯碼研究[J].齊齊哈爾大學學報,2009,25(1)：1-5.

[10]張怡,韓維.高速RS編碼算法及FPGA實現[J].無線電通信技術,2005(1)：23-26,30.