RS码编码算法.doc

RS码编码算法一.RS编码对于能够纠正t个错误的RS(n,k,d)码，具有如下特征:1) 码长：n二2m—1符号或m(2m—1)比特2) 信息码元数：k=n—2t或mk比特；3) 监督码元数：n-k=2t符号或m(n-k)比特；4)最小距离：d—2t+1=n—k+1符号或m(n-k+1)比特;最小距离为d的本原RS码的生成多项式为g(x)=(x—a)(x—a2)(x—a3).…(x—ad—2)式中的m是一个任意整数令信息元多项式为：m(x)=m0+m1+m2x2+…+mk—1xk—1二.RS编码器的类型1. 基于乘法形式的RS编码器公式：c(x)=m(x)g(x)结构图如下:输入输tEe(x)r(x)=r2t—1x2t—1+r2t—2x2t—2+…+r2x2+r1x+r0r(x)=r2t—1x2t—1+r2t—2x2t—2+…+r2x2+r1x+r0乘法编码器由上面结构的乘法编码器输出的码字是非系统码2. 基于除法形式的RS编码器(1) 根据生成多项式g(x)构造的除法编码器r(x)=r2t—1x2t—1+r2t—2x2t—2+…+r2x2+r1x+r0r(x)=r2t—1x2t—1+r2t—2x2t—2+…+r2x2+r1x+r0xn-ka(x)g(x)=b(x),r(x)g(x)r(x)=r2t—1x2t—1+r2t—2x2t—2+…+r2x2+r1x+r0剩余多项式r(x)至少比g(x)低一次。

r(x)=r2t—1x2t—1+r2t—2x2t—2+…+r2x2+r1x+r0Cn一1一0h0+Cn亠M+…+Cn亠Jk则编程的码多项式为c(x)=xn_ka(x)€r(x)=Cn，1Xn，1€Cn，2Xn，2€…€C2X2€宁€C0具体实现如下图:输也们除法电路构成的RS编码器(2) 根据校验码多项式h(x)构造的除法编码器设校验多项式为：h(x)=hxk+hxk-1€€hx+h'丿kk，110系统码的多项式为：C(x)=Cxn，1+Cxn_2€€Cxn_k+Cxn_k，1€€Cx+Cn，1n一2n一kn一k，110它的前k位系数：Cn,],cn，2,…,cn，k是已知的信息位，而后n—k位系数：Cn,k_],Cn,k,2,…,C],C0是需求的校验位码多项式必是生成多项式g(x)的背式，所以C(x)=q(x)g(x)„°C(x)

xn-1的系数:Cn一1一0h0+Cn亠M+…+Cn亠Jkxn-2的系数:Cn-2-0h0+Cn-2-1h1+…+Cn-2-khkCn-i-jhj，0Cn-i-jhji，1,2,€,n一ki，0,1,2,…,n-k由于h(x)为首一多项式，hk，1，故上式可写为Cn一1一0h0+Cn亠M+…+Cn亠JkCn一1一0h0+Cn亠M+…+Cn亠Jk上式展开为:c,“=-(c+c++c,h“)n-k-1n-10n-21n-kk-17c，-(ch+ch++ch)n-k-2'n-20n-31n-k-1k-17cn-k-(n-k)，c0，-(ckh0+ck-1h1+…+c1hk-1)由上式看出码字C的第一个码元cn一k-1可由k个信息元cn一］,cn一2,…,cn一k与h(x)的系数相乘得到，而由cn一2，cn一3,…,cn一k，cn一k-1可得到第二个校验元cn-k-2，再由cn-3,…^n-k信息元和第一、第二校验元J-―入-一2可得到第三校验元cn一k一3按这样的线性关系递推，一直可求得所有的n-k个校验元cn-k-1,cn-k-2‘…,C1,c0•输出码字〔入K術坏码k纵编码器(3) RS的时域编码实际例子Cn一1一0h0+Cn亠M+…+Cn亠JkRS码是非二进制码，它是在GF(q)上的，这里q€2。

这里我们选用GF(16)域来进行，域中16个元素可用4bits符号表示例构造一个能纠正3个错误符号，码长为15,m=4的RS码求生成多项式和编码电路解：当t=3时，最小码距Dmin=7，信息兀长度k=9该码为(15，9)RS码，其生成多项式为：g(x)=(x,a)(x,a2)(x,a3)(x,a4)(x,a5)(x,a6=x6,a10x5,a14x4,a4x3,a6x2,a9x,a6由分圆多项式多项式：g(x)=(x2+x+1)(x4+x+1)aeGF(16)是本原域元素，它是多项式x4+x+1的根，贝ya4+a+1=0或a4=a+1以X4+x+1为模的GF(24)的元素如下表:a0=10001a8=a2+10101a0010a9=a3+a1010a20100a10=a2+a+10111a31000a11=a3+a2+a1110a4=a+10011a12=a3+a2+a+11111a5=a2+a0110a13=a3+a2+11101a6=a3+a21100a14=a3+11001a7=a3+a+11011a15=10001GF(24)中每个元素都可表示成它的自然基地1,a,a2,a3(在域GF⑵上)的线性组合，如下形式：a3a3€a2a2€aia€a0因此在GF(24)上的24进制rs码，它的编码电路可用k或n—k级24进制寄存器实现。

本例是用n-k，6级乘法器电路实现，如下图图中的移位积存器必14输出码.a10须是由能积存16进制的元件组成，这可用4级触发器组成的移存器完成ai°,ai4,a4,a6,a9常乘器可用模2加法器构成a9(aa3€aa2€aa€a)=aa12€aa11€aa10€aa9'3210J3210=83(33€a2€a€1)€a2(a3€a2€a)€a】(a2€a€1)€a°(a3€a)=(a3€a2€a0)a3€(a3€a2€a/a2€(a3€a2€a1€a0)a€(a3€a/GF(24)中乘a10的转换电路如下表示:a10(aa3€aa2€aa€a)'3210丿=(a€a€a)a3€(a€a€a€a)a2€(a€a€a)a€(a€a)式中：a3=a3€a2€a1a2=a3€a€a€a210a'=a€a€aa'=a€a1210020JLJLv32V'3210丿'210丿'20丿jL」LJL」1.jLiLiiLJlJ11113□a-GF(214)中乘al电路GF(24)中乘a14的转换电路如下表示:a:=a€aa=a€a332221a'=二a€a€aa'=a€a1310010GF(214)中乘a14电路ai_a3+a2+ai+a0a0_a3+aiGF(24)中乘a4的转换电路如下表示:0a0_a3+aa2-a3_a2GF(214)中乘ai4电路GF(24)中乘a6的转换电路如下表示:a_a+a+aa_a+a331o22oa'_a+a+aa'_a+a131oo21GF(214)中乘a6电路GF(24)中乘a9的转换电路如下表示:a3_a3+a2+a0a2_a3+a2+ai~~T-Ja-KIGF（214）中乘a9电路[15,9,7]rs编码器具体实现电路如下图所示:工作过程如下：（1）门打开，开关拨到符号输入端，所有移存器清0。

然后将6个16进制信息符号，一边送入移存器，一边送入信道注意每一节拍移动一个16进制符号＜（2）6个16进制符号送入移存器后，完成除法运算，移存器中的就是余式此时，门关闭，开关拨到下面再经过6个节拍的移动，得到所有6个校验元,并且跟随信息元送入信道，完成一个码字的编码过程3）清洗积存器，打开门，开始第二组信息元的编码ai_a3+a2+ai+a0a0_a3+aia4在域GF(24)上的系数ai°,ai4,a4,a6,a9可用自然基地表示为如下形式:a10(aa*3+aa2+aa+a)，aa13+aa12+aa11+aa10'3210J3210，a(a3+a2+1)+a(a3+a2+a+1)+a(a3+a2+a)+a(a2+a+1)3210，(a+a+a)a3+(a+a+a+a)a2+(a+a+a)a+(a+a)v32r'3210丿'210丿'20丿a14(aa3+aa2+aa+a)，aa17+aa16+aa15+a14v3210丿321，aa3+aa2+aa+(a+a)032'10丿a4(aa3+aa2+aa+aa0)，aa7+aa6+aa5+aa4v3210丿3210，a?(a3+a+1)+a_(a3+a2)+a〔(a2+a)+a"(a+1)，(a+a)a3+(a+a)a2+(a+a+a)a+(a+a)v32丿v21丿v310丿v30丿a6(aa3+aa2+aa+a)，aa9+aa8+aa7+aa6v3210J3210，83(33+a)+a2(a2+1)+a】(a3+a+1)+a°(a3+a2)，(a3+a1+a0)a3+(a2+a°)a2+(a3+a1+a°)a+(a2+a1)ai_a3+a2+ai+a0a0_a3+ai。