黃增先,，王進華

　?。ǜＶ荽髮W(xué) 電氣工程與自動化學(xué)院，福建 福州 350108）

       摘要：針對G3-PLC物理層信道編碼的要求,，設(shè)計了一種RS譯碼器,。為了解決譯碼過程中有限域乘法器存在的連線復(fù)雜、運算速度慢等問題,，設(shè)計了一種查表運算,。采用該查表運算可以快速實現(xiàn)有限域的乘法運算，并且可以簡化BerlekampMassey (BM)迭代過程中的求逆運算,，使得用傳統(tǒng)的BM迭代就可以高效地實現(xiàn)RS譯碼,。結(jié)合FPGA平臺，利用Verilog硬件描述語言和Vivado軟件對譯碼器進行設(shè)計與實現(xiàn),。時序仿真結(jié)果與綜合結(jié)果表明，該譯碼器資源占用率低,，能夠在100 MHz系統(tǒng)時鐘下進行有效譯碼,。

　　關(guān)鍵詞：G3-PLC;RS譯碼器;FPGA;BM迭代

0引言

　　G3-PLC是由G3-PLC聯(lián)盟于2009年推出的窄帶電力線通信規(guī)范，目前已經(jīng)得到多個國際標(biāo)準(zhǔn)體系的認可,，并被幾個主要國際電表商采納,。電力線信道條件惡劣，存在多種干擾,，使得數(shù)據(jù)在電力線上傳輸誤碼率較大,。RS碼在糾正隨機錯誤和突發(fā)錯誤方面效果顯著，在G3-PLC信道編碼系統(tǒng)中,，添加RS模塊比未加RS模塊在10-4 BER(Bit Error Rate)條件下至少多了1 dB的編碼增益［1］,，這充分說明了RS碼在G3-PLC系統(tǒng)中的重要性，它能夠有效提高系統(tǒng)通信的可靠性,。

　　RS譯碼過程的運算定義在有限域上,，因此有限域運算的設(shè)計對譯碼器的整體性能具有重大的意義。有限域運算的主要難點在于有限域乘法運算和有限域求逆（除法）運算的硬件設(shè)計,。目前,，有限域乘法器的電路實現(xiàn)主要有比特串行結(jié)構(gòu)和比特并行結(jié)構(gòu)［2］。比特串行結(jié)構(gòu)采用時序電路設(shè)計,，具有占用資源少的優(yōu)點,，但運算速度較慢。比特并行結(jié)構(gòu)采用組合邏輯結(jié)構(gòu)來實現(xiàn),，運算速度快,，但連線復(fù)雜。根據(jù)伽羅華域的性質(zhì)，可以將有限域求逆運算轉(zhuǎn)化為乘法運算［3］,，因此可用有限域乘法器實現(xiàn)求逆運算,，但還是難以避免有限域乘法器本身所具有的缺點。為避免求逆運算的復(fù)雜度過大,，人們提出了改進的BM算法,，使BM迭代的過程中無需求逆運算［4-5］。無求逆的BM算法可以有效避免求逆運算,，但算法的證明復(fù)雜,。針對上述問題，本文提出了一種查表法來實現(xiàn)有限域乘法與求逆運算,，簡化了有限求逆運算硬件實現(xiàn)的復(fù)雜度,，使得用傳統(tǒng)的BM迭代就可以高效地實現(xiàn)RS譯碼。

1基于G3-PLC的RS碼結(jié)構(gòu)

　　RS碼是非二進制BCH碼的一個重要子類,。RS碼的最小距離等于它的奇偶校驗符號數(shù)加一,，是GF(2m)上具有極大最小距離的線性分組碼?；贕3-PLC的RS碼的生成多項式為：

　　其中α為伽羅華GF(28)上的本原元素,，t=8為可糾正符號數(shù)［67］。相應(yīng)的本原多項式為：

