第八章差错检测与校正.ppt

正反码的例子（续） 又如，若传输中发生了四位错，接收端收到1101011010，则合成码组为11010⊕11010=00000，而此时校验码组也为00000，查表会认为是无差错，也就是说对这种差错是漏捡了。 再如，若传输中发生了三位错，接收端收到1101011011，则合成码组为11010⊕11011=00001，此时校验码组也为00001，查表会认为是冗余位中有一位差错，其位置对应于校验码组中“1”的位置，从而将其误纠为1101011010。 实际上，任何一种检错码，都会发生漏检的情况；而任何一种纠错码，也都会发生误纠的情况。漏检率和误纠率都是差错控制编码的重要技术指标，当然是越小差错控制能力越强。 正反码（续） 正反码的编码效率较低，只有1/2。但其差错控制能力还是较强，如上述长度为10的正反码，能检测出全部两位差错和大部分两位以上的差错，并且还具有纠正一位差错的能力。由于正反码的编码效率较低，只能用于信息位较短的场合。 下面将介绍两种编码效率较高的，且差错控制能力较强的纠错和检错码。 8.1.3 海明码 介绍 由R. Hamming在1950年首次提出 也是一种可以纠正一位差错的编码，但当信息位足够长时，它的编码效率要比正反码高得多 回顾奇偶校验，若信息位为k=n-1位，加上一位偶校验位a0，构成一个n位的码字。在接收端校验时，可按关系式 若S=0，则无错；若S=1，则有错。上式可称为监督关系式，S称为校正因子 海明码（续） 在奇偶校验情况下，只有一个监督关系式，一个校正因子，其取值只有两种（0或1），分别代表了无错和有错两种情况，而不能指出差错所在的位置 若增加冗余位，也相应地增加监督关系式和校正因子，就能区分更多的情况。 信息位为k位，增加r位冗余位，构成n=k+r位码字 。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同位置的一位错，则要求 或 例子 以k = 4为例来说明，要满足前述不等式，则r≥3。现取r = 3，则n = k + r = 7。 在4位信息位a6a5a4a3后面加上3位冗余位a2a1a0，构成7位码字a6a5a4a3 a2a1a0 。其a2、a1和a0分别由4位信息位中某几位半加得到。那末在校验时， a2、a1和a0就分别和这些位半加构成三个不同的监督关系式。 000 001 010 011 100 101 110 111 错码位置 无错 海明码编码规则 海明码码字(Code Word) 按如下方法构建： 把所有2的幂次方的数据位标记为奇偶校验位(编号为1, 2, 4, 8, 16, 32, 64等的位置) 其他数据位用于待编码数据. (编号为3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置) 海明码编码规则（续） 每个奇偶校验位的值代表了代码字中部分数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序。 位置1：校验1位，跳过1位，校验1位，跳过1位(1,3,5,7,9,11,13,15,…) 位置2：校验2位，跳过2位，校验2位，跳过2位 (2,3,6,7,10,11,14,15,…) 位置4：校验4位，跳过4位，校验4位，跳过4位 (4,5,6,7,12,13,14,15,20,21,22,23,…) … 海明码的校验 在接收方，按照编码规则重新计算每一位校验位的值。 将错误的校验位的位置序号相加，所得到的结果就是发生错误的位的序号。 信息位 冗余位 信息位 冗余位 0000 000 1000 111 0001 011 1001 100 0010 101 1010 010 0011 110 1011 001 0100 110 1100 001 0101 101 1101 010 0110 011 1110 100 0111 000 1111 111 8.1.4 循环冗余码 在计算机网络和数据通信中用得最广泛的检错码是一种漏检率低得多也便于实现的循环冗余码CRC（Cyclic Redundancy Code） CRC码又称为多项式码。这是因为任何一个由二进制数位串组成的代码都可以和一个只含有0和1两个系数的多项式建立一一对应的关系。 代码1011011对应的多项式为x6 + x4 + x3 +1 而多项式x5 + x4 + x2 + x对应的代码为110110 8.1.4 循环冗余码 k位要发送的信息位可对应于一个（k-1）次多项式K(x)，r位冗余位对应于一个（r-1）次多项式R(x) 。由k位信息位后面加上r位冗余位组成的n=k+r位码字T(x)则对应于一个（n-1）次多项式，且T(x) = xr K(x)