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

吳曉軍，沈向輝，曾志斌

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

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

吳曉軍，沈向輝，曾志斌

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

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

RS;伽羅華域乘法器;FPGA

1 引言

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

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

2 RS編碼原理

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

圖1 RS編碼框圖

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

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

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

3.1 RS(204，188)編碼電路

由式(6)可得RS(204，188)編碼電路圖，其編碼電路為多項(xiàng)式運(yùn)算取余數(shù)的運(yùn)算過(guò)程，如圖2所示。

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

由于RS(204，188)是RS(255，239)碼的截?cái)啻a，即RS(204，188)其信息段前面加上41個(gè)0，即可組成RS(255，239)。即將補(bǔ)零后的239個(gè)碼元送入編碼器，得到16個(gè)校驗(yàn)位，輸出時(shí)再去掉前面的41個(gè)為0即可。

對(duì)RS(204，188)來(lái)說(shuō)，其生成多項(xiàng)式g(x)與本原多項(xiàng)式p(x)可由Matlab計(jì)算得出:

由圖2可以看出，此編碼電路得到的碼字為系統(tǒng)碼。信息碼元以每k個(gè)符號(hào)為一組送入編碼電路。通過(guò)對(duì)二選一控制器的控制輸出碼元，即前k個(gè)數(shù)據(jù)輸出為輸入數(shù)據(jù)，數(shù)據(jù)輸入停止，此時(shí)通過(guò)二選一控制器依次輸出移位寄存器的數(shù)據(jù)即n-k個(gè)監(jiān)督位，最后得到既為n個(gè)符號(hào)的系統(tǒng)碼。

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

3.2 伽羅華域加法器

由伽羅華域的性質(zhì)可知，伽羅華域加法即為兩個(gè)加數(shù)對(duì)應(yīng)位的模2加，不進(jìn)位，不錯(cuò)位，只需對(duì)相應(yīng)位做異或運(yùn)算即可實(shí)現(xiàn)(“+”號(hào)表示異或運(yùn)算)。

3.3 伽羅華域乘法器

利用標(biāo)準(zhǔn)基實(shí)現(xiàn)乘法器，標(biāo)準(zhǔn)基乘法器不需要基的轉(zhuǎn)換，可以在任何系統(tǒng)中使用，且規(guī)則簡(jiǎn)單，可以很容易地?cái)U(kuò)展到高階有限域。要得到A，B在GF域的乘積，先將A，B多項(xiàng)式相乘，然后再將二者的乘積模上本原多項(xiàng)式即可。

假設(shè)C表示元素A和元素B相乘的結(jié)果，則有:

計(jì)算過(guò)程和普通多項(xiàng)式的乘法運(yùn)算一樣，因?yàn)閍為p(x)的根即:

從而依次得出式(11)。

將式(11)代入式(10)得到標(biāo)準(zhǔn)基表示結(jié)果，例如C0位為:

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

因?yàn)?1＆E=E，0＆E=0。

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

由此類推可得式(14):

由式(14)可知完成該式的乘法運(yùn)算共需26個(gè)異或門(mén)。

3.4 一種改進(jìn)的伽羅華域乘法器

本文提出的方法對(duì)文獻(xiàn)［7］中方案的改進(jìn)，文獻(xiàn)［7］以a225B為例，其利用邏輯代數(shù)的結(jié)合律將a225B化簡(jiǎn)為如下形式:

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

式(15)可改寫(xiě)為:

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

改進(jìn)的式(16)中C6表達(dá)式為:

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

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

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

同理可得:

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

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

對(duì)于其他常數(shù)項(xiàng)乘法器可以按照此相同方法得到，由此可見(jiàn)通過(guò)優(yōu)化減少了異或門(mén)數(shù)量，減少了硬件開(kāi)銷。

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

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

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

5 結(jié)束語(yǔ)

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

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

［2］劉昌銀.基于對(duì)偶基的比特并行算法實(shí)現(xiàn)RS編碼［J］.北京廣播學(xué)院學(xué)報(bào)(自然科學(xué)版)，2005，12(1).

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

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

［5］姜丹.信息論與編碼［M］.北京:中國(guó)科學(xué)技術(shù)大學(xué)出版社，2009.

［6］劉福奇，劉波.Verilog HDL應(yīng)用程序設(shè)計(jì)實(shí)例精講［M］.北京:電子工業(yè)出版社，2009.

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

［8］陳曦，邱志成，等.基于Verilog HDL的通信系統(tǒng)設(shè)計(jì)［M］，北京:中國(guó)水利水電出版社，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-)，男(漢族)，山東人，中國(guó)傳媒大學(xué)碩士研究生.E-mail:wxj0918001@163.com

(責(zé)任編輯

:王 謙)