RS編譯碼電路的可重構(gòu)性研究

譚思煒, 潘紅兵, 龍宏波

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

0 引言

可重構(gòu)性是指同一系統(tǒng)的硬件或軟件模塊根據(jù)數(shù)據(jù)流或控制流的輸入重新配置,改變電路結(jié)構(gòu)或模塊功能,滿足新的任務(wù)需求。目前可編程集成芯片大規(guī)模運(yùn)用在通信系統(tǒng)設(shè)計(jì)領(lǐng)域,給可重構(gòu)電路的實(shí)現(xiàn)帶來可能。本文根據(jù)集成芯片的可編程特點(diǎn),以可重構(gòu)的思想對(duì)傳統(tǒng)的編譯碼電路進(jìn)行修改,使其能依據(jù)不同通信系統(tǒng)RS(Reed-Solomon)碼標(biāo)準(zhǔn)的配置信息,實(shí)現(xiàn)對(duì)應(yīng)的編譯碼過程。

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

1 可重構(gòu)RS編碼電路

得其具有較強(qiáng)的突發(fā)糾錯(cuò)能力。定義2t=n-k,t表示RS碼是由生成多項(xiàng)式G(x)定義的一組線性循環(huán)碼RS(n,k),k表示數(shù)據(jù)符號(hào)碼長(zhǎng),n表示包括數(shù)據(jù)符號(hào)和校驗(yàn)符號(hào)在內(nèi)的碼長(zhǎng)。RS碼非二進(jìn)制的屬性使RS碼的糾錯(cuò)能力,即最多糾正t個(gè)符號(hào)的錯(cuò)誤。

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

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

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

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

圖2 可重構(gòu)RS編碼電路Fig.2 A configurable RS encoding circuit

如果需要配置的寄存器個(gè)數(shù)小于22個(gè),則配置信息逐位設(shè)置0或1從左往右通過依次關(guān)掉與門來關(guān)掉不需要的寄存器,直到剩下的寄存器組可以構(gòu)成對(duì)應(yīng)標(biāo)準(zhǔn)所需的LFSR為止。

2 可重構(gòu)RS譯碼電路

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

2.1 可重構(gòu)伴隨多項(xiàng)式計(jì)算

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

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

圖3 Si迭代計(jì)算模塊Fig.3 Siiterative computation block

圖4 可重構(gòu)伴隨多項(xiàng)式計(jì)算電路Fig.4 Reconfigurable syndrome computation circuit

2.2 關(guān)鍵方程求解

定義錯(cuò)誤位置多項(xiàng)式：

其中：v表示錯(cuò)誤個(gè)數(shù)。錯(cuò)誤多項(xiàng)式是用來定義某位接收碼字上的錯(cuò)誤,顯然v≤t,表示錯(cuò)誤個(gè)數(shù)應(yīng)該在RS碼的糾錯(cuò)范圍內(nèi)。如果rk上發(fā)生錯(cuò)誤,則有σ(α-k)=0。

定義錯(cuò)位值多項(xiàng)式：

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

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

1)初始化。

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

圖5 改進(jìn)歐幾里德迭代運(yùn)算模塊Fig.5 Iterative computation block of modified Euclidean algorithm

圖6 解關(guān)鍵方程的可重構(gòu)電路結(jié)構(gòu)Fig.6 Reconfigurable key equation circuit

2.3 錢氏搜索與糾錯(cuò)

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

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

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

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

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

圖8 錯(cuò)誤值計(jì)算Fig.8 Error value computation

錯(cuò)誤值計(jì)算的可重構(gòu)結(jié)構(gòu)如圖9所示,設(shè)錯(cuò)誤值計(jì)算模塊個(gè)數(shù)為255,并行計(jì)算n位接收碼的錯(cuò)誤值,提高計(jì)算速度。根據(jù)不同RS碼標(biāo)準(zhǔn),輸入配置信息,選擇相應(yīng)數(shù)量的錯(cuò)誤值計(jì)算模塊。

圖9 錯(cuò)誤值計(jì)算的可重構(gòu)結(jié)構(gòu)Fig.9 Reconfigurable error value computation structure

3 結(jié)論

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

[1]王新梅,肖國(guó)鎮(zhèn).糾錯(cuò)碼—原理與方法[M].西安：西安電子科技大學(xué)出版社,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]李偉.面向序列密碼的反饋位移寄存器可重構(gòu)并行化設(shè)計(jì)技術(shù)研究[D].鄭州：解放軍信息工程大學(xué),2009.

[9]張?zhí)煊?基于改進(jìn)型歐幾里德算法的RS譯碼研究[J].齊齊哈爾大學(xué)學(xué)報(bào),2009,25(1)：1-5.

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