黃增先，王進(jìn)華

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

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

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

0引言

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

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

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

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

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

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

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

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

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

　　(2)利用BM迭代算法求出錯(cuò)誤位置多項(xiàng)式；

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

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

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

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

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

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

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

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

　　計(jì)算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)計(jì)算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伴隨子計(jì)算

　　假定接收多項(xiàng)式為：

　　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)

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

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

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

　　2.3BM迭代

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

　　其中βi表示錯(cuò)誤位置，BM迭代的具體過(guò)程如下：

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

　　（2)判斷修正系數(shù)dk是否等于0。如果dk≠0，則σ(k+1)(X)=σ(k)(X)+dkT(k)(X)，接著計(jì)算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)。

　?。?)計(jì)算下一步的修正系數(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。

　　（4)更新k的值，即k=k+1。

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

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

　　2.4錢搜索與福尼算法

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

　　由關(guān)鍵方程：

　　

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

　　所以有錯(cuò)誤值多項(xiàng)式：

　

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

　　2.5錯(cuò)誤糾正

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

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

　　3.1仿真結(jié)果

　　為了便于觀測(cè)結(jié)果，將第一幀待編碼字設(shè)為［235:1］，令編碼后的前8個(gè)位置為錯(cuò)誤位置，使得接收值為［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］作為譯碼器輸入的第一幀，其中括號(hào)內(nèi)為正確值。利用Candence公司的NC-Verilog Simulator對(duì)設(shè)計(jì)進(jìn)行仿真，通過(guò)仿真圖7、8可以看出，8個(gè)錯(cuò)誤全部得到糾正。

　　3.2綜合結(jié)果

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

4結(jié)束語(yǔ)

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

　　參考文獻(xiàn)

　　［1］ 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碼的研究與實(shí)現(xiàn)［D］. 武漢：華中科技大學(xué), 2012.

　?。?］ 林舒. 差錯(cuò)控制編碼［M］. 北京：機(jī)械工業(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.

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

　　RS碼譯碼器［J］. 微電子學(xué)與計(jì)算機(jī), 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.

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

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