一種改進的RS編碼算法及其FPGA實現

吳曉軍，沈向輝，曾志斌

(中國傳媒大學廣播電視數字化教育部工程研究中心，北京 100024)

一種改進的RS編碼算法及其FPGA實現

吳曉軍，沈向輝，曾志斌

(中國傳媒大學廣播電視數字化教育部工程研究中心，北京 100024)

介紹通信系統中廣泛應用的RS編碼算法，提出了一種改進的伽羅華域的乘法器算法，從而節約了硬件資源的開銷，最終通過FPGA平臺驗證了其可行性和有效性。

RS;伽羅華域乘法器;FPGA

1 引言

RS碼(Reed-Solomon Code)是一類具有強糾錯能力的多進制BCH碼，是目前最有效、用于最廣泛的差錯控制編碼方式之一。相比于其它線性分組碼而言，在同樣的編碼效率下，RS碼具有強糾錯能力，特別對中等碼長，其糾錯性能接近于理論值。它既能糾錯隨機誤碼又能糾正突發性誤碼，因此廣泛應用于通信、數據存儲系統和數字電視傳輸中。

由于地面廣播信道是一個既有隨機錯又有突發錯的混合信道，所以RS碼成為首選對象。本文以廣泛應用于DVB系統中的RS(204，188)為例介紹其算法原理，并且提出了一種針對RS(204，188)編碼中常數項伽羅華域乘法器進行的改進方法，減少了異或門所需個數，從而節省了硬件資源，并最終對改進方案通過FPGA進行實現與驗證，測試結果證明了其可行性與有效性。

2 RS編碼原理

RS(n，k)碼，即RS(n，k，2t)，其由m，n和k三個參數表示，其中m表示碼元符號取自域GF(2^m)，n為碼字長度(n=2m-1)，k為信息長度，有k個符號。其最多可以糾正t個碼元傳輸錯誤。編碼完成后即在k個信息碼元后加了n-k個監督位。如圖1所示:RS碼的碼字多項式、信息多項式和生成多項式分別為:

圖1 RS編碼框圖

RS碼的基本思想就是選擇一個合適的多項式g(x)(生成多項式)，并且使得對每個信息段計算得到的碼字多項式都是g(x)的倍式，即使得碼字多項式除以生成多項式所得的余式為0，即:

所以其校驗位就是在有限域中經多項式運算最終得到的余數。

3 RS(204，188)編碼電路及改進方法

3.1 RS(204，188)編碼電路

由式(6)可得RS(204，188)編碼電路圖，其編碼電路為多項式運算取余數的運算過程，如圖2所示。

圖2 RS(204，188)編碼電路圖

由于RS(204，188)是RS(255，239)碼的截斷碼，即RS(204，188)其信息段前面加上41個0，即可組成RS(255，239)。即將補零后的239個碼元送入編碼器，得到16個校驗位，輸出時再去掉前面的41個為0即可。

對RS(204，188)來說，其生成多項式g(x)與本原多項式p(x)可由Matlab計算得出:

由圖2可以看出，此編碼電路得到的碼字為系統碼。信息碼元以每k個符號為一組送入編碼電路。通過對二選一控制器的控制輸出碼元，即前k個數據輸出為輸入數據，數據輸入停止，此時通過二選一控制器依次輸出移位寄存器的數據即n-k個監督位，最后得到既為n個符號的系統碼。

編碼電路主要由伽羅華域加法器、伽羅華域乘法器和移位寄存器構成，有限域的加法和乘法運算是編碼電路的核心。

3.2 伽羅華域加法器

由伽羅華域的性質可知，伽羅華域加法即為兩個加數對應位的模2加，不進位，不錯位，只需對相應位做異或運算即可實現(“+”號表示異或運算)。

3.3 伽羅華域乘法器

利用標準基實現乘法器，標準基乘法器不需要基的轉換，可以在任何系統中使用，且規則簡單，可以很容易地擴展到高階有限域。要得到A，B在GF域的乘積，先將A，B多項式相乘，然后再將二者的乘積模上本原多項式即可。

假設C表示元素A和元素B相乘的結果，則有:

計算過程和普通多項式的乘法運算一樣，因為a為p(x)的根即:

從而依次得出式(11)。

將式(11)代入式(10)得到標準基表示結果，例如C0位為:

由此得到的是通用的伽羅華域乘法器，由于在RS編碼中生成多項式g(x)是已知的，即A(X)是已知的。

