北京邮电大学：《数据通信原理》课程教学资源（PPT课件讲稿）第十一章 差错控制编码（2/2）

教字通信原理 (92) 2001 Copyright SCUT DT&P Labs

2001 Copyright SCUT DT&P Labs 1 数字通信原理 （9-2）

第十一章差错控制编码 2001 Copyright SCUT DT&P Labs

2001 Copyright SCUT DT&P Labs 2 第十一章 差错控制编码

113循环码 1循环码的基本概念 (1)定义对线性分组码C,如对任意ccC,C循环左移或循 环右移任意位后得到的码组C仍然有ccC,则称C为循 环码。 (2)码多项式 为用代数理论研究循环码,可将码组用多项式表示,该多项 式称为码多项式 一般地,长为n的码组Cn1Cn2.C1C,对应码多项式T(x) 7(x)=Cn1x21+C +.+C1x+C 式中,x系数对应码字中C的取值。 2001 Copyright SCUT DT&P Labs 3

2001 Copyright SCUT DT&P Labs 3 11.3 循环码 1.循环码的基本概念 （1）定义 对线性分组码C，如对任意 Ci  C， Ci 循环左移或循 环右移任意位后得到的码组Ci ’ 仍然有Ci ’  C ，则称C为循 环码。 （2）码多项式 为用代数理论研究循环码，可将码组用多项式表示，该多项 式称为码多项式。 一般地，长为n的码组Cn-1Cn-2…C1C0，对应码多项式T(x) 式中，xi系数对应码字中Ci的取值。 1 0 2 2 1 1 T(x) C x C x ... C x C n n n = n + + + + − − − −

113循环码 (2)码多项式(续前) 例:(7,3)码字:1001110对应x6+x3+x2+x 对二进制码组,T(x)的系数只在二元域上取值,二元城上加乘 运算规则如下: 加运算: 0④0=00⊕1=110=111=0 乘运算 0.0=00·1=01.0=11.1=1 减法和除法可由加法和乘法定义。 2001 Copyright SCUT DT&P Labs

2001 Copyright SCUT DT&P Labs 4 11.3 循环码 （2）码多项式（续前） 例： （7,3）码字：1001110 对应 x 6＋x 3＋x 2＋x 对二进制码组，T(x)的系数只在二元域上取值，二元域上加乘 运算规则如下： 加运算： 乘运算： 减法和除法可由加法和乘法定义。 00 = 0 01=1 10 =1 11= 0 00 = 0 01 = 0 10 =1 11 =1

113循环码 (3)同余类的概念 在整数除法中,取定除数n,可将所有整数按除以n所得余数进行 分类,余数相同的数称为关于n的同余类。 一般地,若 Q为整数,p<n)(模n) 则记为: 所有余数为p的整数属于关于n的一个同余类 2001 Copyright SCUT DT&P Labs

2001 Copyright SCUT DT&P Labs 5 11.3 循环码 （3）同余类的概念 在整数除法中，取定除数n，可将所有整数按除以n所得余数进行 分类，余数相同的数称为关于n的同余类。 一般地，若 （Q为整数，p < n）（模 n） 则记为： 所有余数为p的整数属于关于n的一个同余类。 n p Q n m = + ( ) ( ) n n m  p

113循环码 (3)同余类的概念(续前) 类似地,可以定义关于多项式N(Xx)的同余类,若 F(x) =Q(x)+ RO N(x) N(x) 式中Q(x)为整式,余式R(x)的幂<N(X)的幂。 上式可写成: F(x)=Q(x)N(x)+r(x) 记为:F(x)≡R(x)mdN(x) 例:在系数为二元城的多项式中,有1=x"mod(x"+1) 因为 x"+1+1 1+ x+1x从而有上述论。 2001 Copyright SCUT DT&P Labs 6

2001 Copyright SCUT DT&P Labs 6 11.3 循环码 （3）同余类的概念（续前） 类似地，可以定义关于多项式N(x)的同余类，若 式中Q(x)为整式，余式R(x)的幂 < N(x)的幂。 上式可写成： 记为： 例：在系数为二元域的多项式中，有 因为： 从而有上述结论。 ( ) ( ) ( ) ( ) ( ) N x R x Q x N x F x = + F(x) = Q(x)N(x) + R(x) F(x)  R(x) modN(x) 1 mod( +1) n n x x 1 1 1 1 1 1 1 + = + + + + = + n n n n n x x x x x

(3)同余类的概念(续前) 113环码 定理1若T(X)是长度为n的循环码中的一个码多项式,则xT(x)按模 xn+1运算的余式必为循环码中的另一码多项式。 证明:设i=1,有x(x)=Cnx"+Cn2x4++C1x2+Cox x<n=1x”+Cn-2x”-+.+C1x2+C0x xT(x) x"+1 Cn"+1) +Cm-2-"++C 2+Co*+C x"+1 Cx"-t.+cx+cx+c +1 余式为C-2x2++Cd对应码组Cn1Cn2.C1C左 循环一位之后的得到的码组: n-2.C1 Co Cn 2001 Copyright SCUT DT&P Labs

