黃增先，王進華

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

?

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

黃增先，王進華

(福州大學(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)時鐘下進行有效譯碼。

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

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

0　引言

G3-PLC是由G3-PLC聯(lián)盟于2009年推出的窄帶電力線通信規(guī)范，目前已經(jīng)得到多個國際標準體系的認可，并被幾個主要國際電表商采納。電力線信道條件惡劣，存在多種干擾，使得數(shù)據(jù)在電力線上傳輸誤碼率較大。RS碼在糾正隨機錯誤和突發(fā)錯誤方面效果顯著，在G3-PLC信道編碼系統(tǒng)中，添加RS模塊比未加RS模塊在10-4BER(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碼的生成多項式為：

(1)

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

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

(2)

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)。

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

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

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

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

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

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

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

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

(3)

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

圖1　RS譯碼流程圖

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)域中元素的冪次形式與向量形式。

圖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種不同伴隨子計算模式。將伴隨子的計算式稍作變形可得：

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

(4)

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

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

在計算伴隨子的過程中只需通過配置αi的值來得到相應(yīng)的伴隨子，從而可以適應(yīng)不同的碼字長度?；贕3-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)為：

(5)

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

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

(3)計算下一步的修正系數(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)就是錯誤位置多項式。

步驟(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)={S(X)σ(X)}modX2t

(6)

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

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

所以有錯誤值多項式：

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

(7)

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

(8)

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

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

2.5錯誤糾正

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

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

3　RS譯碼器的仿真及綜合結(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。

圖7　RS譯碼器輸入時序圖

圖8　RS譯碼器輸出時序圖

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%。

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

[3] 林舒. 差錯控制編碼[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.

[5] 石宇, 黑勇, 喬樹山. 一種用于PLC系統(tǒng)的多碼率RS碼譯碼器[J]. 微電子學(xué)與計算機, 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è)計套件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-)，男，碩士研究生，主要研究方向：電力線通信。

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