CRC简介
CRC(Cyclic Redundancy Check),循环冗余校验码,是一种错误检测码,可以检错,但不能纠错。
CRC算法对数据进行多项式计算,并将得到的校验码(固定位数)附在数据的后面,接收设备也执行类似的算法,以保证数据传输的正确性和完整性。
不同的多项式对错误的检测率(以汉明距离(Hamming Distance)衡量)有差别,所以多项式都是经过测试精心挑选的。
多项式决定了校验码的位数,根据校验码位数不同,一般有CRC-4,CRC-8,CRC-16,CRC-32,CRC-64,CRC-128等。
CRC算法
以CRC-8来举例:
CRC-8,有8bit的校验码,取多项式(Polynomial)为:x^8+x^4+x^3+x^2+1。一般多项式最高位x^8项的系数总是1,所以隐去,标记为1Dh(1 1101b)。
将数据与多项式相除,得到的余数再与多项式相除,如此反复,所以叫循环冗余,最终得到一个8位的余数就是循环冗余校验码。
二进制的除与异或的结果一样。
1Dh也是SAE-J1850推荐的多项式;2Fh是AUTOSAR CRC-8推荐的另一个多项式。
数据:F2 01 83
binary: 11110010 00000001 10000011 00000000 <- 先在校验码位置补8个0
xor 10001110 1 <-divisor x^8+x^4+x^3+x^2+1
—————————————-
1111100 10000001 10000011 00000000
xor 1000111 01
—————————————-
111011 11000001 10000011 00000000
xor 100011 101
—————————————-
11000 01100001 10000011 00000000
xor 10001 1101
—————————————-
1001 10110001 10000011 00000000
xor 1000 11101
—————————————-
1 01011001 10000011 00000000
xor 1 00011101
—————————————-
1000100 10000011 00000000
xor 1000111 01
—————————————-
11 11000011 00000000
xor 10 0011101
—————————————-
1 11111001 00000000
xor 1 00011101
—————————————-
11100100 00000000
xor 10001110 1
—————————————-
1101010 10000000
xor 1000111 01
—————————————-
101101 11000000
xor 100011 101
—————————————-
1110 01100000
xor 1000 11101
—————————————-
110 10001000
xor 100 011101
—————————————-
10 11111100
xor 10 0011101
—————————————-
11000110 ->CRC:C6h
需要注意的是:在实际的算法中,会增加刚算法开始时初始化的值以及最后结果的异或值作为参数。
下面时AUTOSAR中对8位CRC算法J1850多项式1D的描述:

CRC计算代码
根据算法描述计算CRC
1 | #!/user/bin/env python3 |
根据长度为256的CRC表计算CRC
如果事先存储好CRC表,可以以空间换取时间
1 | #!/user/bin/python3 |
Reference: