信息论与编码讲义第二十一讲

1、2022-2-211第七章：第七章：线性分组码7.1 分组码的概念分组码的概念7.2 线性分组码线性分组码7.4 循环码循环码7.5 卷积码卷积码2022-2-2127.4 一些特殊的一些特殊的线性分组码线性分组码本节介绍几种重要的线性分组码。一、二元一、二元Hamming码码nN=2m-1，L=2m-1-m，即二元(2m-1，2m-1-m)线性分组码。n其一致校验矩阵是如下的m(2m-1)阶矩阵H：H的(2m-1)列恰好是(2m-1)个非全0的m维向量。2022-2-2137.4 一些特殊的一些特殊的线性分组码线性分组码定义定义6.2.1 如果任一个接收向量y，都有唯一的码字u满足d(y,

2、u)t，则称该码为t阶完备码。命题命题 当一个(N，L)线性分组码是t阶完备码时，所有不同伴随式所对应的陪集首恰好是所有重量不超过t的N维向量。注意：不同伴随式的个数为2N-L，重量不超过t的N维向量的个数为定理定理6.2.1 二元Hamming码（它是二元(2m-1，2m-1-m)线性分组码）是1阶完备码。（2m=1+2m-1 ）tkkNC0tkkNLNC02此时应该2022-2-2147.4 一些特殊的一些特殊的线性分组码线性分组码二、二、Hadamard码码从Hadmard矩阵的行中选择码字可以构造出Hadamad码。Hadmard矩阵Mn是一个nn阶矩阵，其中n=2m。该矩阵满足n有一

3、行为全0行，其余的行有2m-1个0，2m-1个1。n任意两行有2m-1个位置不同， 2m-1个位置相同。10002M01101100101000004M2022-2-2157.4 一些特殊的一些特殊的线性分组码线性分组码nnnnnMMMMM22022-2-2167.4 一些特殊的一些特殊的线性分组码线性分组码以Hadmard矩阵Mn的所有行作为所有的码字，得到的码就是Hadamad码。 Hadamad码的参数如下：共有n个码字，因此共有n个信息，因此信息长为logn=m。码长为n。编码效率为R=m/n=m/2m。dmin=2m-1=n/2。生成矩阵为Mn的任意m个非全0行构成的mn阶矩阵。（？

4、）2022-2-2177.4 一些特殊的一些特殊的线性分组码线性分组码三、三、Golay码码Golay码是线性(23, 12)码，最小距离为7。将其增加一个全校验位扩展为二元线性（24,12）码，最小距离为8。表6.4.1给出了Golay码和扩展Golay码的重量分布。 2022-2-218循环码要求掌握的内容n根据多项式会写循环码的生成矩阵和校验矩阵n会写循环码生成和校验矩阵的系统形式n会画循环码的编码电路n由生成多项式的根定义循环码7.4 一些特殊的一些特殊的线性分组码线性分组码2022-2-219n定义n循环码的生成多项式和校验多项式n循环码的生成矩阵和校验矩阵n循环码的系统码形式7.4

5、 一些特殊的一些特殊的线性分组码线性分组码2022-2-2110 定义定义1：设CH是一个n.k线性分组码，C1是其中的一个码字，若C1的左(右)循环移位得到的n维向量也是CH中的一个码字，则称CH是循环码。nknVV,定义定义2：设：设是n维空间的一个k维子空间，若对任一knnnVaaa,021,v恒有knnnnVaaaa,10121,v则称Vn,k为循环子空间或循环码2022-2-2111问题一如何寻找k维循环子空间？如何设计n,k循环码？ 利用多项式和有限域的概念2022-2-2112n注： 1、GF(p)上的n维向量与GF(p)上的多项式之间有一一对应的关系pGFaaaainn,021

6、 xfaxaxannnn02211n注： 1、GF(p)上的n维向量与GF(p)上的多项式之间有一一对应的关系 2、模n 多项式F(x)的剩余类构成一个多项式剩余类环Fpx/F(x)，若在环中再定义一个数乘运算，即 pGFccaxcaxcaaxaxacnnnnnnnn,0221102211 则模F(x)的剩余类构成一个n维线性空间，定义为剩余类结合代数。2022-2-2113问题一转化为如何从模多项式xn-1的剩余类结合代数中寻找循环子空间？2022-2-2114定理 以多项式xn-1为模的剩余类线性结合代数中，其一个子空间Vn, k为循环子空间(或循环码)的充要条件是：Vn,k是一个理想。

