信息论与编码-第六章4.ppt

信息论与编码-循环码 上次课小结： 线性分组码的一些概念：域、矢量空间、线性 分组码； 生成矩阵和校验矩阵 伴随式与译码：伴随式的定义、标准阵列译码 表。 信息论与编码-循环码 循环码是线性分组码中最重要的一类码。 循环码的特点是：码集C中任意一个码字经循环移位后仍然是码字。 由于构成码集C的k维n重矢量空间的基底也一定是码字，因此，k个基底可以是同一个基底经循环移位得到。所以，只用一个基底就可以表示一个码的特征，也就不需要用矩阵来描述。 信息论与编码-循环码 描述循环码的重要的数学工具是多项式。 设一个码字为 ，可以用一个称为码多项式的多项式来表示，多项式的系数就是码字的各个码元的值，指数项表示码元在码字中所处的位置，即 对于二进制码， 。 信息论与编码-循环码 以此类推。 信息论与编码-循环码 从多项式的性质出发，根据近世代数理论，可以得到以下结论： (1)一个(n,k)循环码的码多项式是模(xn+1)乘运算下多项式交换环的一个主理想子环，反之，多项式交换环的一个主理想子环一定可以产生一个循环码。而主理想子环中的所有码多项式都可以由其中一个元素(码多项式)的倍式组成，这个元素称为该主理想子环的生成元，或称它为对应循环码的生成多项式。生成多项式不是唯一的，但总有一个是最低的。 信息论与编码-循环码 例题：研究一个长度为7的循环码的构成方法。 解：根据上面的循环码编码方法，首先对 做因式分解，得到 信息论与编码-循环码 所以， 的因子共有以下几种： ：次数为1（1个）； ， ：次数为3（2个）； ， ：次数为4（2个）； ：次数为6（1个）； 如果给定了n和k，那么只能选用满足要求的（n-k）次多项式作为生成多项式，本题中没有要求k，可以选用不同的多项式做生成多项式，当然会得到不同的码集。 信息论与编码-循环码 设选取 为生成多项式，则n-k=3，k=4，所以信息多项式为 信息码组共有16种不同的组合，因此，共有16个码字。 例如 则循环编码后的码多项式为 对应的码字为（0101110）。 信息论与编码-循环码 相同地，可以得到不同信息组的时候的码字。可以看出，码集中有四组码字循环 信息论与编码-循环码 一致校验多项式 如果 分解为 ，选g(x)为生成多项式，则h(x)称为码的一致校验多项式，阶次为k，和校验矩阵类似，校验多项式满足： 当然，也可以选择h(x)为码生成多项式，则g(x)就是一致校验多项式。 因此，由g(x)生成的（n，k）码和由h(x)生成的（n，k）码互为对偶码。 信息论与编码-循环码 循环码是线性分组码的一种。对于线性分组码，可以用生成矩阵来描述。具体到循环码，则简化为生成多项式。因此也一定可以用生成矩阵来描述循环码。 所谓生成矩阵，就是码空间的一组基底。而生成多项式及其移位后的一组多项式，就可以作为一组基底，因此，如果循环码的生成多项式为 信息论与编码-循环码 则生成矩阵为 这种形式的生成矩阵不是系统形式的。如果要生成系统形式的生成矩阵，则第l行应是多项式 信息论与编码-循环码 这里， 是 除以g(x)的余式，因为 所以 由于g(x)是码字，所以 也是码字，因此 也一定是码字，可以作为基底。 信息论与编码-循环码 实际上，可以由生成多项式直接得到系统码。因为系统码中，信息位占据了码字的前k个位置，而信息多项式为 如果用 乘以m(x)，得到 如果在其后加上n-k比特的校验位，就构成了码字. 信息论与编码-循环码 也就是说，要在上面的多项式后面加上次数底 于n-k的多项式。这个多项式应该是用g(x)除 ，得到的余式r(x)（商为Q(x)），即 也就是说，得到的码多项式为 由于g(x)是码多项式，因此Q(x)g(x)也是码字，这样由信息多项式得到的码字一定是系统码。 信息论与编码-循环码 归纳起来，我们可以得到由信息组得到对应系统码字的方法是： （1）由信息组得到信息多项式，将信息多项式 乘以 ； （2）用g(x)除 ，得到余式r(x)； （3）将r(x)加在