CRC校验简介

循环冗余校验(英语:Cyclic redundancy check,通称“CRC”)是一种根据网络数据数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数,主要用来检测或校验数据传输或者保存后可能出现的错误。

在通信协议中,为了保留CRC的突发错误检测特性,通常按照物理层发送数据位的方式计算CRC。

在数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC. CCITT,ARJ、LHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。

CRC的本质是模-2除法的余数,采用的除数不同,CRC的类型也就不一样。通常,CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有CRC16,CRC32。

基本原理

CRC为校验和的一种,是两个字节数据流采用二进制除法(没有借位和进位,使用异或来代替减法)相除所得到的余数。其中被除数是需要计算校验和的信息数据流的二进制表示;除数是一个长度为(n+1)的预定义二进制数,通常用多项式的系数来表示。在做除法之前,要在信息数据之后先加上n个0. 冗余码的位数是n位。

冗余码的计算方法是,先将信息码后面补0,补0的个数是生成多项式最高次幂;将补零之后的信息码用模二除法(非二进制除法)除以G(X)对应的2进制码,注意除法过程中所用的减法是模2减法,即没有借位的减法,也就是异或运算。当被除数逐位除完时,得到比除数少一位的余数。此余数即为冗余位,将其添加在信息位后便构成CRC码字。

例子

例如,假设信息码字为11100011,生成多项式G(X)=$X^5+X^4+X+1$,计算CRC码字。G(X) = $X^5+X^4+X+1$,也就是110011,因为最高次是5,所以,在信息码字后补5个0,变为1110001100000。用1110001100000模二除法除以110011,余数为11010,即为所求的冗余位。
因此发送出去的CRC码字为原始码字11100011末尾加上冗余位11010,即 1110001111010。接收端收到码字后,采用同样的方法验证,即将收到的码字用模二除法除以110011(是G(X)对应的二进制生成码),发现余数是0,则认为码字在传输过程中没有出错。

缺点

尽管在错误检测中非常有用,CRC并不能可靠地校验数据完整性(即数据没有发生任何变化),这是因为CRC多项式是线性结构,可以非常容易地故意改变量据而维持CRC不变。