0%

CRC8计算

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分段快速查表算法在某遥测系统中的实现