基于G3-PLC的RS譯碼器的設計與實現

黃增先，王進華

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

?

基于G3-PLC的RS譯碼器的設計與實現

黃增先，王進華

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

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

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

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

0　引言

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

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

1　基于G3-PLC的RS碼結構

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

(1)

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

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

(2)

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

2　RS譯碼的原理與實現

基于BM迭代的譯碼算法，由于其實現過程較為簡單，譯碼速度快，是最為常用的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迭代模塊、求根模塊、福尼算法求錯誤位置系數模塊。相應的譯碼流程如圖1所示。

圖1　RS譯碼流程圖

2.1有限域查找表的構造

RS譯碼算法中的四則運算是在相應的伽羅華域中進行的，傳統的有限域乘除運算實現比較復雜，使用查表法可以簡化有限域乘法運算與求逆運算。

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

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

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

計算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);

相應計算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)

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

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

(4)

因此伴隨子計算的硬件結構可用圖3表示。

圖3　伴隨子計算結構圖

在計算伴隨子的過程中只需通過配置αi的值來得到相應的伴隨子，從而可以適應不同的碼字長度。基于G3-PLC系統的RS碼譯碼器的輸入需要進行串并轉換，所以每個碼元的輸入將保持8個時鐘周期，在每個碼元輸入的時鐘周期內配置i的值為1,2,3…8，當所有碼元輸入結束后將得到8個相應的伴隨子S1,S2,S3…S8，通過復用一次圖3所示結構單元，在每個碼元輸入的時鐘周期內配置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表示此刻對應的錯誤位置多項式的最高次冪，T表示修正項。

(3)計算下一步的修正系數：

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

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

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

步驟(2)中出現的求逆運算用2.1節中介紹的查表運算來實現，使得用傳統的BM迭代就可以高效地實現RS譯碼。

2.4錢搜索與福尼算法

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

由關鍵方程：

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

(6)

可知φ(X)的最大次數為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)

根據圖5結構求得錯誤位置多項式2t個系數后，由福尼算法得錯誤位置βk上的錯誤值δk為：

(8)

圖4　求根結構圖

圖5　錯誤位置多項式系數計算結構圖

2.5錯誤糾正

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

圖6　糾錯結構圖

3　RS譯碼器的仿真及綜合結果

3.1仿真結果

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

3.2綜合結果

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

圖7　RS譯碼器輸入時序圖

圖8　RS譯碼器輸出時序圖

4　結束語

本文闡述了基于G3-PLC的RS譯碼器的譯碼原理與實現結構。提出一種查表運算來實現有限域的乘除法運算，提高了運算速度并且實現簡單。用NC-Verilog Simulator對設計的譯碼器進行仿真驗證，給出了仿真時序圖，結果表明所設計的RS譯碼器能糾正8個符號的錯誤。最后利用Vivado對設計進行綜合，并由Xilinx xc7k160tfbg484-1 FPGA進行硬件實現。本設計所占的資源較少，不到總資源的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系統中高速RS碼的研究與實現[D]. 武漢：華中科技大學, 2012.

[3] 林舒. 差錯控制編碼[M]. 北京：機械工業出版社, 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系統的多碼率RS碼譯碼器[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設計套件Vivado應用指南[M]. 北京：清華大學出版社, 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-)，男，博士，教授，博士生導師，主要研究方向：魯棒性控制、非線性系統控制。