CRC verification principle and manual calculation case

Leslie Shang included in Computer Networking

2022-11-07 533 words 3 minutes views

Contents

前言

一个完整的数据帧通常由以下部分构成：

帧头 + 数据 + 校验位 + 帧尾

校验位是为了保证数据在传输过程中的完整性，采用一种指定的算法对原始数据进行计算，得出的一个校验值。

接收方接收到数据时，采用同样的校验算法对原始数据进行计算，如果计算结果和接收到的校验值一致，说明数据校验正确，这一帧数据可以使用，如果不一致，说明传输过程中出现了差错，这一帧数据丢弃，请求重发。

常用的校验算法有奇偶校验、校验和、CRC，还有LRC、BCC等不常用的校验算法。

CRC算法简介

循环冗余校验（Cyclic Redundancy Check， CRC）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。

CRC 校验计算速度快，检错能力强，易于用编码器等硬件电路实现。

从检错的正确率与速度、成本等方面，都比奇偶校验等校验方式具有优势。

因而，CRC 成为计算机信息通信领域最为普遍的校验方式。常见应用有以太网/USB通信，压缩解压，视频编码，图像存储，磁盘读写等。

CRC参数模型

同样的CRC多项式，调用不同的CRC计算函数，得到的结果却不一样，而且和手算的结果也不一样，这就涉及到CRC的参数模型了。计算一个正确的CRC值，需要知道CRC的参数模型。

一个完整的CRC参数模型应该包含以下信息：WIDTH，POLY，INIT，REFIN，REFOUT，XOROUT。

NAME：参数模型名称。
WIDTH：宽度，即生成的CRC数据位宽，如CRC-8，生成的CRC为8位
POLY：十六进制多项式，省略最高位1，如 $x^8 + x^2 + x + 1$，二进制为1 0000 0111，省略最高位1，转换为十六进制为0x07。
INIT：CRC初始值，和WIDTH位宽一致。
REFIN：true 或 false，在进行计算之前，原始数据是否翻转，如原始数据：0x34 = 0011 0100，如果REFIN为 true，进行翻转之后为0010 1100 = 0x2c
REFOUT：true 或 false，运算完成之后，得到的CRC值是否进行翻转，如计算得到的CRC值：0x97 = 1001 0111，如果REFOUT为 true，进行翻转之后为11101001 = 0xE9。
XOROUT：计算结果与此参数进行异或运算后得到最终的CRC值，和WIDTH位宽一致。

通常如果只给了一个多项式，其他的没有说明则：INIT=0x00，REFIN= false，REFOUT= false，XOROUT=0x00。

常用的21个标准CRC参数模型：

CRC算法名称	多项式公式	宽度(WIDTH)	多项式(POLY)	初始值(INIT)	结果异或值(XOROUT)	输入反转(REFIN)	输出反转(REFOUT)
CRC-4/ITU	$x^4 + x + 1$	4	03	00	00	true	true
CRC-5/EPC	$x^5 + x^3 + 1$	5	09	09	00	false	false
CRC-5/ITU	$x^5 + x^4 + x^2 + 1$	5	15	00	00	true	true
CRC-5/USB	$x^5 + x^2 + 1$	5	05	1F	1F	true	true
CRC-6/ITU	$x^6 + x + 1$	6	03	00	00	true	true
CRC-7/MMC	$x^7 + x^3 + 1$	7	09	00	00	false	false
CRC-8	$x^8 + x^2 + x + 1$	8	07	00	00	false	false
CRC-8/ITU	$x^8 + x^2 + x + 1$	8	07	00	55	false	false
CRC-8/ROHC	$x^8 + x^2 + x + 1$	8	07	FF	00	true	true
CRC-8/MAXIM	$x^8 + x^5 + x^4 + 1$	8	31	00	00	true	true
CRC-16/IBM	$x^{16} + x^{15} + x^2 + 1$	16	8005	0000	0000	true	true
CRC-16/MAXIM	$x^{16} + x^{15} + x^2 + 1$	16	8005	0000	FFFF	true	true
CRC-16/USB	$x^{16} + x^{15} + x^2 + 1$	16	8005	FFFF	FFFF	true	true
CRC-16/MODBUS	$x^{16} + x^{15} + x^2 + 1$	16	8005	FFFF	0000	true	true
CRC-16/CCITT	$x^{16} + x^{12} + x^5 + 1$	16	1021	0000	0000	true	true
CRC-16/CCITT-FALSE	$x^{16} + x^{12} + x^5 + 1$	16	1021	FFFF	0000	false	false
CRC-16/X25	$x^{16} + x^{12} + x^5 + 1$	16	1021	FFFF	FFFF	true	true
CRC-16/XMODEM	$x^{16} + x^{12} + x^5 + 1$	16	1021	0000	0000	false	false
CRC-16/DNP	$x^{16} + x^{13} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^2 + 1$	16	3D65	0000	FFFF	true	true
CRC-32	$x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$	32	04C11DB7	FFFFFFFF	FFFFFFFF	true	true
CRC-32/MPEG-2	$x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$	32	04C11DB7	FFFFFFFF	00000000	false	false