7、循环码是模xn-1的剩余类线性结合代数中的一个理想。2022-2-2115问题二如何从多项式剩余类环中寻找理想？2022-2-2116 由于 1、多项式剩余类环中任何一个理想都是主理想主理想中的所有元素可由某一个元素的倍式构成 2、在主理想的所有元素中，至少可找到一个次数最低的首一多项式g(x),即生成多项式2022-2-2117问题三如何寻找生成多项式g(x)？2022-2-2118循环码模多项式xn-1剩余类线性结合代数中的理想生成多项式2022-2-2119生成多项式和校验多项式2022-2-2120两个定理 定理定理1(p147):GF(q)(q为素数或素数的幂)上的n,k循环码中，存

8、在唯一的n-k次首一多项式g(x)，每一个码多项式C(x)必是g(x)的倍式，每一个小于等于(n-1)次的g(x)的倍式一定是码多项式2022-2-2121两个定理 定理定理2(p148):GF(q)(q为素数或素数的幂)上n,k循环码的生成多项式g(x)一定是xn-1的n-k次因式： xn-1= g(x) h(x)。 反之，若g(x)为n-k次多项式，且xn-1能被g(x)整除，则g(x)一定能生成一个n,k循环码2022-2-2122两个结论 结论1:找一个n,k循环码，即是找一个n-k次首一多项式g(x)，且g(x)必是xn-1的因式。 xCxg结论2:若C(x)是一个码多项式，则反之，

9、若 xCxg，则C(x)必是一个码多项式2022-2-2123nExamples GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 试求一个7,4循环码。g(x)、 xg(x)、x2 g(x)、 x3g(x)、2022-2-2124循环码的生成矩阵和校验矩阵2022-2-2125 011gxgxgxgknknknkn 011hxhxhxhkkkk xhxgxn1g(x)决定生成矩阵，h(x)决定校验矩阵2022-2-2126nkknknknknknkngggggggggggggG01210110110000000 xgxgxxgxkk,212022-2-2127nknkkk

