RS码编码算法.docx

1、RS码编码算法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 T二n - k 1符号或m(n - k T)比特;最小距离为d的本原RS码的生成多项式为g(x) = (x - ： )(x - ： 2)(x - ： 3) (x - ： d -2)式中的m是一个任意整数。令信息元多项式为：2k 1m(x) =m0 m1 m2x 亠 亠 mk-1x二.RS编码器的类型1 .基于乘法形

2、式的RS编码器公式：c(x)二 m(x)g(x)结构图如下：输入-噸浪编吗器由上面结构的乘法编码器输出的码字是非系统码2 .基于除法形式的RS编码器(1)根据生成多项式g(x)构造的除法编码器。xnka(x)g(x)b(x)器剩余多项式r(x)至少比g(x)低一次r(x) = r2t_1x21 r2t-2x2t_2 r2x2 jx r0则编程的码多项式为c(x)二 xn-ka(x) r(x)除法电路构成的RS编码辭 (2)根据校验码多项式h(x)构造的除法编码器设校验多项式为：h(x) = hkxk hkx11 亠 亠 h1x h0系统码的多项式为:C(X)二C n_iXn5 _2乂2 5 k

3、x 5 _必1 Cq它的前k位系数：Cn _1,Cn_2，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,r 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) - n - 1, g(x)二 n - k, g(x)二 n - k, q(x) - k - 1所以q(x)xn的最低位次数至少为n次，而在h(x)C(x)的乘积中xn

4、T,x门一2,xk的次数为0。X1的系数：xn _2的系数：Cn _2血 Cn_2_lhi Cn_2_khk而k工 Cn jhj =0 i = 0,1,2,，n - kro由于h(x)为首一多项式，hk =1，故上式可写为k -1Cn_k_i 八 Cnijhj i = 1,2, ,n-kj=0上式展开为：Cn -k = -(Cn-1ho Cn_2hi Cn-khk-1)Cn _k_2 = (Cn_2ho Cn -3h1 Cn-k-1hk-1)-Cn -k-(n-k) - Co 八(Ckho “柑 qhk_1)由上式看出码字C的第一个码元Cn kJ可由k个信息元Cn _1,C n_2,，c n_

5、k与h(x)的系数相乘得到，而由Cn _2,C n,，C n_k,C n _k J可得到第二个校验元Cn _k _2，再由Cn _3, ,C n _k信息元和第一、第二校验元 5 _k_1,C n_k2可得到第三校验元Cn _k_3。按这样的线性关系递推，一直可求得所有的 n - k个校验 “ B兀 Cn -k -1，Cn -k -2， ，C1, Co 0瓦循坏码k级編码器(3) RS的时域编码实际例子RS码是非二进制码，它是在GF(q)上的，这里q= 2。这里我们选用GF(16)域来进行，域中16个元素可用4bits符号表示。例 构造一个能纠正3个错误符号，码长为15, m=4的RS码。求生

6、成多项式和 编码电路。解：当t = 3时，最小码距D min = 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)a GF(16)是本原域元素，它是多项式x4 x 1的根，则a4 a 1 = 0或 a4 = a 1以x4 x 1为模的GF(24)的元素如下表：a0 =100018 2斗a = a +10101a00109 3a = a + a10102

7、 a0100a = a + a + 101113 a100011 3 丄 2a = a + a + a1110a4 = a + 10011a =a + a +a + 11111a5 = a2 + a0110a = a + a + 111016 3+2a = a + a1100a = a + 11001a = a + a +1101115 .a =10001GF(24)中每个元素都可表示成它的自然基地1,a,a2,a3 (在域GF(2)上)的线 性组合，如下形式：3 2asa a?a aa a因此在GF(24)上的24进制RS码，它的编码电路可用k或n-k级24进制寄存 器实现。本例是用n -k

8、 = 6级乘法器电路实现，如下图。图中的移位积存器必须是由能积存16进制的元件组成，这可用4级触发器组成的移存器完成。a10,a14,a4,a6,a9常乘器可用模2加法器构成。在域GF(24)上的系数a10,a14,a4,a6,a9可用自然基地表示为如下形式:10 3 2 13 12 11 10a (83a a?a aa a) - 83a a?a aa aa= a3(a3 a2 1) a2(a3 a2 a 1) a1(a3 a2 a) a0(a2 a 1)=3 a2 aja3 (a? a? aa)a2 (a? aa)a (a? a。)14/ 3 2 、 17 16 15 14a (a3a a2

9、a a1a a0) = a3a a2a a1a a3 2=aa a3a a?a (aa。)43 2 0 7 6 5 -. 4a (a3a a2a a1a a0a ) =a3a a2a a1a a0a= a3(a3 a 1) a2(a3 a2) a1(a2 a) a0(a 1)=3 a?)a3 (a? aja2 (a? aa)a a。)6 3 2 . 9 8 7 6a (a3a a2a a1a a0)=a3a a2a a1a a0a二 a3(a3 a) a2(a2 1) a1(a3 a 1) a0(a3 a2)32=3 a1 ao)a (a? a)a 3 a a)a (a? aja9(a3a3

10、a2a2 a1a a0)=a3a12 a2a11 a1a10 a0a9ai a)a a)=a3(a3 a2 a 1) a2(a3 a2 a) a1(a2 a 1) a0(a3 a) =3 a2 a)a3 Q3 a? aja2 Q3 a?a10(a3a3 +a2a2 +aa + a0)=3 +a? +a)a3 +(a3 +a?+ 印 + a)a2 + (a?式中：a3=a3 +a2 十 aa2= 83+ a? + aa*=a2 +a +a0a0 | = a2 + a0ja：GF(24)中乘a10的转换电路如下表示:ai a)a (a? a。)aH JL I IH l HKa。GF(214)中乘a

11、10电路GF(24)中乘a14的转换电路如下表示:a?= a? aiGF(214)中乘a14电路a31 = a3 a?GF(24)中乘a4的转换电路如下表示:a31 二 a。二 a3a* = a2a。 = a3GF(214)中乘a14电路GF(24)中乘a6的转换电路如下表示:GF(214)中乘a6电路GF(24)中乘a9的转换电路如下表示:a3 J a3 a2 a0a? i = a3 a? aiai、a3 a2 aa。 aoa? aiGF(214)中乘a9电路15,9,7 RS编码器具体实现电路如下图所示:符界输入9f ?RS编码瞬工作过程如下：(1) 门打开，开关拨到符号输入端，所有移存器清 0。然后将6个16进制信 息符号，一边送入移存器，一边送入信道。注意每一节拍移动一个16进制符号。(2)6个16进制符号送入移存器后，完成除法运算，移存器中的就是余式。此时，门关闭，开关拨到下面。再经过 6个节拍的移动，得到所有6个校验元, 并且跟随信息元送入信道，完成一个码字的编码过程。(3)清洗积存器，打开门，开始第二组信息元的编码。