CRC校验在电子通信领域非常常用，可以说有通信存在的地方，就有CRC校验：

美信(MAXIM)的芯片DS2401/DS18B20，都是使用的CRC-8/MAXIM模型
SD卡或MMC使用的是CRC-7/MMC模型
Modbus通信使用的是CRC-16/MODBUS参数模型
USB协议中使用的CRC-5/USB和CRC-16/USB模型
STM32自带的硬件CRC计算模块使用的是CRC-32模型

CRC计算

了解了CRC参数模型知识，下面手算一个CRC值，来了解CRC计算的原理。

问：原始数据：0x34，使用CRC-8/MAXIN参数模型，求CRC值？

答：根据CRC参数模型表，得到CRC-8/MAXIN的参数如下：

1
2
3
4
5


POLY = 0x31 = 0011 0001(最高位1已经省略)
INIT = 0x00
XOROUT = 0x00
REFIN = TRUE
REFOUT = TRUE

实际计算：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


0.原始数据 = 0x34 = 0011 0100，多项式 = 0x31 = 1 0011 0001
1.INIT = 00，原始数据高8位和初始值进行异或运算保持不变。
2.REFIN为TRUE，需要先对原始数据进行翻转：0011 0100 > 0010 1100
3.原始数据左移8位，即后面补8个0：0010 1100 0000 0000
4.把处理之后的数据和多项式进行模2除法，求得余数：
原始数据：0010 1100 0000 0000 = 10 1100 0000 0000
多项式：1 0011 0001
模2除法取余数低8位：1111 1011
5.与XOROUT进行异或，1111 1011 xor 0000 0000 = 1111 1011 
6.因为REFOUT为TRUE，对结果进行翻转得到最终的CRC-8值：1101 1111 = 0xDF
7.数据+CRC：0011 0100 1101 1111 = 34DF，相当于原始数据左移8位+余数。

验证手算结果：

可以看出是一致的，当你手算的结果和工具计算结果不一致时，可以看看INIT，XOROUT，REFINT，REFOUT这些参数是否一致，有1个参数不对，计算出的CRC结果都不一样。

CRC校验

按照上面CRC计算的结果，最终的数据帧：0011 0100 1101 1111 = 34DF，前8位0011 0100是原始数据，后8位1101 1111 是 CRC结果。

接收端的校验有两种方式，一种是和CRC计算一样，在本地把接收到的数据和CRC分离，然后在本地对数据进行CRC运算，得到的CRC值和接收到的CRC进行比较，如果一致，说明数据接收正确，如果不一致，说明数据有错误。

另一种方法是把整个数据帧进行CRC运算，因为是数据帧相当于把原始数据左移8位，然后加上余数，如果直接对整个数据帧进行CRC运算（除以多项式），那么余数应该为0，如果不为0说明数据出错。

而且，不同位出错，余数也不同，可以证明，余数与出错位数的对应关系只与CRC参数模型有关，而与原始数据无关。

CRC在线计算工具

在线计算：http://www.ip33.com/crc.html

总结

CRC校验并不能100%的检查出数据的错误，非常低的概率会出现CRC校验正确但数据中有错误位的情况。这和CRC的位数，多项式的选择等等有很大的关系，所以在实际使用中尽量选择标准CRC参数模型，这些多项式参数都是经过理论计算得出的，可以提高CRC的检错能力。CRC校验可以检错，也可以纠正单一比特的错误。