　　G3-PLC系統(tǒng)中根據(jù)不同的通信速率與信道環(huán)境,，物理層選擇不同的符號數(shù)和調(diào)制方式,，因此造成碼字長度不同。當(dāng)調(diào)制方式為DQPSK時,，總共有6種可選的碼字長度,，分別為：(251/235)、(233/217),、(179/163),、(143/127)、(89/73)和(53/37),，這些碼字都是RS(255/239)的縮短碼,，具有相同的譯碼結(jié)構(gòu)與糾錯能力，因此文中以RS(251/235)為例進行設(shè)計與實現(xiàn),。

2RS譯碼的原理與實現(xiàn)

　　基于BM迭代的譯碼算法,，由于其實現(xiàn)過程較為簡單，譯碼速度快,，是最為常用的RS譯碼算法,。譯碼的一般步驟為：

　　(1)計算接收碼字R(X)的2t個伴隨式Si,i=l，2,，…2t,；

　　(2)利用BM迭代算法求出錯誤位置多項式,；

　　(3)利用錢搜索(Chien Search)求解錯誤位置多項式的根以確定錯誤位置；

　　(4)利用福尼算法求出錯誤位置上的錯誤值,；

　　(5)由以上步驟得到錯誤多項式E(X),，則糾錯后的碼字多項式為：

　　由上述步驟可知，RS譯碼器必須包含4個模塊,，即伴隨子求解模塊,、BM迭代模塊、求根模塊,、福尼算法求錯誤位置系數(shù)模塊,。相應(yīng)的譯碼流程如圖1所示。

　　2.1有限域查找表的構(gòu)造

　　RS譯碼算法中的四則運算是在相應(yīng)的伽羅華域中進行的,，傳統(tǒng)的有限域乘除運算實現(xiàn)比較復(fù)雜,，使用查表法可以簡化有限域乘法運算與求逆運算。

　　伽羅華域元素通常有向量表示形式和冪次表示形式,，比如GF(28)中元素α1的向量表示形式為(00000010),，其中向量表示形式有利于有限域加法運算，而冪次表示形式有利于乘,、除法運算,。查表運算的過程是通過查表來實現(xiàn)伽羅華元素向量表示形式與冪次表示形式的互相轉(zhuǎn)換，這樣就可以根據(jù)相應(yīng)的運算要求來切換伽羅華域元素的表示形式以達到簡化運算的目的,。構(gòu)造圖2所示兩個存儲空間，分別用來存儲GF(28)域中元素的冪次形式與向量形式,。

　　在進行伽羅華元素乘法運算時,，首先將向量形式轉(zhuǎn)化為冪次形式，進行冪次相加對應(yīng)的就是乘法運算,，冪次相減對應(yīng)的就是除法運算,，接著判斷向量形式中的元素是否有0變量，如果有則向量域地址為0,，沒有則將冪次域和對255取模加1后的值作為向量域的地址,。最后將運算結(jié)果重新轉(zhuǎn)化為向量形式。

　　計算a×b偽代碼如下：

　　y1=Men_a(a);

　　y2=Men_a(b);

　　y3=y1+y2;

　　if(y1==11111111||y2==11111111)

　　y4=0000000;

　　else

　　y4=Men_b(mod(y3,255)+1);

　　相應(yīng)計算a÷b即a×b-1的偽代碼為：

　　y1=Men_a(a);

　　y2=Men_a(b);

　　y3=y1-y2;

　　if(y1==11111111||y2==11111111)

　　y4=0000000;

　　else

　　y4=Men_b(mod(y3,255)+1);

　　2.2伴隨子計算

　　假定接收多項式為：

　　R(X)=r0+r1X+r2X2+…+rn-1Xn-1

　　則由

　　Si=R(αi),1i2t

　　得：

　　Si=r0+r1αi+r2α2i+…+rn-1αi(n-1)

