ch2. 纠错编码.ppt

汉明码监督矩阵构成的两种方式： 构成 H 阵的标准形式， 。 按m位的二进制数的自然顺序从左到右排列（不包括全0列）。当发生可纠的单个错误时，伴随式为 H 阵中对应的列，译码比较方便。 非标准形式的监督矩阵可以通过列置换变成标准形式的监督矩阵，纠错能力保持不变。 如果给汉明码添加一位奇偶校验位，可得到扩展汉明码： 信息位保持不变，监督位增加一位。 最小码距 ， 可纠正一位错误，同时发现两位错误。 扩展汉明码的监督方程： 循环码是线性分组码的一个重要子集。 循环码除了具有线性分组码的一般性质外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。 循环码有严密的代数学理论基础，检错和纠错能力较强，而且编码和解码设备都不太复杂。 9.3 循环码 循环码 1)对于二进制码，码多项式的每个系数不是0就是1。 2) 仅是码元位置的标记。我们并不关心 的取值。 3) 码多项式与码字的关系：本质上是一回事，仅是表示方法的不同而已。 设循环码的码字为 ，用码多项式表示为 码字（1100101）可以表示为：  ? 循环码的循环特性可以用码多项式来证明。 在整数运算中，有模n运算。若一个整数m可以表示为:  则 在模n运算下，一整数m等于其被n除所得的余数。 循环码 在码多项式运算中也有类似的按模运算法则。 若一任意多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，也就是： ? ???????????????????????????????则可以写为：  ? 在循环码中，若 是一个长为n的许用码字，则 在模 运算下，也是一个许用码字。 某循环码的一个码字为1100101，则 若将此码左移一位，得： ? 对应的码字为1001011，与将码字1100101循环左移一位相同。 例： … 从码中取出一个前面k-1位都是0的码字，定义这个码字的码多项式为生成多项式 。 在 循环码中，除了全0码字以外，其他码字的连0个数最多只有k-1个。 码多项式的次数为 ，且常数项不为0。 循环码 信息 比特 码字 （循环1） 信息 比特 码字 (循环2） 信息 比特 码字 0001 0010 0101 0110 1000 1011 1100 0001011 0010110 0101100 0110001 1000101 1011000 1100010 0011 0100 0111 1001 1010 1101 1110 0011101 0100111 0111010 1001110 1010011 1101001 1110100 0000 1111 0000000 1111111 5 循环码 为了保证构成的生成矩阵G的各行线性不相关，通常用 这样来构造生成矩阵。 循环码 k-1 个 0 循环码 设信息码元为 时，由生成矩阵得到相应的码字的码多项式： 所有码多项式必定为 的倍式。 循环码 循环码 监督矩阵 循环码 是 的倒多项式。 循环码 循环码的校正子多项式 就是用接收到的码多项式除以生成多项式 所得的余式。 译码可分为三步： 1)由接收到的码多项式 计算校正子多项式 ； 2)由校正子 确定错误图样 ； 3)将错误图样 与 相加，纠正错误。 循环码 其中 为 维矩阵， 为 维单位矩阵。 被称为生成矩阵。 对 线性分组码，生成矩阵为 维矩阵。 对于系统码，生成矩阵可以表示为 把生成矩阵的每一行用一个行向量 来表示，则生成矩阵可以表示为 令 ，则 由于生成矩阵G的每一行都是一个码字，所以G 的每行都满足 ，则有 对于标准形式的校验矩阵和监督矩阵，有 (3) 校验矩阵和生成矩阵的关系 线性分组码的封闭性：线性分组码中任意两个码字之和仍然是该码的码字。 证明：设 和 分别是码 中的两