信息论其他课件第6章3循环码卷积码.pptx

信道编码,第6章,2,6.1 纠错编译码的基本原理与分析方法 6.2 线性分组码 6.3 卷积码,内容,3,6.3.3码距、纠错能力、MDC码及重量谱,N重码矢c = (cn-1,c n-2,…c1,c0)可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集 发码一定在这个子集里，传输无误时的收码也一定位于该子集 当出现差错时，接收的N重矢量: 对应到子集外空间某一点 对应到该子集，却对应到该子集的另一点上,4,码字能检、纠错误的充要条件时码字的一些码元发生错误后，这个错误的码字还没有变成其他许用码字，这样就可以判断是否有错 要使错误码字不容易变成许用码字，这要求所涉及的码字应有大的差别，而码字之间的差别可用码字之间的汉明距离来表示定理6.2 线性分组码的最小距离等于码集中非零码字的最小重量 dmin = min {w (C i )} C iC 及C i  0 证明：根据线性分组码的封闭性，任意两个码字的和仍为码集中的一个码字； 两个码字之间的汉明距离等于两个码字对应位模2和后，所形成的新码字的1的个数，即等于新码字的码重 所以线性分组码的最小码距必等于非零码字的最小重量。

5,,线性分组码的最小码距决定了线性分组码的检、纠错能力，如果给定一组码字，若码的最小码距越大，则说明任意两个码字之间的差别越大，那么检、纠错能力越强6,7,定理6.1 任何最小距离dmin的线性分组码，其检错能力为（dmin-1）, 纠错能力t为,,6.3.3码距、纠错能力、MDC码及重量谱,8,,,,,,,,t,,d=7,,,dmin=3,d=5,,,,C1,C2,C3,C4,C5,码集各码字间的距离是不同的，码距最小者决定码的特性，称之为最小距离dmin 这里dmin=3，纠错能力是1，检错能力是2,6.3.3码距、纠错能力、MDC码及重量谱,9,定理6.3 (n,k) 线性分组码最小距离等于dmin的充要条件是：校验矩阵H中任意(dmin-1)列线性无关,且有dmin个列向量是线性相关的 证明：,最小距离等于dmin，则必有一码字C具有dmin个非零分量使上式成立，即H中一定有dmin个列向量是线性相关的设H中某dmin-1个列向量线性相关，即有常数使 即可以构造一个码字C，重量为dmin-1，与码集的最小码距矛盾定理6.4 (n,k) 线性分组码的最小距离必定小于等于 (n-k+1) dmin  (n-k+1) 证明：R(H)=n-k 若码集的最小码距为dmin,则任意dmin-1列线性无关，即R(H) ≥ dmin-1 即n-k ≥ dmin-1,10,11,例： (7,3)线性码 各列都不相同，任意3列之和不等于0，3列线性无关；而最小的相关列的列数为4。

所以该码的最小距离为4，小于n-k +1＝5检错能力和校验矩阵的关系,12,(5,2)线性分组码，生成矩阵为3,C=mG，得4个对应的码字为 00000 01101 10111 11010,易知dmin=3 可以纠正1个错误 发现2个错误,对应的系统码校验矩阵为,13,校验矩阵中不存在全零的列；,h1 h2 h3 h4 h5,第i位发生错误的错误图样对应的伴随式恰好是H中第i列，H各列各不相同，保证了5种不同的错误图样对应不同的伴随式，即如果H各列各不相同，则相应的线性分组码就具有一位的纠错能力若E=11000接受到某个码R 则对应的伴随式,14,我们可能就会判断是第四位发生了错误予以纠正，C=00100+R这样就产生了错误译码 所以，这种(5,2)线性码能发现2个错误，只能纠正一个错误纠错能力t只是说明距离为t的差错一定能纠正，但并不代表大于t的差错一定不能纠正15,16,（n,k）线性码最小距离dmin的上边界是n-k +1如果我们设计的(n,k)线性码的dmin达到了n-k +1，就是达到了设计性能的极点因此，dmin＝ n-k+1的码称为极大最小距离码 (MDC – Maximized minimum Distance Code)。

总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分布特性有关6.3.3码距、纠错能力、MDC码及重量谱,17,任何一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件 上式称作汉明限，任何一个纠t码都应满足上述条件6.3.4 完备码(Perfect code),18,6.3.4 完备码,某二元(n,k)线性分组码能使等式 成立，即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首，而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用这样的二元(n,k)线性分组码称为完备码19,汉明码(Hamming Code),汉明码不是指一个码，而是代表一类码 汉明码的纠错能力t = 1，二进制汉明码码长n和信息位k服从以下规律： (n,k)=(2m-1, 2m-1-m) 其中m= n-k，是正整数 当m＝3、4、5、6、7、8…时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)…。

汉明码是完备码，因为它满足上述等式20,汉明码校验矩阵的构成,汉明码的校验矩阵H具有特殊的性质，能使构造方法简化一个(n,k)码的校验矩阵有n－k行和n列，二进制时n-k个码元所能组成的列矢量总数是2n-k-1(除全零矢量外), 恰好和校验矩阵的列数n =2m-1相等只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G21,例 6.4 构造一个m=3的二元(7，4)汉明码 解：先利用汉明码的特性构造一个(7，4)汉明码的校验矩阵H，再通过列置换将它变为系统形式： 0 0 0 1 1 1 1 列置换 1 1 1 0 1 0 0 H = 0 1 1 0 0 1 1  0 1 1 1 0 1 0 = [PT  I3] 1 0 1 0 1 0 1 1 1 0 1 0 0 1 再得生成矩阵G为 1 0 0 0 1 0 1 G = [I4  P] = 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1,,,,,22,高莱（Golay）码,是二进制（23，12）线性码， 其最小距离dmin＝7，纠错能力t =3。

