常用的检错码 - 奇偶校验码.docx
常用的检错码-奇偶校验码3.2过失控制3.2.2常用的检错码-奇偶校验码奇偶校验码是一种简单的检错码，奇偶校验码分为奇校验码和偶校验码，两者原理一样。它通过增加冗余位来使得码字中“1的个数保持奇数或偶数。?无论是奇校验码还是偶校验码，其监督位只要一位；?假设信息为为I1,I2,In，对于偶校验码，校验位R能够表示为：R=I1I2In?假设信息为为I1,I2,In，对于奇校验码，校验位R能够表示为：R=I1I2In1?无论是奇校验码还是偶校验码，都只能检测出奇数个错码，而不能检测偶数个错码。44讨论：从检错能力、编码效率和代价等方面来评价垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验3.2过失控制3.2.2常用的检错码-奇偶校验码奇偶校验在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。53.2.2常用的检错码定比码所谓定比码，即每个码字中“1的个数与“0的个数之比保持恒定，故又名等比码或恒比码。?当码字长一定，每个码字所含“1的数目都一样，“0的数目也都一样。?由于若n位码字中“1的个数恒定为m，还可称为“n中取m码定比码n中取m的编码效率为：logCmR=?2nn定比码能检测出全部奇数位错以及部分偶数位错。实际上，除了码字中“1变成“0和“0变成“1成对出现的过失外，所有其它差错都能被检测出来64代码“1011011对应的多项式为x6+x4+x3+1多项式“x5+x4+x2+x所对应的代码为“1101103.2.2常用的检错码循环冗余检验循环冗余码CyclicRedundancyCode，简称CRC是无线通信中用得最广泛的检错码，又被称为多项式码。二进制序列多项式：任何一个由m个二进制位组成的代码序列都能够和一个只含有0和1两个系数的m-1阶多项式建立逐一对应的关系。CRC有关的多项式：?信息位多项式、冗余位多项式、码字多项式、和生成多项式信息位1010001：K(x)=x6+x4+1冗余位1101：R(x)=x3+x2+1；码字10100011101：T(x)=x10+x8+x4+x3+x2+173.2.2常用的检错码循环冗余检验CRC校验在发送端编码和接收端校验时都利用一事先约定的生成多项式G(x)来进行。?G(x)的最高项为xr，其中，r为冗余位的长度；?在发送方，利用G(x)对xrK(x)做模2除生成冗余位；?在接受方利用G(x)对收到的码字多项式T(x)做模2除来检测错误?当码字有错误发生时，被生成多项式做除后应该使余数不为0。?G(x)的最高位和最低位必须为1。83.2.2常用的检错码循环冗余检验设生成多项式G(x)=x4+x2+x+1，现1待传输的信息位为1010001，试计算相应的CRC码；2原码字为10100011101，由于噪声的干扰，在接收端变成了10100011011，请问能否被检出？解1：K(x)=x6+x4+1；G(x)=x4+x2+x+1，r=4x4?K(x)=x10+x8+x4由除法来求余式R(x)的详细计算经过如右图所示得到CRC码为：1101加上CRC码的码字为：10100011101943.2.2常用的检错码循环冗余检验设生成多项式G(x)=x4+x2+x+1，现1待传输的信息位为1010001，试计算相应的CRC码；2原码字为10100011101，由于噪声的干扰，在接收端变成了10100011011，请问能否被检出？解2：原码字为10100011101，由于噪声的干扰，在接收端变成了10100011011，这相当于在码字上半加了过失形式00000000110。过失形式对应的多项式记为E(x)=x2+x接收端收到的就不再是T(x)，而是T(x)+E(x)(T(x)+E(x)/G(x)=T(x)/G(x)+E(x)/G(x)=E(x)/G(x)若E(x)/G(x)不等于0，则这种过失就能够被检测出来。53.2.2常用的检错码循环冗余检验对于CRC而言，生成多项式G(x)直接影响到其校验性能。研究表明，生成多项式与检错能力之间存在下面关系：?若G(x)含有(x+1)的因子，则能检测出所有奇数位错。?若G(x)中不含有x的因子，或者换句话讲，G(x)中含有常数项1，那么能检测出所有突发长度br的突发错?若G(x)中不含有x的因子，而且对任何0r+1的突发错误的漏检率为2-rWirelessandMobileNetworksTechnologyZhenzhouTangWenzhouUniversity51以CRC-16为例，其生成多项式G(x)=x16+x15+x2+1，进而其能检测出所有双错、奇数位错、突发长度小于等于16的突发错，并以1-2-15约为99.997%的概率要检出突发长度为17的突发错和以1-2-16约为99.998%的概率检出突发长度大于等于18的突发错。3.2.2常用的检错码循环冗余检验典型的标准CRC生成多项式名称多项式CRC-4x4+x+1CRC-12x12+x11+x3+x2+x+1CRC-16x16+x15+x2+1CRC-CCITTx16+x12+x5+152
