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

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
# coding=utf-8
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 = raw_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
# coding=utf-8
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, ":*/",
print hex(crc8_table[i]),
if (i <255):
print ", ",
if ((i+1) % 8 == 0):
print
print "}"
def crc_byte(data):
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 = raw_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分段快速查表算法在某遥测系统中的实现