第6章 信道编码 (后半部分)1.ppt

1、第6章 信道编码 （后半部分）,6.3.3码距、纠错能力、MDC码及重量谱,N重码矢c = (cn-1,c n-2,c1,c0)可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集 发码一定在这个子集里，传输无误时的收码也一定位于该子集 当出现差错时，接收的N重矢量: 对应到子集外空间某一点 对应到该子集，却对应到该子集的另一点上,6.3.3码距、纠错能力、MDC码及重量谱,码集各码字间的距离是不同的，码距最小者决定码的特性，称之为最小距离dmin 这里dmin=3，纠错能力是1，检错能力是2,6.3.3码距、纠错能力、MDC码及重量谱,定理6.1 任何最小距离dmi

2、n的线性分组码，其检错能力为（dmin-1）, 纠错能力t为 定理6.2 线性分组码的最小距离等于码集中非零码字的最小重量 dmin = min w (C i )C iC 及C i 0,6.3.3码距、纠错能力、MDC码及重量谱,定理6.3 (n,k) 线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有（dmin-1)列线性无关。 定理6.4 (n,k) 线性分组码的最小距离必定小于等于 (n-k+1) dmin (n-k+1),6.3.3码距、纠错能力、MDC码及重量谱,例： H (7，4)线性码 各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任

3、意3列线性相关。所以该码的最小距离为3，小于n-k +14。,6.3.3码距、纠错能力、MDC码及重量谱,（n,k）线性码最小距离dmin的上边界是n-k +1。如果我们设计的（n,k）线性码的dmin达到了n-k +1，就是达到了设计性能的极点。因此，dmin n-k +1的码称为极大最小距离码 (MDC Maximized minimum Distance Code)。 总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分布特性有关。, 6.3.4完备码(Perfect code),任何一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于

4、任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件 上式称作汉明限，任何一个纠t码都应满足上述条件。, 6.3.4完备码,某二元(n,k)线性分组码能使等式 成立，即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首，而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。这样的二元(n,k)线性分组码称为完备码。,汉明码(Hamming Code),汉明码不是指一个码，而是代表一类码。 汉明码的纠错能力t = 1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服

5、从以下规律： (n,k)=(2m-1, 2m-1-m) 其中m= n-k，是正整数。 当m3、4、5、6、7、8时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)。 汉明码是完备码，因为它满足上述等式。,汉明码校验矩阵的构成,汉明码的校验矩阵H具有特殊的性质，能使构造方法简化。一个(n,k)码的校验矩阵有nk行和n列，二进制时n-k个码元所能组成的列矢量总数是2n-k-1, 恰好和校验矩阵的列数n =2m-1相等。只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。,例 构造一个m=3的二元(7，4)汉

6、明码。 解：先利用汉明码的特性构造一个(7，4)汉明码的校验矩阵H，再通过列置换将它变为系统形式： 0 0 0 1 1 1 1 列置换 0 1 1 1 1 0 0 H = 0 1 1 0 0 1 1 1 0 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 0 1 1 G = I4 P = 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1,m3m2m1m0 c6c5c4c3c2c1c0,0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

7、1010 1011 1100 1101 1110 1111,0000 000 0001 111 0010 110 0011 001 0100 101 0101 010 0110 011 0111 100 1000 011 1001 100 1010 101 1011 010 1100 110 1101 001 1110 000 1111 111,A(x)=1+7x3+7x4+x7 dmin=3, t=1,完备码 t 1,扩展码,如果给每个码字添加一位奇偶校验位ci(n+1) ： ci=ci1,ci2,cin , ci(n+1)， 构成（n1，k）线性码，称为扩展码。 在二进制偶校验时： 原来码

8、字中1的个数为偶数，则添加校验位0； 原来码字中1的个数为奇数，则添加校验位1。 如果某码原来的最小重量dmin是奇数，则新的最小距离变为dmin +1，检错能力增1。 校验矩阵He ,H,m3-0 c7- 0,0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111,00000000 00011110 00101101 00110011 01001011 01010101 01100110 01111000 10000111 10011001 10101010 10110100 110011

9、00 11010010 11100001 11111111,缩短码,把第一位为1的所有码字舍去，剩下另一半第一位为0的码字舍去它们的第一位后组成一个新的( n1，k1)系统码，称为缩短码。 码长n1和信息位长度k1均缩短了。( n1，k1)缩短码共包含2k2=2k-1个码字。 由于原先保留的均是第一位为0的码，舍去它们的第一位不会改变码的最小重量，因此缩短码与原码具有同样的dmin。称为（n-1, k-1, dmin）缩短码。,例：(7,4)码的生成矩阵为 47,m3m2m1 m0ci2ci1ci0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1