　　直接用該式進行硬件實現(xiàn)時需要相應(yīng)配置碼字的長度,，這在實現(xiàn)過程中比較繁瑣,，因為G3-PLC系統(tǒng)中，采用DQPSK調(diào)制時有6種可選的碼字長度,，這就需要配置6種不同伴隨子計算模式,。將伴隨子的計算式稍作變形可得：

　　因此伴隨子計算的硬件結(jié)構(gòu)可用圖3表示?！?/p>

在計算伴隨子的過程中只需通過配置αi的值來得到相應(yīng)的伴隨子,，從而可以適應(yīng)不同的碼字長度,。基于G3-PLC系統(tǒng)的RS碼譯碼器的輸入需要進行串并轉(zhuǎn)換,，所以每個碼元的輸入將保持8個時鐘周期,，在每個碼元輸入的時鐘周期內(nèi)配置i的值為1,2,3…8，當(dāng)所有碼元輸入結(jié)束后將得到8個相應(yīng)的伴隨子S1,S2,S3…S8,，通過復(fù)用一次圖3所示結(jié)構(gòu)單元,，在每個碼元輸入的時鐘周期內(nèi)配置i的值為9,10,11…16，可得到S9,S10,S11…S16,。

　　2.3BM迭代

　　定義錯誤位置多項式σ(X)為：

　　其中βi表示錯誤位置,，BM迭代的具體過程如下：

　　（1)初始化,。令k=1,，σ(1)(X)=1，d1=S1,，T(1)(X)=X,，N1=0。其中N表示此刻對應(yīng)的錯誤位置多項式的最高次冪,，T表示修正項,。

　　（2)判斷修正系數(shù)dk是否等于0,。如果dk≠0,，則σ(k+1)(X)=σ(k)(X)+dkT(k)(X)，接著計算T(k+1)(X),，首先判斷2Nk是否大于等于k,，如果2Nk<k，則T(k+1)(X)=d-1kX1σ(k)(X),；如果2Nkk,，則T(k+1)(X)=X1T(k)(X)。如果dk=0,，則σ(k+1)(X)=σ(k)(X),，T(k+1)(X)=X1T(k)(X)。

　?。?)計算下一步的修正系數(shù)：

　　dk+1=Sk+1+∑°σ(k+1)(X)i=1Sk+1-iσi

　　其中°σ(k+1)(X)表示σ(k+1)(X)的最高次數(shù),。更新Nk+1的值，即Nk+1=k-N,。

　?。?)更新k的值，即k=k+1,。

　?。?)判斷k是否小于2t,。如果k<2t ，則回到步驟（2）,；如果k=2t,，則σ(2t)(X)就是錯誤位置多項式。

　　步驟（2）中出現(xiàn)的求逆運算用2.1節(jié)中介紹的查表運算來實現(xiàn),，使得用傳統(tǒng)的BM迭代就可以高效地實現(xiàn)RS譯碼,。

　　2.4錢搜索與福尼算法

　　求解σ(X)的根，由于σ0=1,，所以0元素不是σ(X)的根,，因此將伽羅華域GF(28)中的所有非零元素一個一個代入錯誤位置多項式σ(X)中，求得的根取其乘法逆元就可以得到錯誤位置,。最后用圖4結(jié)構(gòu)來實現(xiàn),，第一個時鐘周期不進行乘法運算，相當(dāng)于判斷σ(α0)是否等于0,，從第二個時鐘周期開始先進行乘法運算,，再求和判斷。經(jīng)過255個時鐘周期就可以遍歷GF(28)所有非0元素,。

　　由關(guān)鍵方程：

　　

　　可知(X)的最大次數(shù)為2t-1,，因此定義：

　　所以有錯誤值多項式：

　

　　根據(jù)圖5結(jié)構(gòu)求得錯誤位置多項式2t個系數(shù)后，由福尼算法得錯誤位置βk上的錯誤值δk為：

　　2.5錯誤糾正

