循环冗余校验码.ppt

循循环冗余校冗余校验编码（CRC）CyclicRedundancychecking(CRC)循循环冗余校冗余校验，又称多，又称多项式式码。在循在循环冗余校冗余校验中，不是通中，不是通过将各比特位将各比特位相加来得到期望的校相加来得到期望的校验，而是通，而是通过在数据在数据单元末尾加一串冗余比特，称作元末尾加一串冗余比特，称作循循环冗余冗余校校验码或或循循环冗余校冗余校验余数余数，使得整个数，使得整个数据据单元可以被另一个元可以被另一个预定的二定的二进制数所整制数所整除。除。1.CRC校验基本思想校验基本思想CRC校验的基本思想是：(1)(1)根根据据欲欲发发的的k位位信信息息生生成成一一个个r比比特特的的序序列列，称称为为帧帧校校验验序序列列FCS（Frame checkingSeries）。）。（2 2）求求出出实实际际发发送送的的数数据据帧帧（k+rk+r位位），这这个个帧帧所所对对应应二二进进制制序序列列恰恰好好能能够够被被某某个个预预先先确定的确定的数数（生成多项式）整除。（生成多项式）整除。（3 3）接接收收器器用用相相同同的的数数（生生成成多多项项式式）去去除除传传来来的的帧帧。如如果果无无余余数数，则则认认为为无无差差错错；如如果余数不为果余数不为0 0，刚认为传输出错。，刚认为传输出错。奇偶校奇偶校验对一个字符校一个字符校验一次，适合异一次，适合异步通步通讯；而；而CRC对一个数据一个数据块（frame）校）校验一次，适合同步通一次，适合同步通讯。在串行同步通信中，几乎都使用在串行同步通信中，几乎都使用这种校种校验方法。如磁方法。如磁盘信息的信息的读/写等。写等。2.CRC校验常用场合校验常用场合CRC码生成和校生成和校验基本分基本分为三步三步：第第一一步步：在在数数据据单元元(k(k位位）的的末末尾尾加加上上r r个个0 0。r r是是一一个个比比预定定除除数数的的比比特特位位数数(r+1)(r+1)少少1 1的数。的数。第第二二步步：采采用用二二进制制除除法法将将新新的的加加长的的数数据据单元元（k+rk+r位位)除除以以除除数数。由由此此除除法法产生生的的余余数数就就是是循循环冗冗余余码校校验码。3.CRC码的生成码的生成第三步：求第三步：求CRCCRC循循环冗余校冗余校验码(K+r)被除数被除数+r(余数余数)如果余数位数小于如果余数位数小于r，最左的缺省位数最左的缺省位数为0。如果余数如果余数为0,则r=0。CRC码的生成码的生成CRC码校校验：到到达达接接收收方方的的数数据据单去去除除以以用用来来产生生循循环冗余校冗余校验余数的余数的G G（X X）。）。如如果果余余数数0 0，将将通通过检验。如如果果余余数数非非零，将通不零，将通不过检验。4.CRC码的校验码的校验任何一个二任何一个二进制数序列可以和一个只含有制数序列可以和一个只含有0和和1两个系数的代数多两个系数的代数多项式建立起一一式建立起一一对应的关系。因此，用来求的关系。因此，用来求CRC码的那个除的那个除数通常用多数通常用多项式来表示。原因如下：式来表示。原因如下：代数多代数多项式很短式很短可以通可以通过多多项式来式来进行概念的数学行概念的数学证明。明。5.多多项式式多多项式式任何一个任何一个n位的二位的二进制数都可以用一个制数都可以用一个n-1次的多次的多项式来表示式来表示,这种多种多项式叫式叫码多项式（又叫信息多（又叫信息多项式）式）。码多多项式与二式与二进制序列之制序列之间的一一的一一对应关系：关系：（an-1 an-2a1a0）NA(x)=an-1Xn-1+an-2Xn-2+a1X+a0X0码多项式多多项式式二二进制序列制序列实例例以以n=3位二位二进制数制数为例例二二进制数制数对应多多项式式000 001 010 01110010111101xx+1x2x2+1x2+x+1n1011011 x6+x4+x3+x+1nx5+x4+x2+x 110110码多多项式运算法式运算法则:二二进制制码多多项式的加减运算式的加减运算为 模模2加运算，加运算，即两个即两个码多多项式相加式相加时，对应项系数系数进行模行模2加减。加减。乘除运算与普通多乘除运算与普通多项式式类似；似；模模2加减：即各位做不加减：即各位做不带进位、借位的按位、借位的按位加减。位加减。这种加减运算种加减运算实际上就是上就是逻辑上的异或运算。即加法和减法等价。上的异或运算。即加法和减法等价。码多多项式式生成多生成多项式式G(x):求求CRC码时所用的所用的“除数除数”所所对应的多的多项式叫式叫生成多项式。在串行通信中通常使用下列三种生成多在串行通信中通常使用下列三种生成多项式式G（X）来）来产生生CRC码。CRC-16CRC-16：G(x)=XG(x)=X1616+X+X1515+X+X2 2+1+1，美国二进制同，美国二进制同步系统中采用。步系统中采用。CRC-CCITTCRC-CCITT：G(x)=XG(x)=X1616+X+X1212+X+X5 5+1+1，CCITTCCITT推荐。推荐。CRC-32CRC-32：G(x)=XG(x)=X3232+X+X2626+X+X2323+X+X2222+X+X1616+X+X1212+X X1111+X+X1010+X+X8 8+1X+1X7 7+X+X5 5+X+X4 4+X+X2 2+X+1+X+1码多多项式式循循环冗余冗余码生成器采用模生成器采用模2 2除法。下除法。下图显示了示了这一一过程。程。CRCCRC校校验器的功能完全像器的功能完全像发生器一生器一样，当，当收到附加了收到附加了CRCCRC码的数据后，做同的数据后，做同样的模的模22除法。如果余数是全除法。如果余数是全0 0，则将将CRCCRC码丢弃，接受数据。否弃，接受数据。否则，丢弃收到的数据。弃收到的数据。6.CRC码生成器和校验器码生成器和校验器CRC校校验码的生成器和校的生成器和校验器器r个比特0数据g(x)CRC校验码r+1r余数先发数据位先发数据位后发校验位后发校验位g(x)余数r+1r数据0接收，非接收，非0拒绝拒绝数据发送方发送方接收方接收方 0G(X)1010CRC校校验码信息信息码CRC冗余校冗余校验码7.CRC码性能码性能CRCCRC码是很有效的差错校验方法。码是很有效的差错校验方法。除了正好除了正好数据数据块的比特的比特值是按除数是按除数值变化的化的错误外，外，循循环冗余校冗余校验(CRC)将将检测出其他所有出其他所有错误。而且，常用的而且，常用的CRC除数通常有除数通常有17，或是，或是33个比特，使得不可个比特，使得不可检测的的错误可能降低到几可能降低到几乎近于零。乎近于零。CRC接收接收电路再配上适当的硬件路再配上适当的硬件电路不路不仅可可以以检错，而且可以，而且可以纠错，纠错能力很能力很强特特别适合适合检测突突发性性错误，在数据通信中得到，在数据通信中得到较广泛的广泛的应用。用。检错性能性能能能检测出全部出全部单个个错误能能检测出全部随机二位出全部随机二位错误能能检测出全部奇数个出全部奇数个错误能能检测出全部出全部长度小于度小于k位的突位的突发错误能以能以1-（1/2）k-1概率概率检测出出长度度为（k+1）位的突）位的突发性性错误课堂堂练习题设某一循某一循环码，其生成多，其生成多项式式为G（X）=X5+X2+1，试求出信息序列的循求出信息序列的循环校校验码CRC（要求写出（要求写出计算步算步骤）。）。设某一循某一循环码，其生成多，其生成多项式式为G（X）=X5+X4+X2+1，试求出信息序列求出信息序列1010001100的的CRC循循环校校验码（要求写出（要求写出计算步算步骤）。）。