吳曉軍，沈向輝，曾志斌

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

一種改進的RS編碼算法及其FPGA實現(xiàn)

吳曉軍，沈向輝，曾志斌

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

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

RS;伽羅華域乘法器;FPGA

1 引言

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

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

2 RS編碼原理

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

圖1 RS編碼框圖

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

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

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

3.1 RS(204，188)編碼電路

由式(6)可得RS(204，188)編碼電路圖，其編碼電路為多項式運算取余數(shù)的運算過程，如圖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可以看出，此編碼電路得到的碼字為系統(tǒng)碼。信息碼元以每k個符號為一組送入編碼電路。通過對二選一控制器的控制輸出碼元，即前k個數(shù)據(jù)輸出為輸入數(shù)據(jù)，數(shù)據(jù)輸入停止，此時通過二選一控制器依次輸出移位寄存器的數(shù)據(jù)即n-k個監(jiān)督位，最后得到既為n個符號的系統(tǒng)碼。

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

3.2 伽羅華域加法器

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

3.3 伽羅華域乘法器

利用標準基實現(xiàn)乘法器，標準基乘法器不需要基的轉換，可以在任何系統(tǒng)中使用，且規(guī)則簡單，可以很容易地擴展到高階有限域。要得到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為例，其利用邏輯代數(shù)的結合律將a225B化簡為如下形式:

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

式(15)可改寫為:

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

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

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

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

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

同理可得:

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

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

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

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

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

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

5 結束語

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

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

［2］劉昌銀.基于對偶基的比特并行算法實現(xiàn)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］.北京:電子工業(yè)出版社，2009.

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

［8］陳曦，邱志成，等.基于Verilog HDL的通信系統(tǒng)設計［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

(責任編輯

:王 謙)