0%

CRC8计算

发表于 更新于 分类于 ， 阅读次数： Valine：

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

crc8_calc_runtimeview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/user/bin/env python3
# coding=utf-8
__author__ = "wu_chenxu@126.com"
__version__ = "1.1"
__date__ = "2019-12-21"
import os
Polynomial=0x1D
InitialValue = 0xFF
XorValue = 0xFF
def crc_1byte(data):
	crc_1byte = data
	for i in range(0,8):
		if (crc_1byte & 0x80):
			crc_1byte <<= 1
			crc_1byte^=Polynomial
		else:
			crc_1byte<<=1
		crc_1byte &= 0xFF	
	return crc_1byte
def crc_byte(data):
	crcTemp = InitialValue 
	for byte in data:
		crcTemp = (crc_1byte(crcTemp^byte))
	return XorValue^crcTemp
if __name__ == '__main__':
	print("Polynomial=",hex(Polynomial))
	print("InitialValue=", hex(InitialValue))
	print("XorValue=", hex(XorValue))
	while True:
		string_input = input("please input data:")
		input_list = string_input.split()
		print(input_list)
		input_list = [eval(a) for a in input_list]
		print("CRC value:", hex(crc_byte(input_list)))
	os.system('pause')

根据长度为256的CRC表计算CRC

如果事先存储好CRC表，可以以空间换取时间

crc8_calc_tableview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#!/user/bin/python3
# coding=utf-8
__author__ = "wu_chenxu@126.com"
__version__ = "1.1"
__date__ = "2019-12-21"

import os
Polynomial=0x1D
InitialValue = 0xFF
XorValue = 0xFF
crc8_table=[]
def crc_1byte(data):
	crc_1byte = data
	for i in range(0,8):
		if (crc_1byte & 0x80):
			crc_1byte <<= 1
			crc_1byte^=Polynomial
		else:
			crc_1byte<<=1
		crc_1byte &= 0xFF	
	return crc_1byte
		
def generate_crc_table():
	for i in range(0,256):
		crc8_table.append(crc_1byte(i))
		
def print_crc8table():
	#print as C array	
	print("uint8 g_crc8_table[256] = {")
	for i in range(0,256):
		if (i % 8 == 0):
			print("/*", i, ":*/", end='')
		print(hex(crc8_table[i]), end='')
		if (i <255):
			print(", ", end='')
		if ((i+1) % 8 == 0):
			print()
	print("}")
	
def crc_byte(data):
	if len(crc8_table) != 256:
		generate_crc_table()

	crcTemp = InitialValue 
	for byte in data:
		crcTemp ^= byte
		crcTemp = crc8_table[crcTemp]
	return (XorValue^crcTemp)
	
if __name__ == '__main__':
	print("Polynomial=",hex(Polynomial))
	print("InitialValue=", hex(InitialValue))
	print("XorValue=", hex(XorValue))
	generate_crc_table()
	print_crc8table()
	while True:
		string_input = input("please input data:")
		input_list = string_input.split()
		print(input_list)
		input_list = [eval(a) for a in input_list]
		print("CRC value:", hex(crc_byte(input_list)))
	os.system('pause')

Reference:

  1. CRC wiki
  2. AUTOSAR_SWS_CRCLibrary
  3. CRC online
  4. CRC_32分段快速查表算法在某遥测系统中的实现