RS码译码算法与译码器的DSP实现方法

第24卷第2期

2004年4月

　JournalOfNortheastChinaInstituteOfElectricPowerEngineering

Vol.24,No.2Apr.,2004

文章编号:1005-2992(2004)02-0014-04

RS码译码算法与译码器的DSP实现方法

戴伏生1,朱　亮2,王春虎3

(1.哈尔滨工业大学[威海分校],山东威海2209;2.哈尔滨工业大学航天学院,哈尔滨150001;3.黑龙江省电

力有限公司调度中心调度处,黑龙江哈尔滨150001)

摘　　　要:推荐一种多项式辗转相除方法实现RS码译码算法,为便于掌握与寻找出DSP编程规律通过举例分析算法的译码过程。给出用DSP实现译码的硬件原理电路,并介绍如何解决译码软件编程方面的关键问题。

关　键　词:RS码;信道编解码;DSP译码;差错控制中图分类号:TN911.72　　　　文献标识码:A

在移动通信、散射通信、卫星通信、电力线载波通信中,分组数据在传输过程中,由于多径干扰、电离层不稳定、天电干扰、电力线高频谐杂波及电晕等多种因素影响,造成以突发错误为主的传输误码,因此

需要选用较强纠错能力的信道编码措施来纠正错误,减少数据传输的误码率。RS(Rood2Solomon)码最突出的优点是纠正突发错误能力极强,因此正适于用在这些场合。但是,以往由于CPU处理速度的,人们考虑用硬件实现RS码译码,这种电路异常复杂,虽然现在可以用超大规模可编程硬件逻辑电路如FPGA实现,但真正实现仍然相当困难,而且存在难于彻底根除的影响正确译码的逻辑竞争冒险问题,因此了RS码的广泛应用。随着数据处理DSP芯片制造技术的发展和进步,其处理速度越来越快,目前单片DSP指令执行速度已经达到几千MIPS,如TMS320CX速度为8800MIPS,因此RS码译码完全可以用高速DSP实现,不仅可以大大简化电路设计的复杂性,而且软件编程也非常方便。如果需要实现高速传输数据的译码,可以用多片DSP并行处理来实现,而DSP又特别容易设计成多片并行处理结构。

1　RS码编译码算法

RS码作为一类非二进制BCH码,它的码元符号和生成多项式g(x)的根取自同一伽罗华有限域

m

GF(q),一般为GF(2)域。对于纠正t个错误的RS码有:码长n=2-m1个符号、信息段k个符号、监督

