RS码编码算法

1、RS码编码算法RSRS 编码对于能包纠正 t t 个错误的 RS(n,k,dRS(n,k,d) )码，具有如下特征：1)码长：n=2m一1符号或m(2m一1)比特2)信息码元数：k=n一2t或mk比特；3)监督码元数：nk=2t符号或m(n-k)比特；4)最小距离：d=2t+1=nk+1符号或m(n-k+1)比特;最小距离为 d d 的本原 RSRS 码的生成多项式为23d一2g(x)二(x-二)(x一二)(x二)(x一二)式中的 m m 是一个任意整数。令信息元多项式为：.2k-1m(x);m0m1m2x-myx二.RSRS 编码器的类型1 1 . .基于乘法形式的 RSRS 编码器公式:c

2、(x)=m(x)g(x)结构图如下：由上面结构的乘法编码器输出的码字是非系统码。2 2 . .基于除法形式的 RSRS 编码器(1)根据生成多项式g(x)构造的除法编码器。r(x)=b(x)g(x)剩余多项式r(x)至少比g(x)低一次。/、2t-1.2t-2.2.SoSo徜出乘法编码器乘法编码器nkxa(x)g(x)r(x)=r2t_1xr2t_2xr2xr1xr0则编程的码多项式为nk.c(x)=xa(x)r(x)n_1n_22:cn1xcn2x-，c2xc1xc0具体实现如下图:除工电路构成的心编码器(2)根据校验码多项式h(x)构造的除法编码器设校验多项式为：.k.k_1h(x)=hk

3、xhk_1x-，h1xh0系统码的多项式为：n-1n-2n-kn-k-1C(x)=cnqx却_2*备_卜*g_k.G“xc0它的前k位系数：cn_1,cnj,，cn_k是已知的信息位，而后n-k位系数：cn_k_1,cn_2，c1,c0是需求的校验位。码多项式必是生成多项式g(x)的背式，所以C(x)=q(x)g(x)C(x)-n-1,：:g(x)=n-k,：:q(x)-k-1而h(x)C(x)=q(x)g(x)h(x)=q(x)(xn-1)=q(x)xn-q(x)由于C(x)n1,fg(x)=n-k,；:g(x)=n-k,；:q(x)k-1所以q(x)xn的最低位次数至少为n次，而在h(x)

4、C(x)的乘积中xn-1,xn2,，xk的次数为 0 0。xn1的系数：cn_1_0h0cn_1_1h1cn_1_khkxn/的系数：cn-2-0h0cn_2_1h1,，cn_2khk而k、cn_jhj=0i=0,1,2,n-kj=0由于h(x)为首一多项式，hk=1,故上式可写为k_1c.=_chi=12n-knkinijj,j=0上式展开为：cn_k_1=-(cn_1h0，cn二h1cn-khk-1)cn_k_2=(cn_2h0，cn_3h1-cn_k-1hk-1)acn_k_(n_k)=c=-(ckh。,ck/h15hk_1)由上式看出码字C的第一个码元cnU1可由k个信息元cn1,cn

5、2，cnk与k1n12kh(x)的系数相乘得到,而由cn_2,cn,，cnkcnk可得到第二个校验元cn_k_2,再由cn_3,，备信息元和第一、第二校验元.k_1,.k_2可得到第三校验元cn二。按这样的线性关系递推，一直可求得所有的n-k个校验兀cnk3,cnk2,c1,c00具体实现如下图： 输出码字输出码字tnTk循环码循环码k级编码器级编码器(3)(3)RSRS 的时域编码实际例子RSRS 码是非二进制码，它是在GF(q)上的，这里q#2。这里我们选用GF(16)域来进行，域中 1616 个元素可用 4bits4bits 符号表示。例构造一个能纠正 3 3 个错误符号，码长为 15,

