RS码编码算法

1、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是一个任意整数。令信息元多项式为：2 k 1m(x) =m0 m1 m2x 亠亠 mk-1x二.RS编码器的类型1 .基于乘法形式的R

2、S编码器公式：c(x)二 m(x)g(x)结构图如下：输入%JiLlc (x)-噸浪编吗器由上面结构的乘法编码器输出的码字是非系统码2 .基于除法形式的RS编码器(1)根据生成多项式g(x)构造的除法编码器。xnka(x)g(x)b(x)器剩余多项式r(x)至少比g(x)低一次r(x) = r2t_1x21r2t-2x2t_2r2x2 jx r0则编程的码多项式为c(x)二 xn-ka(x) r(x)c2x输出码2c1xc0n 1 丄n 2二 cn_1xcn_2x除法电路构成的RS编码辭(2)根据校验码多项式h(x)构造的除法编码器设校验多项式为：h(x) = hkxkhkx11 亠 亠 h1

3、x h0系统码的多项式为:C(X)二C n_iXn5 _2乂"25kx" 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)

4、- k - 1所以q(x)xn的最低位次数至少为n次，而在h(x)C(x)的乘积中xn T,x门一2,xk的次数为0。X1的系数：Cn _1h° C n_i_ihi C n_i_khkxn _2的系数：Cn _2血 Cn_2_lhiCn_2_khk而k工 Cn jhj =0i = 0,1,2,，n - kro由于h(x)为首一多项式，hk =1，故上式可写为k -1Cn_k_i 八' Cnijhji = 1,2, ,n-kj=0上式展开为：Cn -k = -(Cn-1ho Cn_2hiCn-khk-1)Cn _k_2 = (Cn_2ho Cn -3h1 Cn-k-1hk-1)

5、-Cn -k-(n-k) - Co 八(Ckho “柑qhk_1)由上式看出码字C的第一个码元Cn kJ可由k个信息元Cn _1,C n_2,，c n_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(

6、q)上的，这里q= 2。这里我们选用GF(16)域来进行，域中16个元素可用4bits符号表示。例 构造一个能纠正3个错误符号，码长为15, m=4的RS码。求生成多项式和 编码电路。解：当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 =

7、0或a4 = a 1以x4 x 1为模的GF(24)的元素如下表：a0 =1000182斗a = a +10101a001093a = a + a10102 a0100a = a + a + 101113 a1000113 丄2a = a + a + a1110a4 = a + 10011a =a + a +a + 11111a5 = a2 + a0110a = a + a + 1110163+2a = a + a1100a = a + 11001a = a + a +1101115.a =10001GF(24)中每个元素都可表示成它的自然基地1,a,a2,a3 (在域GF(2)上)的线 性组

8、合，如下形式：32asaa?aaaa°14信息符号L15p9JRS编创电路图TICD因此在GF(24)上的24进制RS码，它的编码电路可用k或n-k级24进制寄存 器实现。本例是用n -k = 6级乘法器电路实现，如下图。图中的移位积存器必须是由能积存16进制的元件组成，这可用4级触发器组成的移存器完成。a10,a14,a4,a6,a9常乘器可用模2加法器构成。输出码在域GF(24)上的系数a10,a14,a4,a6,a9可用自然基地表示为如下形式:1032131211103 a23 a2a(83aa?aaaa°)-83aa?aaaa°a= a3(a3 a21)

9、a2(a3 a2 a 1) a1(a3 a2 a) a0(a2 a 1)=3a2aja3(a?a?aa°)a2(a?aa°)a(a?a。)14/32、17161514a(a3aa2aa1aa0)=a3aa2aa1aa32=a°aa3aa?a (aa。)4 320765 -.4a (a3aa2aa1a a0a ) =a3a a2a a1a a0a= a3(a3a 1)a2(a3 a2)a1(a2 a)a0(a1)=3 a?)a3 (a? aja2 (a?aa°)a a。)63 2.9 876a (a3aa2a a1aa0)=a3a a2aa1aa0a二 a

10、3(a3a) a2(a21) a1(a3a 1)a0(a3a2)3 2=3 a1 ao)a(a? a°)a 3 a a°)a (a? aja9(a3a3 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 +a

11、2 十 aa2= 83+ a? + aa*=a2 +a +a0a0 | = a2 + a0j'a：'GF(24)中乘a10的转换电路如下表示:ai a°)a (a? a。)aH JL I IH l HKa。GF(214)中乘a10电路GF(24)中乘a14的转换电路如下表示:ai a?a?'= a? aiGF(214)中乘a14电路a31 = a3a?GF(24)中乘a4的转换电路如下表示:a31 二 a。二 a3a* = a2a。' = a3aGF(214)中乘a14电路GF(24)中乘a6的转换电路如下表示:a3> a3a1a0a2 丨 a2a0aj = a3 - aia。ao'pai1GF(214)中乘a6电路GF(24)中乘a9的转换电路如下表示:a3 J a3a2a0a? i = a3a?aiai、a3 a2 aa。ao'a?aiGF(214)中乘a9电路15,9,7 RS编码器具体实现电路如下图所示:符界输入9f ?RS编码瞬工作过程如下：(1) 门打开，开关拨到符号