RS码纠突发错误译码算法研究与实现

:2004-02-23:(1976-),,,,RS杨忠立1,刘玉君1,王云鹤2,唐冬明1(1,,450002;2,,100038):文章在简述常规RS译码过程基础上,研究了RS用于纠突发错误译码的数学推导模型,以RS(15,9)码为例,详细分析了译码过程,最后讨论了关键方程公共根的选择对误纠概率的影响,指出了纠突发错误译码的应用前景:RS码;突发错误;误纠概率:TN911:A:1671-0673(2004)04-0077-03StudyandImplementationofBurstErrorCorrectingAlgorithmforReedSolomonCodesYANGZhongli,LIUYujun,WANGYunhe,TANGDongming(InstituteofInformationEngineering,InformationEngineeringUniversity,Zhengzhou450002,China)Abstract:ThispaperfirstdescribesdecodingofconventionalReedSolomoncodesandstudiesthemathematicalderivationmodeltocorrectbursterror.ThenaRS(15,9)codeisusedasanexampletoanalysethedecodingprocedureconcretely.Thearticlediscussestheinfluenceonprobabilityofmiscorrectbychoiceofthecommonrootofkeyequations.Lastitpointsouttheapplicationperspectiveofbursterrorcorrecting.Keywords:reedsolomoncode;bursterrors;probabilityofmiscorrect1-(RS),RS:RS(n,k)(n-k)/2(n-k)/2,,RS(n,k)(n-k),(n-k)/2,([2])2RS,E(x)=ei1xl1+ei2xl2++eivxlv(1),v,0vt;eirr;irrR(x)=C(x)+E(x)(2)C(x)=cn-1xn-1+cn-2xn-2++c1x+c0(n,k)RSSj=R(j)=C(j)+E(j)=E(j)(j=1,2,,2t)(3),Yr=eir,r=1,2,,v第5卷第4期信息工程大学学报Vol.5No.42004年12月JournalofInformationEngineeringUniversityDec.2004;Xr=ir,r=1,2,,v,E(j)=ei1(j)i1+ei2(j)i2++eiv(j)iv=ei1(i1)j+ei2(i2)j++eiv(iv)j=Y1Xj1+Y2Xj2++YvXjv(4)(4)(3),2tS1=Y1X1+Y2X2++YvXvS2=Y1X21+Y2X22++YvX2v(0vt)(5)S2t=Y1X2t1+Y2X2t2++YvX2tvBerlekamp,(5),t3RS,E(x)=ei1xi1+ei2xi1+1++eivxi1+v-1(6)eirr;i1;v,Sj=R(j)=C(j)+E(j)=E(j)=ei1(j)i1+ei2(j)i1+1++eiv(j)i1+v-1=ei1(i1)j+ei2(i1+1)j++eiv(i1+v-1)j,(j=1,2,,2t)(7),2tS1=Y1X1+Y2X1++(v-1)Y2tX1S2=Y1X21+2Y2X21++2(v-1)Y2tX21S2t=Y1X2t1+2tY2X2t1++2t(v-1)Y2tX2tl(8)S1/X1S2/X21S2t/X2t1=0(v-1)022(v-1)02t2t(v-1)Y1Y2Yv(9)v,[v],[]=[v]-1=a11a12a1va21a22a2vav1av2avv(10)(9),:Y1Y2Yv=a11a12a1va21a22a2vav1av2avvS1/X1S2/X21Sv/Xv1(11)(2t-v)S(v+1)/X1v+1S(v+2)/X1v+2S2t/X2t1=0v+1(v+1)(v-1)0v+2(v+2)(v-1)02t2t(v-1)Y1Y2Yv=b(v+1)1b(v+1)2b(v+1)vb(v+2)1b(v+2)2b(v+2)vb2t1b2t2b2tv=S1/X1S2/X21Sv/Xv1(12)S(v+1)=b(v+1)1S1Xv1+b(v+1)2S2X1v-1++b(v+1)vSvX1S(v+2)=b(v+2)1S1Xv+11+b(v+2)2S2X1v++b(v+2)vSvX21S2t=b2t1S1X2t-11+b2t2S2X2t-21++b2tvSvX2t-v1(13),X1,,(11),()(),4GF(24),:x4+x3+x0,RS(15,9):vmax=2t-2=4,:t=(n-k)/2=3()(1),()!,:[a]=[4]-1=0230246036904812-1=782004a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44=1101351415911412727614(14)∀(12),:b51b52b53b54b61b62b63b64=05100061231101351415911412727614=692612857(15)(2):3x14+2x13+1x12+0x11=0!:S1=R(1)=C(1)+E(1)=E(1)=8S2=R(2)=C(2)+E(2)=E(2)=4S3=R(3)=C(3)+E(3)=E(3)=12S4=R(4)=C(4)+E(4)=E(4)=14S5=R(5)=C(5)+E(5)=E(5)=4S6=R(6)=C(6)+E(6)=E(6)=0(16)∀(13),(15)(16):14x14+13x13+14x12+5x11+4=0(17)5x14+12x13+2x12+6x11+0=0(18)#:(17)4911;(18)11,11,11∃(11),Y1Y2Y3Y4=a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44S1/X1S1/X21S3/X31S4/X41=1101351415911412727614121290=3210(19)3x14+2x13+1x12+0x11=0,,5X1X1,X12t-vmax,vmaxt,;vmax,,,vmaxX1,vmax,,;,,,,,;,[2],Owsley,,vmax,,,6,,,,,,:[1][M]:,20019[2]POwsleyBursterrorcorrectionextensionsforReedSolomoncodes[D]PhDdissertEEDept,UnivofIdaho,July1988[3]JChen,POwsleyABurstErrorCorrectingAlgorithmforReedSolomonCodes[J]IEEETransInformTheory1992,38:1807-1812[4]LiuguoYin,JianhuaLu,KBenLetaief,etalBursterrorcorrectingalgorithmforReedSolomoncodes[J]ElectronicsLetters,2001,37:695-696794:RS