ch9信道编码线性分组码以及循环码20100512版.pptVIP

第九章 差错控制编码 9.4 线性分组码 9.5 循环码 §9.4 线性分组码 可用线性方程组表述码的规律性的分组码称为线性分组码。 本节将以汉明（Hamming）码为例引入线性分组码的一般原理。 汉明码是一种能够纠正一位错码且编码效率较高的线性分组码。 因此r个监督关系式能够指示1位错码的2r – 1个可能位置。若码长为n，信息位为k，则监督位为r=n-k,则指示一位错码的n种位置要求 n=2r – 1 实例 一个码长为31的汉明码，其监督位r应该为多少？编码效率是多少？ 假设分组码(7,4)中,为了纠正1位错误,则要求r=3,取r=3,则用7位码表示该码组,S1S2S3的值与错码位置对应关系如下 得监督关系式为: 无误码时: 一般线性分组码的原理 若给定监督关系式,则如何求解所有的码组. 监督关系式矩阵 （n，k）线性分组码的监督矩阵H由r行n列组成，这r行是线性无关的。系统码的监督矩阵可写成如下形式： 则系统码的生成矩阵可写成如下形式： 例2 由典型生成矩阵产生码组集合 计算线性码组的方法 给定监督矩阵 1）求生成矩阵 2）求所有码组 给定生成矩阵 由生成矩阵求所有码组 仅仅给定码长和要求 自己给定监督矩阵 接收端 2.伴随式（校正子） 设发送码组为A，接收码组为B，错误图样 E＝B－A中哪位出现1，就表示接收码组B中相应的码元错了。接收端利用监督矩阵来检测接收码组B中的错误。令 ，称为伴随式或校正子。 S与E之间有确定的线性变换关系。即S能代表B中错误的情况，B无错S＝0，B有错S≠0。此时由S得到E，再由B＋E可得正确码组。 线性码的性质-封闭性 所谓封闭性，一种线性码中的任意两个码组之和仍为这种码中的一个码组 由于线性码的封闭性，因而两个码组之间的距离必是另一码组的重量。故码的最小距离即为码的最小重量（全0码组除外）。 实例 0000000，0001011，0010110，0011101，0100111，0101100，0110001，0111010 1000101，1001110，1010011，1011000，1100010，1101001，1110100，1111111 求该线性码组的检错与纠错能力 若线性分组码的任一码组循环移位所得的码组仍在该码组集中，则此线性分组码称为循环码。 人们常用代数多项式来表示循环码的码字，这种多项式称为码多项式.(n,k)循环码的码多项式为 码组中各位码元的数值是其码多项式中相应各项的系数值（0或1）。 码多项式的按模运算 在循环码中,若T(x)是一个长为n的许用码组,则 xi T(x)在按模xn+1运算下,也是一个许用码组, 即若: 则T’(x)也是一个许用码组 所以一个长为n的循环码，它必为按模xn+1运算的一个余式 证明 若 循环码码组集合的获取-得到生成矩阵G 1.生成矩阵中每行都是一个循环码组 2. 寻找生成矩阵的方法就是寻找k个不相关的码组，组成生成矩阵 3. 对于循环码而言，这k个不相关的码组可以看成是一个特定码组循环移位得到的 4. 因此主要的工作在于寻找这个特定码组，我们称这个特定码组组成的码多项式为生成多项式 生成多项式g(x)的特点 1. 在循环码中，除全“0”外，再没有连续k位均为“0”的码组，即连“0”的长度最多只能有k-1位，否则会出现信息位全为“0”但是监督位不全为“0” 的码组。 2. g(x)是(n,k)码中次数为(n-k)的唯一一个多项式。 如果有两个，则由码的封闭性，这两个码组相加得到的也应该是一个许用码组，该码组的连“0”个数多于k-1位。 循环码的生成矩阵G 生成多项式及生成矩阵 生成多项式g(x)表示其前面k-1位皆为0的(n-k)次多项式对应的码组 生成矩阵 如何求任意(n,k)的生成多项式 知道生成矩阵G后,则可以写出循环码组,即 因此,任一循环码组T(x)都是g(x)的倍数,可以写成 T(x)=h(x)g(x) 由于生成多项式g(x)本身也是一个码组,因此T’(x)=g(x),由于T’(x)是(n-k)次多项式,故xk T’(x)为n次多项式. 由于 循环码的生成多项式为(xn+1)的一个(n-k)次因式 （n,k）循环码的求取步骤 1.对xn+1进行因式分解 2. 从xn+1的因子中选出一个（n-k）次因式作为生成多项式g(x) 3求取生成矩阵G 4.将生成矩阵G化成典型生成矩阵 5.得到所有的循环矩阵 结论 1.线性分组码 2.循环码 * * 汉明码的构造原理 汉明码通过监督关系式和校正子来监督是否发生错误以及