　　經(jīng)過上述操作可求得錯誤位置以及錯誤位置上的錯誤值,。將σ(X)的根進行查表求逆后可得錯誤位置,，將這個錯誤位置值作為碼字緩存空間的讀地址，讀出錯誤碼字后與相應(yīng)的錯誤值進行異或運算,，得到的更新值重新寫回原先的地址,，使錯誤碼字得到修正。具體結(jié)構(gòu)如圖6所示,。　

3RS譯碼器的仿真及綜合結(jié)果

　　3.1仿真結(jié)果

　　為了便于觀測結(jié)果,，將第一幀待編碼字設(shè)為［235:1］,，令編碼后的前8個位置為錯誤位置，使得接收值為［8 7 6 5 4 3 2 1］,，即將［8(235) 7(234) 6(233) 5(232) 4(231) 3(230) 2(229) 1(228) 227…206 122 61］作為譯碼器輸入的第一幀,，其中括號內(nèi)為正確值。利用Candence公司的NC-Verilog Simulator對設(shè)計進行仿真,，通過仿真圖7,、8可以看出，8個錯誤全部得到糾正,。

　　3.2綜合結(jié)果

　　通過Vivado 進行綜合與實現(xiàn),，并利用Xilinx xc7k160tfbg4841 FPGA進行硬件實現(xiàn),。實現(xiàn)過程中用到的RAM和ROM由Vivodo中IP Catalog［8］產(chǎn)生。最終,，BM迭代模塊,、糾錯模塊、求根模塊,、錯誤值計算以及伴隨子計算模塊分別用了517,、721、413,、572,、525個LUT單元。在100 MHz時鐘約束下建立時間與保持時間都留有裕量,，說明譯碼器的工作頻率至少可以達到100 MHz,。

4結(jié)束語

　　本文闡述了基于G3-PLC的RS譯碼器的譯碼原理與實現(xiàn)結(jié)構(gòu)。提出一種查表運算來實現(xiàn)有限域的乘除法運算,，提高了運算速度并且實現(xiàn)簡單,。用NCVerilog Simulator對設(shè)計的譯碼器進行仿真驗證，給出了仿真時序圖,，結(jié)果表明所設(shè)計的RS譯碼器能糾正8個符號的錯誤,。最后利用Vivado對設(shè)計進行綜合，并由Xilinx xc7k160tfbg4841 FPGA進行硬件實現(xiàn),。本設(shè)計所占的資源較少,，不到總資源的3%。

　　參考文獻

　?。?］ RAZAZIAN K, UMARI M, KAMALIZAD A. Error correction mechanism in the new G3PLC specification for powerline communication［C］. Power Line Communications and Its Applications (ISPLC), 2010 IEEE International Symposium on. IEEE, 2010:5055.［2］ 聶鵬. OFDM系統(tǒng)中高速RS碼的研究與實現(xiàn)［D］. 武漢：華中科技大學(xué), 2012.

　?。?］ 林舒. 差錯控制編碼［M］. 北京：機械工業(yè)出版社, 2007.

　　［4］ DAS A S, DAS S, BHAUMIK J. Design of RS (255, 251) encoder and decoder in FPGA［J］. International Journal of Soft Computing & Engineering, 2013, 2(6):391394.

　?。?］ 石宇, 黑勇, 喬樹山. 一種用于PLC系統(tǒng)的多碼率

　　RS碼譯碼器［J］. 微電子學(xué)與計算機, 2014(2):5761.

　?。?］ RAZAZIAN K, UMARI M, KAMALIZAD A, et al. G3PLC specification for powerline communication: overview, system simulation and field trial results［C］. IEEE International Symposium on Power Line Communications and ITS Applications, 2010:313318.

　　［7］ Electricite Reseau Distribution France. G3PLC Physical Layer Specification［Z］.2009.

　?。?］ 孟憲元. Xilinx新一代FPGA設(shè)計套件Vivado應(yīng)用指南［M］. 北京：清華大學(xué)出版社, 2014.