基于G3-PLC的RS譯碼器的設(shè)計(jì)與實(shí)現(xiàn)

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

(福州大學(xué) 電氣工程與自動(dòng)化學(xué)院，福建 福州 350108)

?

基于G3-PLC的RS譯碼器的設(shè)計(jì)與實(shí)現(xiàn)

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

(福州大學(xué) 電氣工程與自動(dòng)化學(xué)院，福建 福州 350108)

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

G3-PLC;RS譯碼器;FPGA;BM迭代

引用格式：黃增先，王進(jìn)華. 基于G3-PLC的RS譯碼器的設(shè)計(jì)與實(shí)現(xiàn)[J].微型機(jī)與應(yīng)用，2016,35(17)：68-71.

0　引言

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

RS譯碼過程的運(yùn)算定義在有限域上，因此有限域運(yùn)算的設(shè)計(jì)對譯碼器的整體性能具有重大的意義。有限域運(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)來實(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ù)雜度過大，人們提出了改進(jìn)的BM算法，使BM迭代的過程中無需求逆運(yùn)算[4-5]。無求逆的BM算法可以有效避免求逆運(yùn)算，但算法的證明復(fù)雜。針對上述問題，本文提出了一種查表法來實(shí)現(xiàn)有限域乘法與求逆運(yù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)符號數(shù)加一，是GF(2m)上具有極大最小距離的線性分組碼。基于G3-PLC的RS碼的生成多項(xiàng)式為：

(1)

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

p(X)=X8+X7+X2+X+1

(2)

G3-PLC系統(tǒng)中根據(jù)不同的通信速率與信道環(huán)境，物理層選擇不同的符號數(shù)和調(diào)制方式，因此造成碼字長度不同。當(dāng)調(diào)制方式為DQPSK時(shí)，總共有6種可選的碼字長度，分別為：(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)。

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

基于BM迭代的譯碼算法，由于其實(shí)現(xià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)式為：

V(X)=R(X)+E(X)

(3)

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

圖1　RS譯碼流程圖

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

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

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

圖2　GF(28)域元素存儲(chǔ)空間圖

在進(jìn)行伽羅華元素乘法運(yùn)算時(shí)，首先將向量形式轉(zhuǎn)化為冪次形式，進(jìn)行冪次相加對應(yīng)的就是乘法運(yùn)算，冪次相減對應(yīng)的就是除法運(yùn)算，接著判斷向量形式中的元素是否有0變量，如果有則向量域地址為0，沒有則將冪次域和對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)配置碼字的長度，這在實(shí)現(xiàn)過程中比較繁瑣，因?yàn)镚3-PLC系統(tǒng)中，采用DQPSK調(diào)制時(shí)有6種可選的碼字長度，這就需要配置6種不同伴隨子計(jì)算模式。將伴隨子的計(jì)算式稍作變形可得：

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

(4)

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

圖3　伴隨子計(jì)算結(jié)構(gòu)圖

在計(jì)算伴隨子的過程中只需通過配置αi的值來得到相應(yīng)的伴隨子，從而可以適應(yīng)不同的碼字長度。基于G3-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，通過復(fù)用一次圖3所示結(jié)構(gòu)單元，在每個(gè)碼元輸入的時(shí)鐘周期內(nèi)配置i的值為9,10,11…16，可得到S9,S10,S11…S16。

2.3BM迭代

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

(5)

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

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

(3)計(jì)算下一步的修正系數(shù)：

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

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

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

步驟(2)中出現(xiàn)的求逆運(yùn)算用2.1節(jié)中介紹的查表運(yùn)算來實(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)來實(shí)現(xiàn)，第一個(gè)時(shí)鐘周期不進(jìn)行乘法運(yùn)算，相當(dāng)于判斷σ(α0)是否等于0，從第二個(gè)時(shí)鐘周期開始先進(jìn)行乘法運(yùn)算，再求和判斷。經(jīng)過255個(gè)時(shí)鐘周期就可以遍歷GF(28)所有非0元素。

由關(guān)鍵方程：

φ(X)={S(X)σ(X)}modX2t

(6)

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

S(X)=S1+S2X1+S3X2+…+S2tX2t-1

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

φ(X)=S1+(S2+σ1S1)X+(S3+σ1S2+σ2S1)X2+…+(S2t+σ1S2t-1+…+σvS2t-v)X2t-1

(7)

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

(8)

圖4　求根結(jié)構(gòu)圖

圖5　錯(cuò)誤位置多項(xiàng)式系數(shù)計(jì)算結(jié)構(gòu)圖

2.5錯(cuò)誤糾正

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

圖6　糾錯(cuò)結(jié)構(gòu)圖

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

3.1仿真結(jié)果

為了便于觀測結(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]作為譯碼器輸入的第一幀，其中括號內(nèi)為正確值。利用Candence公司的NC-Verilog Simulator對設(shè)計(jì)進(jìn)行仿真，通過仿真圖7、8可以看出，8個(gè)錯(cuò)誤全部得到糾正。

3.2綜合結(jié)果

通過Vivado 進(jìn)行綜合與實(shí)現(xiàn)，并利用Xilinx xc7k160tfbg484-1 FPGA進(jìn)行硬件實(shí)現(xiàn)。實(shí)現(xiàn)過程中用到的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í)間都留有裕量，說明譯碼器的工作頻率至少可以達(dá)到100 MHz。

圖7　RS譯碼器輸入時(shí)序圖

圖8　RS譯碼器輸出時(shí)序圖

4　結(jié)束語

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

[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.

[3] 林舒. 差錯(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.

[5] 石宇, 黑勇, 喬樹山. 一種用于PLC系統(tǒng)的多碼率RS碼譯碼器[J]. 微電子學(xué)與計(jì)算機(jī), 2014(2):57-61.

[6] 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.

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

Design and implementation of RS decoder based on G3-PLC

Huang Zengxian,Wang Jinhua

(School of Electrical Engineering and Automation, Fuzhou University, Fuzhou 350108, China)

A kind of RS decoder is designed according to the requirements of G3-PLC physical layer channel encoding. A table-referring is designed in order to solve the problems such as complex connections, slow speed operation that exist in finite field multipliers. Using the look-up table operation can quickly realize the finite field multiplication, simplify the Berlekamp-Massey iterative, and efficiently realize the RS decoding with traditional BM iterative. On the FPGA platform, the design has been implemented by using the Verilog hardware description language and Vivado software. Timing simulation and synthesis results indicate that the decoder has low resource utilization and can efficiently work under the 100 MHz system clock.

G3-PLC; RS decoder; FPGA; BM iteration

TN919.3

ADOI： 10.19358/j.issn.1674- 7720.2016.17.021

2016-05-06)

黃增先(1990-)，男，碩士研究生，主要研究方向：電力線通信。

王進(jìn)華(1963-)，男，博士，教授，博士生導(dǎo)師，主要研究方向：魯棒性控制、非線性系統(tǒng)控制。