一文了解CRC校验算法知识

一口君最近工作用到CRC校验,顺便整理本篇文章和大家一起研究。

一、CRC概念

1． 什么是CRC?

CRC(Cyclic Redundancy Checksum)是一种纠错技术,代表循环冗余校验和。

数据通信领域中最常用的一种差错校验码,其信息字段和校验字段长度可以任意指定,但要求通信双方定义的CRC标准一致。主要用来检测或校验数据传输或者保存后可能出现的错误。它的使用方式可以说明如下图所示:

在数据传输过程中,无论传输系统的设计再怎么完美,差错总会存在,这种差错可能会导致在链路上传输的一个或者多个帧被破坏(出现比特差错,0变为1,或者1变为0),从而接受方接收到错误的数据。

为尽量提高接受方收到数据的正确率,在接收方接收数据之前需要对数据进行差错检测,当且仅当检测的结果为正确时接收方才真正收下数据。检测的方式有多种,常见的有奇偶校验、因特网校验和循环冗余校验等。

2． 使用方法概述

循环冗余校验是一种用于校验通信链路上数字传输准确性的计算方法(通过某种数学运算来建立数据位和校验位的约定关系的 )。

发送方计算机使用某公式计算出被传送数据所含信息的一个值,并将此值 附在被传送数据后,接收方计算机则对同一数据进行 相同的计算,应该得到相同的结果。

如果这两个 CRC结果不一致,则说明发送中出现了差错,接收方计算机可要求发送方计算机重新发送该数据。

3． 应用广泛

在诸多检错手段中,CRC是最著名的一种。CRC的全称是循环冗余校验,其特点是:检错能力强,开销小,易于用编码器及检测电路实现。从其检错能力来看,它所不能发现的错误的几率仅为0．0047%以下。

从性能上和开销上考虑,均远远优于奇偶校验及算术和校验等方式。

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

二、CRC名称的定义

这里需要知道几个组成部分或者说计算概念:多项式公式、多项式简记式、数据宽度、初始值、结果异或值、输入值反转、输出值反转、参数模型。

1、多项式公式

对于CRC标准除数,一般使用多项式(或二项式)公式表示,如下图中除数11011(poly值为0x1c)的二项式为G(X)=X4+X3+X+1,X的指数就代表了该bit位上的数据为1,(最低位为0)。

这里特别注意一下位数问题,除数的位数为二项式最高次幂+1(4+1=5),这个很重要。

2、多项式简记式

通过对CRC的基本了解我们知道,多项式的首尾必定为1,而这个1的位置在下一步计算一定为0,所以就把前面这个1给省略掉了,出现了一个叫简记式的东西,如上例中除数11011的简记式为1011,很多看过CRC高级语言源码的人会知道,对于CRC_16标准下G(X)=X16+X15+X2+1(16#18005)的poly值实际上是8005,这里使用的就是简记式。后面会对这个用法做一个说明。

3、数据宽度

数据宽度指的就是CRC校验码的长度(二进制位数),知道了CRC的运算概念和多项式,就可以理解这个概念了,CRC长度始终要比除数位数少1,与简记式长度是一致的。

以上三个数据就是我们经常能够用到的基本数据

4、初始值与结果异或值

在一些标准中,规定了初始值,则数据在进行上述二项式运算之前,需要先将要计算的数据与初始值的最低字节进行异或,然后再与多项式进行计算。

而在结果异或值不为零的情况下,则需要将计算得到的CRC结果值再与结果异或值进行一次异或计算,得到的最终值才是我们需要的CRC校验码。

这里可以看出,初始值与结果值的位数要求与数据宽度一致。

5、输入值反转与输出值反转

输入值反转的意思是在计算之前先将二项式反转,然后再用得到的新值和数据进行计算。如对于G(X)=X16+X15+X2+1(16#18005),其正向值为1 1000 0000 0000 0101,反转值则为1010 0000 0000 0001 1

输出值反转则是将最终得到的CRC结果反转。

通常,输入值反转后的结果值也会是反转的,所以这两个选项一般是同向的,我们只有在在线CRC计算器中会看到自由选择正反转的情况存在。