10、 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 1 0 ,CimG m3m2m1m0 码字中的c6去掉，c6是信息位m与G的第一列相乘结果，所以G的第一列应去掉；m3去掉，而m3是与G的第一行相乘，所以G的第一行也去掉。,G G 36 原来的校验矩阵H为 H 37 校验时，计算rHT，因r的第一位已没有，故HT的第一行应去掉，即H的第一列去掉。 得到新的校验矩阵H为 H 36,高莱（Golay）码,是二进制（23，12）线性码， 其最小距离dmin7，纠错能力t =

11、3。 是完备码，因为满足等式 223-12 = 2048 = 在(23,12)码上添加一位奇偶位即得二进制线性（24，12）扩展高莱码，其最小距离dmin8。,6.3.5 循环码,循环码是线性码的一个子类； 满足下列循环移位特性：码集C中任何一个码字Ccn-1cn-2 c1c0的循环移位仍是码字。,(7,3)线性分组码,m2-0 c6-0 c6-0,0000000 0011101 0111010 0100111 1110100 1101001 1001110 1011100,000 001 010 011 100 101 110 111,0000000 0011101 0100111 0111

12、010 1001110 1010011 1101001 1110100,循环码的多项式描述,一般(n,k)线性分组码的k个基底之间不存在规则的联系，因此需用k个基底组成生成矩阵来表示一个码的特征。 而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就足以表示一个码的特征。 既然只有一个基底，就无需矩阵，只要用多项式作为数学工具就足够了。,循环码的多项式定义,把码字Ccn-1cn-2 c1c0 与一个不大于n-1次的码多项式C (x)对应起来。 码多项式C (x)定义为： C(x) = cn-1xn-1+ cn-2 xn-2 +c1x +c0 对于二进制码，ci0,1, i = 0,

13、，n-1。,循环码的循环移位,循环移一位：(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),数字电路中乘法左移（二进制向高位移），除法

14、右移，反之。,码字的组成,根据码空间的封闭性， 码字的线性组合仍是码字。 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的任意多项式。对于二进制码，ai0,1, i = 0,，n-1。,生成多项式,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

15、)次的首一码多项式 ，即(n-k)次项的系数为1 。（其他的可能是1也可能是0） g(x)一定是(xn+1)的因子。,校验多项式,多项式xn+1可因式分解为xn+1g(x)h(x)的形式； 如果g(x)代表(n，k)循环码的生成多项式，则h(x)代表该循环码的一致校验多项式，其阶次为k。 h(x)的校验作用表现在：任何码多项式C(x)与h(x)的模xn+1乘积一定等于0，而非码字与h(x)的乘积必不为0。 C(x)h(x) = m(x)g(x)h(x) = m(x)( xn+1) = 0 mod(xn+1),例 6.5 研究一个长度n=7的循环码的构成方法,(1)对(x7+1)作分解，找出n-

16、k次因式。 x7+1(x+1)(x3+x2+1)(x3+x+1)， n-k 因式g(x) 对偶式h(x) 循环码 1 (x+1) (x3+x2+1)(x3+x+1) (7,6) 3 (x3+x2+1) (x+1)(x3+x+1) (7,4) 3 (x3+x+1) (x+1)(x3+x2+1) (7,4) 4 (x+1)( x3+x2+1) (x3+x+1) (7,3) 4 (x+1)(x3+x+1) (x3+x2+1) (7,3) 6 (x3+x2+1)(x3+x+1) (x+1) (7,1),构成(7,3)循环码： 选g(x) =(x+1) (x3+x+1) = (x4+x3+x2+1)，则

17、C(x)=m(x)g(x)= (m2x2+m1x+m0) (x4+x3+x2+1) 当输入信息m=(011)时，m(x)=(x+1)，C(x)=( x+ 1)(x4x3x21) = x5+ x2+ x1+ 1， 对应码矢C = (0100111)。,依次将（000）（111)代入可得全部码表如下表：,例：构造（7，4）循环码,x7+1(x+1)(x3+x2+1)(x3+x+1) g(x)= x3+x2+1或g(x)= x3+x+1 C(x)=m(x)g(x) g(x)= x3+x+1 求G 系统化,循环移位得来,g(x)= x3+x+1 C(x)=m(x)g(x),=mk-1 mk-2m0 =

18、mk-1 mk-2m0 其中，g(x)=gn-k xn-k+ g1 x + g0,生成多项式与生成矩阵,将矩阵中的多项式改写成对应的n重矢量形式，得矢量的矩阵表达式： C=(cn-1,c1, c0)=mk-1,m1, m0 = mG 这里，我们定义(kn)矩阵G为循环码的生成矩阵,生成矩阵G的每一行是n重空间的一个基底，也是k维n重码空间的一个基底。在一般线性分组码的生成矩阵中，这些基底除线性无关外没有什么特殊关系。然而我们从式(4-10)看到，循环码生成矩阵的k个基底，是一个基底(gn-k g1 g0 0 0)的循环移位得出的。因此只要知道一个基底，其它(k-1)个基底可通过循环移位得出,循环码的(n-k)n阶的校验矩阵可写为： H= (4-13) 循环