6、15,m=4m=4 的 RSRS 码。求生成多项式和编码电路。解：当t=3=3 时，最小码距Dmin=7,信息元长度k=9。该码为(15,9)(15,9)RSRS码，其生成多项式为：2、，3、，4、，5、，6a)(xa)(xa)(xa)(xa由分圆多项式多项式：,、，24八g(x)=(xx1)(xx1)awGF(16)是本原域元素，它是多项式x4+x+1的根，则4,八aa1=0a4=a1以x4+x+1为模的GF(24)的元素如下表:a0-1a0001000182a=a+101010101a0010001093a=a+a101010102a01000100102a=a+a+1011101113a

7、10001000113,2a=a+a+a11101110a4=a+100110011123,2.a=a+a+a+11111111152.a=a+a01100110133,2,da=a+a+11101110163.2a=a+a11001100143.a=a+11001100173a=a+a+11011101115.a=100010001GF(24)中每个元素都可表示成它的自然基地1,a,a2,a3(在域GF(2)上)的线性组合，如下形式:g(x)=(xa)(x610=xax5144ax43629axaxaxa32a3aa2aa1aa0因此在GF(24)上的24进制 RSRS 马，它的编码电路可用

8、k或n-k级24进制寄存器实现。本例是用n-k=6级乘法器电路实现，如下图。图中的移位积存器必须是由能积存 1616 进制的元件组成，这可用 4 4 级触发器组成的移存器完成。a10,a14,a4,a6,a9常乘器可用模 2 2 加法器构成。在域GF(24)上的系数a10,a14,a4,a6,a9可用自然基地表示为如下形式：103213121110a(a3aa2aa1aa0)=a3aa2aa1aa0a,32,、,32，32,2=a3(aa1)a2(aaa1)a1(aaa)a0(aa1),、3,、2=(a3a2a1)a(a3a2-a1a0)a-(a2a1-a0)a(a2-a0)32,、=aaa3

9、aa2a(aa。)4/320.7654a(a3aa2aa1aa0a);a3aa2aa1aa0a3322二a3(aa1)a2(aa)a1(aa)a0(a1),、3,、2,、，、二(a3a2)a(a2a)a(a?aa0)a(a?a)6329876a(a3aa2aa1aa0)=a3aa2aa1aa0a32332二a3(a-a)a2(a1),a1(aa1)a0(a-a),、3,、2,、，、14/3a(a3a2、17a2aaaa0)=a3aa2a1514a1aaU5,9RS 编码电路信息符号输出码;区a1a0)a(a2a)a,。aa0)a(a2a1)9,32、121110a(a3aa2aa1aa0)=a

10、3aa2aa1a,32,、，32、,2,、，3、=a3(aaa1)a2(aaa)a1(aa1)a0(aa)aiao)a包a1)=(a3、3,、2,a2ao)a(a3a2ai)a,(a3,a21，GF(24)中乘a10的转换电路如下表示:a2=a3a2,a1-a0a1=a2a1-a0ao=a2a。GF(214)中乘a14电路91032a(a3aa2aa1aa0),、3,、2,、，、二(a3a2a1)a0a2.aa0)a(a2aa0)a凡a0)a3=a3a2-a1GF(214)中乘a10电路GF(24)中乘a14的转换电路如下表示:a2=a2a1a3=a3a2a0=a1a1=a3a1.a0-a0-a0aGF(24)中乘a4的转换电路如下表示:GF(24)中乘a6的转换电路如下表示:al=a3a1a0GF(214)中乘a6电路GF(24)中乘a9的转换电路如下表小：a3=a3a2a0a2=a3a2a1a1=a3a2a1a0a0=a3a1a3=a0a1=a2a2=a3a?=a3aia。a2=a2a0a0-a3a0GF(214)中乘a14电路a0=a2ai15,9,7RSRS 编码器具体实现电路如下图所示:表示撤JI1工作过程如下：(1)(1)门打开，开关拨到符号输入端，所有移存器清 0000 然后将 6 6 个 1616 进制信息符号，一边送入移存器，一边送入信道。注意每一节拍移动一