1999年9月北京邮电大学学报Sep.1999第22卷第3期JournalofBeijingUniversityofPostsandTelecommunicationsVol.22No.3RS码的一种简化译码方法3田宝玉吴伟陵王大庆宋继昌(北京邮电大学信息工程系,北京100876;第一作者52岁,男,副教授)摘要提出了以解有限域二次方程为基础的简化译码方法.与常规RS译码器比较,该方法提高了译码速度并简化了译码器的结构.关键词分组码;RS码;有限域;伴随式分类号TN929.5RS(reed2solomon)码是一种纠突发错误的分组码.由于其较强的纠错能力,故在移动通信和其它衰落信道中,常把RS码用做级联码的外码[1].但是,RS码译码方法比较复杂[2],译码器的实现需要较高的运算速度和较大的存储量.本文针对能纠两个符号错误的RS码,提出了一种简化译码方法.其要点是:将求解错误位置和错误数值的方程组化成一个有限域二次方程,利用有限域二次方程求根公式,代替通常所采用的Chien氏搜索.与常规的RS译码器相比,该方法提高了译码速度并提供了固定的译码延迟,从而简化了译码器结构.1译码方法简述本文所提出的译码方法包括:由伴随式方程导出有限域的二次方程、求二次方程的根、有限域元素的正交展开与解的矢量表示、错误数值的计算和错误的纠正等.1.1有限域二次方程的导出m+k设符号长度为mbit可纠两个符号错误的RS码,生成多项式的根分别为A0,k=0,1,m2,3,其中A为GF(2)中的本原元,m0为正整数;所求伴随式分别s0,s1,s2,s3,其中si∈GF(2m),i=0,1,2,3.假定某码字在传输时最多有两个符号错误,错误位置分别为i,j,则m仅此两位置所对应的错误值ei,ej(ei,ej∈GF(2))不为0,因此可得到如下的方程组:m0im0jei(A)+ej(A)=s0m0+1im0+1jei(A)+ej(A)=s1m0+2im0+2jei(A)+ej(A)=s2m0+3im0+3jei(A)+ej(A)=s3ij设A=x1,A=x2,通过推导可知,x1,x2满足下面的二次方程:收稿日期:19982062253国家“863计划”(863231729603204)和国家自然科学基金(69896243)重大资助项目第3期田宝玉等:RS码的一种简化译码方法97222(s1+s0s2)x+(s1s2+s0s3)x+s2+s1s3=0(1)22求出式(1)的两个根便可求得i,j.令a=s1+s0s2,b=s1s2+s0s3,c=s2+s1s3,式(1)变成ax2+bx+c=0(2)1.2有限域二次方程的解如果无符号错误,则si=0,i=0,1,2,3,从而有a=b=c=0;如果有一个符号错误;si≠0,而a=b=c=0;如果有两个符号错误,则a,b,c均不为0;其它情况则属于两个以上符号错误的情况.当两个符号错误时,令x=byöa,代入式(2),得y2+y+d=0(3)其中,d=acöb2.下面采用MacWilliams的方法[3]解方程(3).将d按正交基展开,有22m-1d=t0A+t1A+⋯+tm-1A(4)可以证明,当Tm(d)=t0+t1+⋯+tm-1=0时,式(3)有两个根,且km-1′′⋯′⋯′y0=D,y1=D+t1,,yk=D+6ti,,ym-1=D+6tii=1i=1′′2′2m-1y=y0A+y1A+⋯+ym-1A(5)这里,D分别取0或1,从而得到方程(3)的两个根y1,y2.1.3有限域元素的正交展开与解的矢量表示m设d在GF(2)中的矢量表示为d=(d0,d1,⋯,dm-1),由式(4)可知,有AA2(t0,t1,⋯,tm-1)=(d0,d1,⋯,dm-1)(6)m-1A2由于译码器所需结果是有限域元素的矢量表示,因此需将式(5)进行适当变换,设y=(y0,y1,⋯,ym-1),则式(5)可写成A2′′′A(y0,y1,⋯,ym-1)=(y0,y1,⋯,ym-1)=m-1A2-1A11⋯1AA201⋯1A2(d0,d1,⋯,dm-1)+(D′,0,⋯,0)(7)m-1m-1A200⋯1A2m-1此处,利用了A+A2+⋯+A2=1的关系,D′=0或1.而且-11A11A21t0+t1+⋯+tm-1=(t0,t1,⋯,tm-1)=(d0,d1,⋯,dm-1)(8)m-11A21因此,可利用式(8)来判断式(3)是否有解.08北京邮电大学学报第22卷1.4错误数值计算