是完备码，因为满足等式 223-12 = 2048 = 在(23,12)码上添加一位奇偶位即得二进制线性（24，12）扩展高莱码，其最小距离dmin＝823,6.3.5 循环码,循环码是线性码的一个子类； 满足下列循环移位特性：码集C中任何一个码字的循环移位仍是码字 对于(n,k)线性分组码中的任何一个码字,该码字向左循环移动一位后,该码字向左循环移动i位后,若 均为码字，则该线性分组码称为循环码；,24,循环码的多项式描述,一般(n,k)线性分组码的k个基底之间不存在规则的联系，因此需用k个基底组成生成矩阵来表示一个码的特征 而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就足以表示一个码的特征 既然只有一个基底，就无需矩阵，只要用多项式作为数学工具就足够了25,把码字C＝[cn-1cn-2 …c1c0] 与一个不大于n-1次的码多项式C (x)对应起来 码多项式C (x)定义为： C(x) = cn-1xn-1+ cn-2 xn-2 +…+c1x +c0 对于二进制码，ci{0,1}, i = 0,…，n-1循环码的多项式定义,26,循环移一位：(cn-1cn-2 …c1c0) (cn-2 …c1c0 cn-1) 循环移一位：C0(x) =cn-1 xn-1+cn-2 xn-2+…+c1x +c0 C1(x) = cn-2 xn-1+cn-3 xn-2+…+c0 x +cn-1 比较循环移位的前后，可用如下的多项式运算来表达循环移位 移1位： C1(x) = xC0(x) mod(xn +1) 移2位： C2(x) = xC1(x) = x2C0(x) mod(xn +1)  移n-1位：Cn-1(x) = xCn-2(x) = xn-1C0(x) mod(xn +1),循环码的循环移位,,,27,码字的组成,根据码空间的封闭性， 码字的线性组合仍是码字。

C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+…+an-1xn-1C0(x) =(a0+a1x + a2x2+…+ an-1xn-1)C0(x) =A(x)C0(x) mod(xn +1) 其中C0(x)是一个码多项式，而A(x)是次数不大于n-1的任意多项式对于二进制码，ai{0,1}, i = 0,…，n-128,C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+…+an-1xn-1C0(x) =(a0+a1x + a2x2+…+ an-1xn-1)C0(x) =A(x)C0(x) mod(xn +1) 作为特殊情况，若C0(x)为n-k次码多项式，A(x)是k-1次任意信息多项式，那么在C0(x)不变的情况下， A(x)系数的2k种组合恰好能产生2k个码字此时的C0(x)起到了生成矩阵的作用，称为生成多项式 问题是：这样的生成多项式能否找到，如何找到？,29,定理:(n,k)循环码C(x)中存在唯一的一个非零的、首一的和最低次数为(n-k)的码多项式g(x)，满足,并且，任何一个码字C(x)是码式当且仅当C(x)是g(x)的倍式C(x)=m(x)g(x),定理:(n,k)循环码C(x)中的生成多项式g(x)一定是xn+1的因子。

即g(x) ︳xn+1 反之，如果g(x)是xn+1的(n-k)次因子，则g(x)一定是(n,k)循环码的生成多项式30,生成多项式,C(x) =m(x) g(x) 码多 信息 生成 项式 多项式 多项式 g(x)＝x n-k + gn-k-1 x n-k-1+…+ g2 x2+ g1 x +1 是(n-k)次的首一码多项式 ，即(n-k)次项的系数为1 循环码的所有码字均可以由生成多项式g(x)产生，所以g(x)称为生成多项式 在(n,k)循环码中，g(x)是唯一一个(n-k)次多项式，且次数最低 每个码多项式都是g(x)的倍式，而每个为g(x)倍式且次数小于或等于(n-1)的多项式必为码多项式31,在循环码中除全“0”码字外，再没有连续k位均为‘0’的码字，否则，在经过若干次循环移位后，将得到k位信息位全为‘0’，但监督位不全为‘0’的一个码字，这性分组码中显然是不可能的 因此，生成多项式必须是一个常数项不为’0’的(n-k)次多项式，而且这个g(x)还是这种(n,k)码中次数为n-k的唯一一个多项式因为如果有两个，则有码的封闭性，把这两个相加，也应该是一个码字，且此码多项式的次数将小于(n-k),即连续’0’的个数多于k-1个，与上面所述矛盾。

生成多项式的特点,32,,以上面的结论为基础，可以找到构造(n,k)循环码的步骤： 1）对(xn+1)作因式分解，找出其n-k次因式； 2）以n-k次因式为生成多项式g(x) 3）信息多项式m(x)与g(x)相乘，既得码多项式 C(x)=m(x)g(x),,m(x)不高于k-1次，所以C(x)的次数不高于(k-1)+(n-k)=（n-1)次,33,例 6.5 研究一个长度n=7的循环码的构成方法,(1) 对(x7+1)作分解，找出n-k次因式 x7+1＝(x+1)(x3+x2+1)(x3+x+1)， n-k 因式g(x) 对偶式h(x) 循环码 1 (。