16章错误检测和校正 16.2.2RS的编码算法 RS的编码就是计算信息码符多项式M(x)除以校验码生成多项式G(x)之后的余数← 在介绍之前需要说明一些符号。在GF(2)域中,符号(n,kRS的含义如下 M 表示符号的大小,如m=8表示符号由8位二进制数组成 表示码块长度 表示码块中的信息长度 n-k=2t表示校验码的符号数 表示能够纠正的错误数目 例如,(28,24)RS码表示码块长度共28个符号,其中信息代码的长度为24,检验码有4 个检验符号。在这个由28个符号组成的码块中,可以纠正在这个码块中出现的2个分散的或 者2个连续的符号错误,但不能纠正3个或者3个以上的符号错误 对一个信息码符多项式M(x),RS校验码生成多项式的一般形式为 (x)=1(x (13-2) 式中,A是偏移量,通常取而=0或=1,而(n-k≥2t(t为要校正的错误符号数)。 下面用两个例子来说明RS码的编码原理 [例16.2]设在GF(2)域中的元素对应表如表16-01所示。假设(6,4)RS码中的4个信息 符号为m、、m和m,信息码符多项式M(x)为 M(x)=m3x+m2x+m x+mo (13-3) 并假设RS校验码的2个符号为Q和Q, M(x) M(x) 的剩余多项式R(x)为 G(x) R(x)=Qx+ Qo 这个多项式的阶次比G(x)的阶次少一阶 如果K=1,t=1,由式(13-2)导出的RS校验码生成多项式就为 x)=l(x-ako*)=(x-a)x-a) (13-4) 根据多项式的运算,由式(13-3)和式(13-4)可以得到 m3.x+m2 x+mix+mox+Qix+Qo=(x-a)(x-a)Q(x) 当用x=a和x=a2代入上式时,得到下面的方程组, m3 a+m a+mia+mo a*+Qla +Q0=0 mnx(a252+mg∞24+m1(a23+m(a2)2+Q2a2+Q=0 经过整理可以得到用矩阵表示的(6,4)RS码的校验方程: HoyO=0 0(a2)5(a2)()3(a2)2(a2) 求解方程组就可得到校验符号: Qo=m3a+ma flee kma Q1-m3a5+my a5+m,ao 在读出时的校正子可按下式计算:第16章 错误检测和校正 5 16.2.2 RS的编码算法 RS的编码就是计算信息码符多项式 M (x) 除以校验码生成多项式 G(x) 之后的余数。 在介绍之前需要说明一些符号。在GF(2m )域中，符号(n，k)RS的含义如下： M 表示符号的大小，如m = 8表示符号由8位二进制数组成 n 表示码块长度， k 表示码块中的信息长度 K=n－k = 2t 表示校验码的符号数 t 表示能够纠正的错误数目 例如，(28，24)RS码表示码块长度共28个符号，其中信息代码的长度为24，检验码有4 个检验符号。在这个由28个符号组成的码块中，可以纠正在这个码块中出现的2个分散的或 者2个连续的符号错误，但不能纠正3个或者3个以上的符号错误。 对一个信息码符多项式 M (x) ，RS校验码生成多项式的一般形式为  − = + = − 1 0 ( ) ( ) 0 K i K i G x x  (13－2) 式中，K0是偏移量，通常取K0 = 0或K0 = 1，而(n-k)≥2t (t为要校正的错误符号数)。 下面用两个例子来说明RS码的编码原理。 [例16.2] 设在GF(23 )域中的元素对应表如表16-01所示。假设(6，4)RS码中的4个信息 符号为m3、m2、m1和m0，信息码符多项式 M (x) 为 1 0 2 2 3 M (x) = m3 x + m x + m x + m (13－3) 并假设RS校验码的2个符号为Q1和Q0， ( ) ( ) ( ) ( ) 2 G x M x x G x M x x n k = − 的剩余多项式 R(x) 为 Q1 Q0 R(x) = x + 这个多项式的阶次比 G(x) 的阶次少一阶。 如果K0 = 1，t = 1，由式(13－2)导出的RS校验码生成多项式就为  − = + = − 1 0 ( ) ( ) 0 K i K i G x x  = ( )( ) 2 x − x − (13－4) 根据多项式的运算，由式(13－3)和式(13－4)可以得到 m3x 5＋m2x 4＋m1x 3＋m0x 2＋Q1x＋Q0 = (x－α)(x－α2 )Q(x) 当用x = α和x = α2代入上式时，得到下面的方程组， 经过整理可以得到用矩阵表示的(6，4)RS码的校验方程： 求解方程组就可得到校验符号： 在读出时的校正子可按下式计算：