2001 Copyright SCUT DT&P Labs 7 （3）同余类的概念（续前） 11.3 循环码 定理1 若T(x)是长度为n的循环码中的一个码多项式，则x iT(x)按模 x n＋1运算的余式必为循环码中的另一码多项式。 证明：设i＝1，有 余式为 。对应码组Cn-1Cn-2…C1C0左 循环一位之后的得到的码组： Cn-2…C1C0Cn-1。 x T x C x C x C x C x n n n n 0 2 1 1 1 2 ( ) = + +...+ + − − − ( ) 1 ... 1 1 ... 1 ... 1 ( ) 0 1 2 1 1 2 1 0 1 2 1 1 1 2 0 2 1 1 1 2 + + + + + = + = + + + + + + + = = + + + + + = + − − − − − − − − − − − n n n n n n n n n n n n n n n n n x C x C x C x C C x C x C x C x C x C x C x C x C x C x x x T x 0 1 2 1 1 2 ... − − − + + + + n n Cn x C x C x C

(3)同余类的概念(续前) 113环码 (接定理1证明),若i=2 T(x)x(xT(x)x(cn-lr 女21 +…+C1x2+C0x+C +1 X十.+C1X+Cax-+ x"+1 +C1x3+ cx+c Cx+C x+ 显然,余式为对应码组Cn-1Cn-2.C1C0左循环两位之后的得到的码 组。 一般地,对任意i有 Q(x)+Cmx"+…+C x+C +C i-2 x-+. x"+1 余式对应Cn-1Cm-2-C1C左循环位之后的得到的码组。证毕 2001 Copyright SCUT DT&P Labs

2001 Copyright SCUT DT&P Labs 8 （3）同余类的概念（续前） 11.3 循环码 （接定理1证明），若i＝2 显然，余式为对应码组Cn-1Cn-2…C1C0左循环两位之后的得到的码 组。 一般地，对任意i有： 余式对应Cn-1Cn-2…C1C0左循环i位之后的得到的码组。 证毕 ( ) ( ( ) ) 1 ... 1 ... 1 1 ... 1 ( ) 1 ( ) 1 2 2 0 3 1 1 3 1 2 1 2 0 3 2 1 1 0 1 2 1 1 1 2 2 + + + + + + = + + = + + + + + = + = + + + + + + + = + = + − − − − − − − − − − − − − n n n n n n n n n n n n n n n n n n n n x C x C x C x C x C C x C x C x C x C x C x C x x x C x C x C x C x C x x x T x x x T x 1 ... ... ( ) 1 ( ) 2 2 1 0 1 1 1 + + + + + + + = + + − − − − − − − − n n i i n i n n i n i n i x C x C x C x C x C Q x x x T x

113循环码 (3)循环码的生成多项式g(Xx)及生成矩阵 一般地,线性分组可表示为 n-1n-2…n-k n-1n-2 n-klk Q 矩阵G中每一行均为一许用码组,如第行对应第个信息位为1 其余为0时生成的码组。 由于G中包含一个分块,所以G为k个独立的码组组成的矩阵。 即:任一线性分组码码组均可由k个线性无关的码组组合而成。 利用上述线性分组码的性质,设g(x)为幂次数为n-k,且 常数项不为0的多项式,则由 g(x), xg(x). k-2g(x), xk-ig(x) 可构成循环码生成矩阵G(Xx) 2001 Copyright SCUT DT&P Labs

2001 Copyright SCUT DT&P Labs 9 11.3 循环码 （3）循环码的生成多项式g(x)及生成矩阵 一般地，线性分组可表示为 矩阵G中每一行均为一许用码组，如第i行对应第i个信息位为1， 其余为0时生成的码组。 由于G中包含一个Ik分块，所以G为k个独立的码组组成的矩阵。 即：任一线性分组码码组均可由k个线性无关的码组组合而成。 利用上述线性分组码的性质，设g(x)为幂次数为n－k，且 常数项不为0的多项式，则由 g(x)，xg(x),……，x k-2g(x)，x k-1g(x) 可构成循环码生成矩阵G(x)。 C C C C G C C C I Q n n n k n n n k k ... ... | = −1 −2 − = −1 −2 −

(3)循环码的生成多项式g(x)及生成矩阵11.3循环码 循环码生成矩阵G(X) xg(x k x' g(x) G[x]= xg(x) g(x) 其中,9(x)称为循环码码生成多项式。 2001 Copyright SCUT DT&P Labs

2001 Copyright SCUT DT&P Labs 10 （3）循环码的生成多项式g(x)及生成矩阵 11.3 循环码 循环码生成矩阵G(x) 其中，g(x)称为循环码码生成多项式。                 = − − ( ) ( ) ...... ( ) ( ) [ ] 2 1 g x x g x x g x x g x G x k k