因為:1＆E=E，0＆E=0。

則C的表達式可完全由B表示。(如:若A=a225=36，則其二進制表示為00100100)代入c0中可得:

由此類推可得式(14):

由式(14)可知完成該式的乘法運算共需26個異或門。

3.4 一種改進的伽羅華域乘法器

本文提出的方法對文獻［7］中方案的改進，文獻［7］以a225B為例，其利用邏輯代數的結合律將a225B化簡為如下形式:

即括號內相同組合項可以先算出，當再次出現時直接利用其計算結果，這樣既減少了重復運算又節約了異或門數。

式(15)可改寫為:

由式(16)可知，輸出C的各個比特位ci(i=0…7)所對應的輸入B的各比特位具有較多的相同組合項，可以進行進一步的組合。因此以輸出C6為例，式(15)中C6表達式為:

改進的式(16)中C6表達式為:

式(16)將式(15)中(B7+B6+B5)寫為((B7+B6)+B5)，這樣(B7+B6)又可以合并相同項，從而減少異或門數量。

并且為擴大相同組合項的個數，可以適時利用異或門性質(E=E+F+F)，兩個F可以分別和其他項進行組合，這樣綜合考慮加入F+F前與加入后其門數量，選擇最少門數方案。

通過優化此a225B共需14個異或門，比優化前節省12個異或門，比文獻［7］的優化方法節省2個異或門。

同理可得:

由式(17)可知，此乘法器共需15個異或門比優化前的28個門數節省13個異或門，比文獻［7］中節省2個異或門。

由式(18)可知，此項乘法器共需18個異或門比優化前的23個異或門節省5個異或門，比文獻［7］中節省1個異或門。

對于其他常數項乘法器可以按照此相同方法得到，由此可見通過優化減少了異或門數量，減少了硬件開銷。

4 RS(204，188)編碼器改進方案的FPGA仿真與驗證

本文采用Altera公司的EP3C16F484C6器件實現了改進后的RS(204，188)編碼器，并Verilog HDL代碼并導入至Modelim中進行仿真，如圖3所示:當編碼電路依次輸入datain=［1:188］時(1到188的188個等差數列)，可見輸出數據dataout在輸出188數據后加入了校驗位:231 90 194 142 112 85 171 63 242 251 154 1 82 33 222。這與Matlab中運用庫函數進行編碼輸出的結果一致。

圖3 RS(204，188)的 Modelim仿真結果

5 結束語

本文簡單了介紹了基于DVB系統的編碼算法原理，重點分析了RS(204，188)編碼電路中最重要的常數項伽羅華域的乘法器設計方法，并提出了一種改進方法。此法與文獻［7］中的改進方法相比，更節省了硬件開銷，最終通過FPGA平臺實現了改進方案，并通過Matlab驗證了其正確性。

［1］車晴.電子系統仿真與MATLAB［M］.北京:北京廣播學院出版社，2000.

［2］劉昌銀.基于對偶基的比特并行算法實現RS編碼［J］.北京廣播學院學報(自然科學版)，2005，12(1).

［3］Shu Lin，Daniel J Costello Jr.Error Control Coding［M］.北京:機械工程出版社，2007.

［4］曹雪虹，張宗橙.信息論與編碼［M］.北京:清華大學出版社，2009.

［5］姜丹.信息論與編碼［M］.北京:中國科學技術大學出版社，2009.

［6］劉福奇，劉波.Verilog HDL應用程序設計實例精講［M］.北京:電子工業出版社，2009.

［7］付興，樊孝明.一種低復雜度RS編碼器的FPGA實現［J］.電視技術，2011，35(9).

［8］陳曦，邱志成，等.基于Verilog HDL的通信系統設計［M］，北京:中國水利水電出版社，2009.

An Improved RS Encoding Algorithm and FPGA Implementation

WU Xiao-jun，SHEN Xiang-hui，ZENG Zhi-bin
(ECDAV，Communication University of China ，Beijing 100024，China)

The RS encoding algorithm widely used in communication system is introduced.And an improved algorithm on Galois Field multiplier is proposed which saves the hardware resources.Finally，its feasibility and validity have been verified through FPGA platform.

RS;galois field;FPGA

TN911.7

A

1673-4793(2012)01-0073-06

2011-12-23

吳曉軍(1986-)，男(漢族)，山東人，中國傳媒大學碩士研究生.E-mail:wxj0918001@163.com

(責任編輯

:王 謙)