信息论与编码zjh201209zjh第六章.ppt

第6章 信道编码 6.1 有扰离散信道的编码定理 差错控制系统分类 6.1.2矢量空间与码空间 例6-1二元域GF(2)上三重矢量空间V的三个自然基底是(100)，(010)，(001) 6.1.3随机编码 6.1.4信道编码定理 6.2 纠错编译码的基本原理与分析 6.2.2最优译码与最大似然译码 6.3 线性分组码 空间构成 校验矩阵 例6-2 (6,3)线性分组码，其生成矩阵是 G= (1)计算码集，列出信息组与码字的映射关系。 (2)将该码系统化处理后，计算系统码码集并列出映射关系。 (3)计算系统码的校验矩阵H。若收码r = [100110], 检验它是否码字？ (4)根据系统码生成矩阵画出编码器电原理图。 定义差错图案E E＝(en－1,…,e1,e0)＝ R－C ＝(rn-1－cn-1,…,r1－c1,r0－c0) 二进制码中模2加与模2减是等同的，因此有 E = R ＋ C 及 R = C ＋ E mod 2 6.3.4 完备码(Perfect code) 任何一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件 上式称作汉明限，任何一个纠t码都应满足上述条件。 6.3.4 完备码 某二元(n,k)线性分组码能使等式 成立，即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首，而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。这样的二元(n,k)线性分组码称为完备码。 汉明码(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)…。 汉明码是完备码，因为它满足上述等式。 汉明码校验矩阵的构成 汉明码的校验矩阵H具有特殊的性质，能使构造方法简化。一个(n,k)码的校验矩阵有n－k行和n列，二进制时n-k个码元所能组成的列矢量总数是2n-k-1, 恰好和校验矩阵的列数n =2m-1相等。只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。 高莱（Golay）码 是二进制（23，12）线性码， 其最小距离dmin＝7，纠错能力t =3。 是完备码，因为满足等式 223-12 = 2048 = 在(23,12)码上添加一位奇偶位即得二进制线性（24，12）扩展高莱码，其最小距离dmin＝8。 6.3.5 循环码 循环码是线性码的一个子类； 满足下列循环移位特性：码集C中任何一个码字的循环移位仍是码字。 循环码的多项式描述 一般(n,k)线性分组码的k个基底之间不存在规则的联系，因此需用k个基底组成生成矩阵来表示一个码的特征。 而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就足以表示一个码的特征。 既然只有一个基底，就无需矩阵，只要用多项式作为数学工具就足够了。 循环码的多项式定义 把码字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。 循环码的循环移位 循环移一位：(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) 码字的组成 根据码空间的封闭性