22t

)(x+α)…(x+α),其段n-k=2t个符号、最小码距d=2t+1。生成多项式为:g(x)=(x+α

i

中α为GF(2m)域上的本原元,α为生成多项式的根i=1,2,…2t。由g(x)生成的码是(n,n-2t)循

环码。

1.1　RS码编码算法简介

RS码编码方法是用信息码多项式C(x)=ck-1xk-1+ck-2xk-2+…+c0升xn-k位后,再去除生成

多项式g(x),所得余数为监督多项式,将监督多项式置于升xn-k位的信息多项式之后,就形成了RS

收稿日期:2004-01-25

作者简介:戴伏生(1963-),男,哈尔滨工业大学信息工程系,副教授,主要研究方向为通信网与通信电子系统.

第2期戴伏生等:RS码译码算法与译码器的DSP实现方法

　　　15

码,即编码后的码组为:

T(x)=x

n-k

C(x)+xn-kC(x)mod[g(x)]。

与RS码译码器比较,编码器可以方便地用超大规模可编程硬件逻辑电路FPGA实现,因此本文不对编码器进行详细讨论。1.2　RS码译码算法

RS码译码算法步骤一般可描述为:①由接收到的码多项式求伴随式的值si;②根据伴随式的值si

求错误位置多项式σ(x);③求错误多项式σ(x)的根得到差错发生位置;④求出相应的错误值ei确定错误图样E(x);⑤用错误图样去纠正接收码的错误。

经典的译码算法很多,本文不对这些算法的优缺点进行比较和讨论,而是推荐一种辗转相除译码算法,并且为便于理解与掌握及DSP编程,通过算例对算法各步骤进行详细讲解。计算方法与步骤为:

(1)计算伴随式的值si

设接收码多项式为:R(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0。当发生ν(ν≤t)个错误时,计

22t2t

)、算接收码伴随式的值si方法为:s1=R(αs2=R(α)、…、s2t=R(α)。如果得到所有si≡0(i=

1,2,…2t),说明接收码正确不需要纠错,否则为存在错误,需要进行纠错运算。(2)求错误位置多项式σ(x)

该步骤最为关键,为了减少计算量,本文推荐使用辗转相除计算方法。具体过程为:令β0(x)=

s1x2t-1+s2x2t-2+…+s2t-1x+s2t。以x2t除以β0(x)开始进行连续辗转相除,同时判断是否满足停

止条件,逐步得到错误多项式σ(x),即:

2t0x=β0(x)q1(x)+β1(x),σ1(x)=q1(x),Φ1=9[σ1(x)];

0β0(x)=β1(x)q2(x)+β2(x),σ2(x)=q2(x)σ1(x)+σ0(x),σ0(x)=1,Φ2=9[σ2(x)];

……;

0βj-2(x)=βj-1(x)qj(x)+βj(x),σj(x)=qj(x)σj-1(x)+σj-2(x),Φj=9[σj(x)];

0βj-1(x)=βj(x)qj+1(x)+βj+1(x),σj+1(x)=qj+1(x)σj(x)+σj-1(x),Φj+1=9[σj+1(x)]。0

其中:90表示求多项式中不为零的最高项的幂次数。如果j满足90[σj(x)]=Φj≤t,而9[σj+1(x)]=0Φj+1>t条件时,则完成辗转相除运算,并得到错误位置多项式为σ(x)=σj(x),而Φj=9[σj(x)]=

90[q1(x)]+90[q2(x)]+…+90[qj(x)]就是发生差错的个数ν=Φj。

(3)求差错发生位置

2

α、ααn-1代入错误位置多项式σ(x),验证是用DSP实现译码求差错位置的方法是,分别把1、、…、

ii)=0,则α否为根。如果得到σ(α为它的根,说明对应第i位出现差错。

(4)求出相应的错误值ei确定错误图样E(x)

(xi)。(x)是σ(x)的特殊导数,即按照一般意义上求错误值计算公式为:ei=ω(xi)/xσ式中:σ′i′

数学规则求导后,再对多项式每一项前面因求导产生的系数进行模2运算才能得到最终结果,例如求导

339269326

σ(x)=α(x)=αx+αx+αx+α,得到σ′x+α。式中:ω(x)称为辅助差错求值多项式,假如发生ν个差错,根据第2步得到的中间结果,ω(x)按照以下递推方法得到:

ω0(x)=0;ω1(x)=1;ω2(x)=q;ν(x)ων-1(x)ω1(x)+ω0(x);ω3(x)=q2(x)+ω1(x);……ων(x)=q2(x)ων-1(x)+ων-2(x);ω(x)=ων(x)。

只要把第3步求得的错误位置对应根代入ei求解式,就可确定各个错误位置上的错误值,即得到错误图样E(x)=en-1xn-1+en-2xn-2+…+e1x+e0。

(5)纠正接收码的错误

把接收码和错误图样多项式对应相减,即R(x)-E(x)就可实现纠正错误,得到正确码组。

　　　16

1.3　RS码编译码算例

东北电力学院学报第24卷

例:构造能纠正4个错误,码长为15个符号的RS码。

由n=15、t=4,可得到m=4、k=7、d=9,因此RS码组为(15,7)码。定义α为伽罗华有限域GF(24)上的一个本原元,则其生成多项式为:

g(x)=x+αx+αx+αx+αx+αx+αx+αx+α。

8

14

7

2

6

4

5

2

4

13

3

5

2

11

6

编码过程:

663322

设待编码的信息码组多项式为:C(x)=αx+αx+αx+αx+αx+αx+1,则按照编码

公式T(x)=xn-kC(x)+xn-kC(x)mod[g(x)]进行编码,得到发送码组多项式为:

61451341231121098147136125114

T(x)=αx+αx+αx+αx+αx+αx+x+αx+αx+αx+αx+1039287αx+αx+αx+α。

译码过程:

327

αααα假设在传输过程中发生了3个字符错误,设第13、12、11位由原来的α、、分别错成α、、,

即收到存在差错的码组多项式为:

6141321271121098147136125114103

R(x)=αx+αx+αx+αx+αx+αx+x+αx+αx+αx+αx+αx9287+αx+αx+α。

计算出伴随多项式值si:

6141321271121098147136125114

)=αα+αααs1=R(α+αα+αα+αα+α+α+αα+αα+αα+αα+10392877αα+αα+αα+α=α。1012102

同理得到s2=0;s3=α;s4=α;s5=α;s6=α;s7=α;s8=α。求错误位置多项式σ(x):

7710512483921022t

根据伴随多项式值得:β用β0(x)=αx+αx+αx+αx+αx+αx+α。0(x)对x

=x进行辗转相除得到:

q1(x)=αx,σ1(x)=αx,Φ1=1;

q2(x)=αx+α,σ2(x)=αx+αx+1,Φ2=2;

69339269q3(x)=αx+α,σ3(x)=αx+αx+αx+α,Φ3=3;

248453372138q4(x)=αx+αx+α,σ4(x)=αx+αx+αx+αx+αx+α,Φ4=5。

4

6

12

2

14

8

8

8

因为t=4,根据计算得到Φ3=3t,所以得到结果是,发生3个字符错误,且σ(x)

339269

=σ3(x)=αx+αx+αx+α。

求差错位置:

214111213α、αααα分别把1、、…、代入σ(x),得到α、、为错误位置多项式σ(x)的根,说明接收码组多项式的第11、12、13位置上字符出现错误,即差错图样模式为:E(x)=e13x13+e12x12+e11x11。

求差错值和错误图样:

326

σ(x)的导数为:σ(x)=α′x+α。可用递推方法求辅助差错求值多项式ω(x),过程为:

ω(x)=ω3(x)=q2(x)ω2(x)+ω1(x)=q2(x)[q3(x)ω1(x)+ω0(x)]+ω1(x)=

102

q2(x)q3(x)+1=αx+αx。

1023361112

(xi)=(αα得到错误值计算式为:ei=ω(xi)/xσxi+αxi)/(αxi+αxi)。分别代入α、、i′1341022131012411

α得到错误值为:e11=α、e12=α、e13=α。错误图样为:E(x)=αx+αx+αx。

纠正接收码的错误:

3

ααR(x)-E(x)后,发生错误的第13、12、11位还原为正确值α、、。

通过上述介绍可见,辗转相除过程最多只需t+1步就可完成。由于辗转相除过程和求辅助差错求值多项式的递推过程,都与发生差错数量有关,每次运算周期的长短并不固定,如果采用FPGA设计译

第2期戴伏生等:RS码译码算法与译码器的DSP实现方法

　　　17

码电路,电路将会相当复杂,而采用DSP软件方式实现译码,该过程只不过是一套非常有规律的循环程序,并且运算量并不很大。

2　RS码译码DSP实现方法

2.1　RS码译码硬件原理电路

设计的用单片DSP译码电路如图1所示,双DSP并行处理译码电路如

图2所示。DSP采用TI公司生产的TMS320C6203,其指令峰值执行速度为2400MIPS。由于,该芯片支持多种协议下的直接接口,包括T1/E1帧协议、MVIP及ST2BUS兼容设备、IOM2兼容设备、AC97兼容设备、IIS兼容设备

和SPI兼容设备,内部时钟和帧同步信号及信号有效极性可灵活设置,可以接收连续数据流且支持多种数据长度,因此,采用DSP实现译码,硬件电路容易设计。图1实现了伽罗华GF(28)有限域RS(255,243)的截短码—RS(62,50),且译码通过率达到20.48Mbps的译码器。而图2的双DSP并行处理电路,由于每个帧同步脉冲的下降沿对D触发器都发生作用,使触发器的两个输出端状态随之翻转,可控制两个DSP工作在交替接收数据,因此它可以对更高传输速率的数据进行译码,它的译码通过率可达到48Mbps,且两片DSP程序是相同的。2.2　软件编程上一些问题的处理在伽罗华有限域GF(2m)进行运算有他自己的特点。加和减运算是相同的,运算时只需将两个码失的对应位进行模2加即可。元素符号的乘法运算为两个幂相加后再对和的幂次取(2-m1)

i的模就得到的乘积结果。元素符号除运算是用分母的逆(α的逆

α-

i

2

=α

m

-1-i

)与分子相乘。多项式的除法运算方法是,首先,求

被除式和除式的最高项次的差值,按照该差值以字符每一个差值

图2　双DSP并行处理译码电路单元左移该除式,再根据被除式和除式最高项次对应本原元α的

j

幂次,确定出一个能使对应的本原元α幂次相等的幂值(假如为j),把除式乘上α后,并与被除式对应项相加就得到一次除的余式,然后,判断该余式的最高项次是否大于被除式移位前的最高项次,如果大于则按照上述方法继续运算直到余式最高项次小于被除式最高项次为止,该余式就是最终要得到的余

j

式,商是根据每次移位数确定各项次而每次乘上的α就是该项次前的系数。由以上介绍可见,在伽罗华有限域GF(2m)发生的运算只有加法和乘法,这非常适合DSP运算。为了实现乘法快速计算,需要预先建立伽罗华有限域码失与本原元α的幂次对应关系表。

但是,全零码失不能用幂次法表示,如果判断为全零码失,相乘结果可直接得出即为全零。对σ(x)求导的编程实现方法是:首先,直接令多项式中所有为偶数幂次项(包括常数项)的码失为零,然后,将

(x)。该式整体向右移动1个字符单元,于是就得到σ(x)求导结果σ′

3　结束语

与采用FPGA设计RS码译码器比较,用DSP实现RS码译码,其硬件电路简单,通用性也较强,软件编程容易且修改方便,用户可以根据实际要求,只要修改软件就可很方便地设计出自己的RS码译码

器。又由于DSP为程序译码,所以不会出现FPGA译码电路中存在的逻辑竞争现象。用FPGA开发一种码组形式的RS码译码器,一般需用2人年的周期,而用DSP实现只需2人月的周期,(下转第65页)

第2期刘云夫等:三种不同十八胺在停炉保护中的性能研究

　　　65

参　考　文　献

[1]　龚询洁.热力设备的腐蚀与防护[J].中国电力出版社,1998.[2]　水处理药剂缓蚀性能测定方法2旋转挂片法[S].HG/T2159-1991.[3]　宋诗哲.腐蚀电化学研究方法[J].化学工业出版社,1988.

[4]　吴荫顺,等.腐蚀试验方法与防腐蚀检测技术[J].化学工业出版社,1995.[5]　张天胜.缓蚀剂[M].化学工业出版社,2001.

PerformanceStudyofAModifiedOctadecylamineApplying

inProtectionofBoilersOffLoad

LIUYun2fu1,WANGDe2yeng1,KONGFan2li2

(1.NortheastChinaInstituteofElectricPowerEngineeringJilinCity,China132012;2.)

Abstract:Rotarycoupontest,electrochemicalpolarizationcurvesandimpendencemethodwereusedtostudythecorrosioninhibitionandformedalayeroffilmperformanceofthreekindsofdifferentoctadecylamines(ODA).Atthesametime,byusingSEMthefilmperformanceofitsgaseousandliquidphasewasstudiedatthehightemperatureofamodifiedODA.TheresultsshowthattheinhibitionofmodifiedODAisexcellentanditcanformalayerofhydrophobicfilmwithgoodprotectiveeffectonthemetallicsurface,soitcanbeusedintheshut2downthermalpowerequipment.Keywords:Octadecylamine;Thermalpowerequipment;Shut2downanticorrosion

(上接第17页)可见用DSP设计RS码译码器可以大大缩短开发周期。

参　考　文　献

[1]　王进祥,毛志刚.RS码译码器综述[J].微电子学,1997,27(2):115-120.

[2]　欧智明,王承恕.RS码的一种新的译码算法[J].北京:邮电大学学报,1994,17(4):67-72.

[3]　方立,吕昕,邓次平.RS码译码器的VLSI设计[J].兵工学报,2002,23(3):422-425.[4]　姚冬苹,蔡超时.RS码的快速编译码[J].铁道学报,2003,25(3):81-83.[5]　邹世开.实现Reed2Solomon码译码的新电路[J].电子学报,1999,27(10):87-90.

[6]　任丽香,马淑芬,李方慧.TMS320C6000系列DSPs的原理与应用[M].北京:电子工业出版社,2000.[7]　王新梅,肖国镇.纠错码原理与方法[M].西安:西安电子科技大学出版社,1991.

TheDecodingAlgorithmofReed2SolomonCodesand

theDSPImplementingMethodofitsDecoder

DAIFu2sheng1,ZHULiang2,WANGChun2hu3

(1.HarbinInstituteofTechnologyatWeihai,Weihai2209,China;2.SchoolofAstronautics,HarbinInstituteofTechnology,Harbin150001,China)

Abstract:AnalgrithmofusingEuclideandvisionisintroducedtodecodeRScode.Anexample,isgiventoanalyzethattheruleofDSPprogrammcanbelearnedeasily.ThecircuitdiagramofRScodedecodingisaddedinthepaperandhowtosolvethekeyproblemofdecodingsoftwareisalsopresented.Keywords:Reed2solomoncode;Channelencodinganddecoding;DSPdecoding;Errorcontrol