RS码编码算法.docx
RS码编码算法-.RS编码对丁能够订正t个错误的RS(n,k,d)码，具有如下特征：1)码长：n=2n-】符号或m(2n-1)比特2)信息码元数：k=n-2t或mk比特：3)监督码元数:n-k=2l符号或m(n-k)比特；4)最小距离:d=2t+l=n-k+l符号或m(n-k+l)比特:最小距离为d的本原RS码的生成多项式为g(x)=(x-Xx-2Xx-3)(x-d-2)式中的In是一个随意整数。令信息元多项式为：m(x)=m0+m+TTi2X2+mk-xkl二.RS编码器的类型1.基于乘法形式的RS编码器公式：c(x)=m(x)g(x)结构图如下：乘法编码法由上面结构的乘法编码器输出的码字是非系统码。2.基于除法形式的RS编码卷(I)依据生成多项式g()构造的除法编码器。令g()g(x)剩余多项式r(x)至少比g(x)低一次。r(x)=r2t,1x2*l+r2t.2x2,-2+r2x2+r1x+则编程的码多项式为C(X)=n-fca(x)+r(x)=CnTXnT+Cn_2Xn2+C2X2+CX+C0除江电路构成的RSa灯器(2)依据校物码多项式h(x)构造的除法编码器设校瞪多项式为：h(x)=hkxk+hk.xkl+hx+h0系统码的多项式为：C(X)=Cn-X-I+Cn.2X>2+C-kXn-k+Cn-k-nkT+C+Co它的前k位系数：CnT,J-2，Cr-k是己知的信息位，而后n-k位系数：C吁k-,Cn-k-2，Cl3。是需求的校验位。码多项式必是生成多项式g(X)的背式，所以C(x)=q(x)g(x)3。C(X)n-1.5°g(x)=n-k.5°q(x)k-1而h(x)C(x)=q(x)g(x)h(x)=q(xXxn-1)=q(x)xn-q(x)由于6。C(X)Wn-l,5og(x)=n-k,dog(x)=n-k,d<>q(x)k-1所以q(x)1的最低位次数至少为n次，而在h(x)C(x)的乘积中nT,n-2,.,k的次数为0。XnT的系数:cn-l-OhO+cn-l-lhl+,+cn-l-khkxn-2的系数:cn-2-()h÷cn-2-h+,',+cn-2-khfc而ZCnTThi=Oi=0,1.2,n-kj=o由Fh(X)为首一多项式，hk=1.故上式可写为k-lcn-k-i=-cll-i-jhj1=1,2,n-kj=o上式绽开为：C1.k-I=-(Cn-IhO+-%+品-必-。J-k-2=一(Cn-2%+7.3%+'*+Cn.k.lhk.l)cn-k-(n-k)=cO=一(CkhO+Ck.h+,+Chk.)由上式看出码字C的第一个码元C-k-l可由k个信息元，,C11.k与h(X)的系数相乘得到，而由C,.2，Cn_3，Cn-k，C.k-l可得到其次个校验元Cn_k_2,再由J_3，Cn-k信息元和笫一、其次校验元Cr-k-l,Cn-k-2可得到第三校验元Ct1.k-30按这样的线性关系递推,始终可求得全部的n-k个校验兀Cn-k-l，Cn-k-2，C，Co°详细实现如下图：(3)RS的时域编码实际例子RS码是非二进制码，它是在GF(q)上的，这里qw2.这里我们选用GF(16)域来进行，域中16个元素可用4bits符号表示。例构造一个能订正3个错误符号，码长为16,E的RS码.求生成多项式和编码电路.解：当1=3时，最小码距Dmin=7,信息元长度k=9。该码为(15,9)RS码，其生成多项式为：g(x)=(x+a)(x+a2)(x+a3)(x+a4)(x+a5)(x+a6=x6+a,0x5+a,4x4+a4x3+a6x2+a9x+a6由分圆多项式多项式：g(x)=(x2+x+l)(x4+x+l)aeGF(16)是本原域元素，它是多项式x"+x+1的根，则a4+a+1=O或a4=a+I以x"+x+l为模的GF(24)的元素如卜表：i10«1-IOOOlas-.12.1«1十IOlOlaOOlOa9=a3+aIOlO7a-OlOOa,0三a2+a÷lOllla3100O11彳2a=a，+a+aIllOa4=a+1OOlla=a+a+a+1HlIS，a=a÷aOllOa13=a3+a2+IIlOl'_，/2十dIlOOaN_31ad十I100laz=+a+IIOlla5.1OOOlGF(2')中每个元素都可表示成它的自然基地1h82位3(在域GF(2)上)的线性组合，如下形式：a3a1+a2a2+aa+a0因此在GF(2上的2。进制RS码，它的编码电路可用k或n-k级24进制寄存器实现。本例是用n-k=6级乘法器电路实现，如下图。图中的移位积存器必需是由能枳存16进制的元件组成，这可用4级触发器组成的移存器完成。a°.a4.aa6,a9常乘器可用模2加法器构成。a"(aa"+a2a"+aa+a0)=a3a'+a2a"+aa"+a°a”=a3(a'+a2+l)+a2(as+a2+a+!)+a1(a'+a2+a)+a0(a2+a+1)=(a3+a2+a)a+(a3+a2+a+a0)a-+(a2+a+a0)a+(a2+a0)a,4(a3a3+a2a2+aa+a0)=a3al7+a2a,6+aal5+a,4=aoaA+a3a2+a2a+(al+a0)a(flj3'+aa+33)=aa+a2a'+a+a°a'=a3(a3÷a+1)+a2(a3+a2)÷a1(a2+a)+a0(a÷l)=(3j+32)a+(112+a)a+(a?+a+a0)a+(a?+a。)a6(a3a3+a2a2+a1a+a)=a3a9+a2a8+a1a7+a0a6=a3(a,+a)+a2(a?+l)+a(a'+a+l)+ao(a'+a?)=(a3+a1+a0)a3+(a2+a0)a2+(a3+a1+a0)a+(a2+a1)Qz1，、12I1K)9a(a3a+a2a-+a1a+a0)=a3a+a2a+a1a+a0a=a3(a1+a2+a+l)+a2(a3+a2+a)+a(a2+a+l)+a0(a1+a)=(a3+a2+a)a3+(a3+a2+a)a2+(a3+a2+a+a0)a+(a3÷a)GF(2b中乘a°的转换电路如下表示：al0(a3a'+a2a2+ala+a0)=(a3+a2+a)a3+(a3÷a2+a+a0)a2+(a2+a+a0)a+(a2+a0)式中：a3'=a3+a2+a2'=a3+a2+a+3a1,=a2÷a÷a0a0t=a2+a0GF()中乘a0路GF(2')中乘a"的转换电路如下表示：aq'=a?+a?H2，=2+aGF(24)中乘4路GF(2')中乘a't的转换电路如下表示:a3,=a0a2'=Sj6214)中痴“电路GF(2l*)中乘a''的转换电路如卜表示：a3,=a3+a+a0a2,=a2+a0a=a3+a+a0Hq=2Ia3=a3+a2+a0a1,=a3+a2+a1+a0a0=a3+a1GF(24)中乘a$电路GF(2")中乘a9的转换电路如下表示：112，=+a2+a31GJGF（24）中乘a9电路15.9.7RS编码器详细实现电路如下图所示:壬I&东投.l工作过程如下：（1）门打开，开关拨到符号输入端，全部移存器消0。然后将6个16进制信息符号，边送入移存器，边送入信道。留意每节拍移动一个16进制符号。（2）6个16进制符号送入移存器后，完成除法运算，移存器中的就是余Ta此时，门关闭，开关接到下面。再经过6个节拍的移动，得到全部6个校验元，并且跟随信息元送入信道，完成一个码字的编码过程。（3）清洗枳存器，打开门，起先其次组信息元的编码。
