[工程科技]数字通信原理_8：差错控制编码.ppt

10、循环码 同余类的概念 在整数除法中，取定除数n，可将所有整数按除以n所得余 数进行分类，余数相同的数称为关于n的同余类。 一般地，若 （Q为整数，p n） 则记为： 所有余数为p的整数属于关于模n的一个同余类。 第八章 差错控制编码 10、循环码 同余类的概念（续前） 类似地，可以定义关于多项式N(x)的同余类，若 式中Q(x)为整式，余式R(x)的幂 N(x)的幂。 上式可写成： 记为： 例：在系数为二元域的多项式中，有 因为： 从而有上述结论。 第八章 差错控制编码 10、循环码 循环码的代数结构 定理1 若U(X)是长度为n的循环码中的一个码多项式，则 XiU(X)（i为不等于0的整数）按模 Xn＋1运算的余 式必为循环码中的另一码多项式。 证明：设i＝1，有 第八章 差错控制编码 10、循环码 循环码的代数结构（续） 余式为 对应码组un-1 un-2… u1 u0左循环一位之后的得到的码组： un-2 … u1 u0 un-1。 若i＝2 第八章 差错控制编码 10、循环码 循环码的代数结构（续） 显然，余式为对应码组un-1un-2…u1u0左循环两位之后的得到的 码组。一般地，对任意i有： 余式对应un-1un-2…u1u0左循环i位之后的得到的码组。 证毕 (容易用归纳法严格证明) 第八章 差错控制编码 10、循环码 循环码的代数结构（续） 例 已知码组的长度为n＝4，其中一码字：U＝1101(高位在右)， 求该码字循环移位3位后得到的码字。 a. 由1101直接(右)循环移3位得：U(3)＝1011 b. 根据多项式关系求解，当i＝3时， 关于X4+1的余式U(3)(X) -? 1011 第八章 差错控制编码 10、循环码 循环码的生成多项式g(x)及生成矩阵 一般地，线性分码组可表示为 矩阵G中每一行均为一许用码组，如第i行对应第i个信息位为1， 其余为0时的信息码生成的码组。 由于G中包含一个Ik分块，所以G为k个独立的码组组成的矩阵。即： 任一线性分组码码组均可由k个线性无关的码组组合而成。 第八章 差错控制编码 10、循环码 循环码的生成多项式g(x)及生成矩阵(续) 利用上述线性分组码 任一线性分组码码组均可由k个线性无关的码组组合而成 这一性质，寻求循环码生成矩阵的构建方法。 设存在一个幂次数为n－k，且常数项不为0的码多项式g(X)， 则由循环码的性质（定理1） g(X)，Xg(X),……，Xk-2g(X)，Xk-1g(X) (最高次幂等于n－1) 也是码多项式，这k个码多项式对应独立的k个码字，由此可构 成循环码生成矩阵G(X)。 第八章 差错控制编码 10、循环码 循环码的生成多项式g(X)及生成矩阵(续) 循环码生成矩阵G(X)： 其中，g(X)称为循环码码生成多项式。G(X)对应的系数矩阵G 右侧的子方阵具有主对角线元素均不为0的形式。该子阵行列 式不为0，因而子阵满秩，因而行向量是线性无关的。 利用码生成矩阵G(X)，任一码字多项式可以表示为： 或： 第八章 差错控制编码 10、循环码 循环码的生成多项式g(X)及生成矩阵(续) 例（7，3）生成多项式 g(X)＝X4+X3+X2+1 对应生成矩阵G[X] 矩阵为： 因为矩阵G左侧的子方阵满秩，因此容易判断该矩阵中的 行向量是线性无关的。 第八章 差错控制编码 10、循环码 循环码的生成多项式g(X)及生成矩阵(续) 定理 2 在循环码中，n－k次的码多项式g(X)有一个且只有 一个。 证明： （a）在含k个信息位的循环码中，除全0码外，其它码 组最多只有k-1个连0。否则，经循环移位后前面k个信息码 元为0，而监督码元不全为0的码组，这在线性分组码中是不 可能的。所以一定有一个n－k次的多项式。 （b）n－k次的码多项式g(X)的常数项不能为0，否则 该多项式右移一位就会出现k个连0的情况。 第八章 差错控制编码 10、循环码