10、kkkkhhhhhhhhhhhhh12101101100000000H xhxhxxhxknkn*2*1,kkkhxhxhxh110*)(2022-2-2128循环码的系统码 模g(x)的除法问题2022-2-2129 xgxrxxmxCknmod0 xgxxmxxmxCxrknknmod2022-2-2130由于生成矩阵G中的k行要求线性无关，因此在求余式时，可选择k个线性无关的信息组 (1,0,0,0) xk-1， (0,1,0,0,0) xk-2, (0,0,0,0,1) 1)(mod()(111xgxxxxrnknk)(mod()(222xgxxxxrnknk)(mod()(0 xgx

11、xxxrknknk2022-2-2131 xrxrxrk10001000121G xri表示ri(x)的系数2022-2-2132knTIPHknTkTTxrxrxrI)(,)(,)(212022-2-2133循环码的编码原理(1)基本步骤(n,k)1、分解多项式xn-1=g(x)h(x)2、选择其中的n-k次多项式g(x)为生成多项式3、由g(x)可得到k个多项式g(x), xg(x),xk-1g(x)4、取上述k个多项式的系数即可构成相应的生成矩阵5、取h(x)的互反多项式h*(x),取h*( x), xh*( x), xn-k-1h*( x) 的系数即可构成相应的校验矩阵2022-2-2

12、134可选择k个线性无关的信息组 (1,0,0,0) xk-1， (0,1,0,0,0) xk-2, (0,0,0,0,1) 1循环码的编码原理(2)(mod()(111xgxxxxrnknk)(mod()(222xgxxxxrnknk)(mod()(0 xgxxxxrknknk2022-2-2135 xrxrxrk10001000121G xri表示ri(x)的系数2022-2-2136循环码的编码n多项式乘法和除法电路n循环码的编码电路(乘法和除法)2022-2-2137多项式乘法和除法电路2022-2-2138 011axaxaxAkkkk 011bxbxbxBrrrr 001001)

13、1(122112111baxbabaxbababaxbababaxbabaxbaxBxAxCirkrikirkirkrkrkrkrkrkrkrkrkrk2022-2-2139b0b1b2br-2b1br-1b1br输出C(x)输入A(x)a0,a1,ak 乘B(x)运算电路(利用校验多项式h(x)编码时会用到)2022-2-2140b0b1b2br-2b1br-1b1br输出C(x)输入A(x)a0,a1,ak乘B(x)运算电路akb0akb1akbr-2akbr-12022-2-2141-b1b1br-1输出商q(x)输入A(x)-b2-br-1-b0除B(x)运算电路a0,a1,ak除式B

14、(x)构成电路，被除式A(x)的系数依次送入电路2022-2-2142h0h1h2hr-2b1hr-1b1hr输入A(x)a0,a1,ak-g1gr-1输出商q(x)-g2-g0-gr-1-gr-1乘H(x),除g(x)运算电路2022-2-2143循环码编码电路2022-2-2144)()()(利用校验多项式编码级编码电路乘法电路实现非系统码形式除法电路实现系统码形式级编码电路循环码编码电路kkn2022-2-2145n-k 级编码器基本原理：利用生成多项式g(x)若要求编成非系统码形式，则利用乘法电路若要求编成系统码形式，则利用除法电路2022-2-2146n-k级乘法电路(非系统码形式)

15、取g(x), xg(x),xk-1g(x)的系数可构成生成矩阵G0110110110000000ggggggggggggknknknknknknG2022-2-2147n-k级乘法电路(非系统码形式)若信息序列 m=(mk-1, mk-2,m0),则mG对应的n维向量为：002112212111gmgmgmgmgmgmgmknkknkknkknkknkknk该n为向量正是多项式m(x)g(x)的系数2022-2-2148g0g1g2gn-k-2b1gn-k-1b1gn-k输出C(x)输入m(x)m0,m1,mk乘g(x)运算电路mk-1 gn-k-1mk-1 gn-k输入m(x)是信息序列，g

16、(x)为生成多项式mk-1 g0mk-1 g12022-2-2149nExamples GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 试画一个7,4循环码的n-k级乘法编码电路。2022-2-2150n-k级除法电路(系统码形式) (1,0,0,0) xk-1， (0,1,0,0,0) xk-2, (0,0,0,0,1) 1)(mod()(111xgxxxxrnknk)(mod()(222xgxxxxrnknk)(mod()(0 xgxxxxrknknk2022-2-2151 xrxrxrk10001000121G xri表示ri(x)的系数GC),(021mmmkk2

17、022-2-2152n-k级除法电路(系统码形式)对任意信息多项式m(x), xn-km(x)除g(x)可得余式r(x)，m(x)的系数为信息序列mr(x) 的系数为m对应的校验比特2022-2-2153n-k级除法电路(系统码形式)若信息序列 m=(mk-1, mk-2,m0)对应的多项式m(x)=mk-1xk-1+ mk-2xk-2+m0knnknkknxmxmxmxmx02211)()()()()(mod()(mod()(mod()(mod()(0221102211xrmxrmxrmxgxmxgxmxgxmxgxmxkkkknnknkkn2022-2-2154n-k级除法电路(系统码形式

18、)综上，循环码的系统码电路是信息多项式m(x) 乘xn-k,除g(x)的实现电路2022-2-2155输入m(x)m0,m1,mk-1-g1gn-k-1-g2-g0-gn-k-1-gn-k-2乘xn-k除g(x)运算电路门12022-2-2156k 级编码器基本原理：利用校验多项式h(x)为系统码编码电路2022-2-2157k 级编码器若信息序列 m=(mk-1, mk-2,m0)对应的多项式m(x)=mk-1xk-1+ mk-2xk-2+m0码多项式C(x)= m(x)g(x),且C(x)为系统码h(x)C(x)= h(x)m(x)g(x) = m(x)(xn-1) = m(x)xn-m(x) = mk-1xn+k-1+ mk-2xn+k-2+m0 xn -(mk-1xk-1+mk-2xk-2+m0)2022-2-2158k 级编码器h(x)C(x)的乘积中，xn-1, xn-2, xk次的系数为零xn-1的系数h0 cn-1 +h1 cn-1-1 + +hk cn-1-k=0 xn-2的系数h0 cn-2 +h1 cn-2-1 + +hk cn-2-k=0 xn-3的系数h0 cn-3 +h1 cn-3-1 + +hk cn-3-k=0 xk的系