CRC8算法的解读,以及在E2E通信保护的应用
CRC8算法的解读,以及在E2E通信保护的应用
目录
- 📙 <font color=orange>CRC8在报文E2E保护中的两种计算方式(预览)
- 🍅 <font color= YellowGreen > 直接计算CRC8校验位
- 🍅 <font color= YellowGreen > 查表法计算CRC8校验位
- 📙 <font color=orange>理解基础:模2 运算
- 🍅 <font color= YellowGreen > 模2加减法(等同于异或操作)
- 🍅 <font color= YellowGreen > 模2乘法
- 🍅 <font color= YellowGreen > 模2除法
- 模2除法(CRC)循环冗余校验码在线计算器在线计算平台
- 📙 <font color=orange>理解基础:循环冗余校验
- 🍅 <font color= YellowGreen > 循环冗余校验简介
- 🍅 <font color= YellowGreen >为何要校验数据完整性(Data Integrity)?
- 🍅 <font color= YellowGreen >何为循环冗余校验?
- 📙 <font color=orange>CRC的算法原理
- 🍅 <font color= YellowGreen >CRC参数模型
- 🍅 <font color= YellowGreen >CRC8查表法,表怎么生成的?
- 🍅 <font color= YellowGreen >CRC8直接计算法
- 🌎<font color=orange>总结
📙 CRC8在报文E2E保护中的两种计算方式(预览)
实际仿真工程中仿真报文我们都需要计算Counter和CRC的,以CRC8校验算法为例,下列参数是CRC参数模型
- // 宽度 WIDTH : 8 bits
- // 多项式 POLY : x^8 + x^4 + x^3 + x^2 + 1 ==== 0x11d (1-0001-1101)
- //初始值 INIT : 0x0
- //结果异或值 XOROUT : 0x0
- //输入数据反转 : false
- //输出数据反转 : false
🍅 直接计算CRC8校验位
/*@!Encoding:936*//****************************************************************************************************
计算counter 值
***************************************************************************************************/
byte E2E_Counter(byte data[],byte c_pos)
{// calculate counterint Counter; Counter = data[c_pos] & 0x0F;Counter++;if(Counter > 15)Counter = Counter - 16;Counter = (data[c_pos] & 0xF0)+ Counter;return Counter;
}
/****************************************************************************************************
直接计算CRC8
***************************************************************************************************/byte E2E_CRC8(byte data[],byte d_length, byte initial_value)
{int i, j;int crc8;const byte crc_poly = 0x1D;crc8 = initial_value; // crc 计算的初始值for (i = 0; i < d_length; i++){crc8 ^= data[i]; /* 每次先与需要计算的数据异或,计算完指向下一数据 */ for (j = 0; j < 8; j++) // 多项式宽度为8,所以需要计算8次{if (crc8 & 0x80)/* 判断最高位是否为1 */{crc8 = (crc8 << 1) ^ crc_poly;}else /* 最高位为0时,不需要异或,整体数据往左移一位 */{crc8 <<= 1;}}}return crc8;}
/****************************************************************************************************
报文发出回调函数
***************************************************************************************************/dword applILTxPending (long aId, dword aDlc, byte data[])
{dword i;byte crc8;if(aId == 0x322){data[6] = E2E_Counter(data,6); data[7] = E2E_CRC8(data,7,0xff);}return 1; // don't prevent sending of the message
}
🍅 查表法计算CRC8校验位
/*@!Encoding:936*//****************************************************************************************************
计算counter 值
***************************************************************************************************/
byte E2E_Counter(byte data[],byte c_pos)
{// calculate counterint Counter; Counter = data[c_pos] & 0x0F;Counter++;if(Counter > 15)Counter = Counter - 16;Counter = (data[c_pos] & 0xF0)+ Counter;return Counter;
}
/****************************************************************************************************
查表法计算CRC8
***************************************************************************************************/byte E2E_CRC8_Table(byte data[],byte d_length,byte initial_value)
{int i;byte crc8;byte Crc8Table[256] = {0x00, 0x1d, 0x3a, 0x27,0x74, 0x69, 0x4e, 0x53,0xe8, 0xf5, 0xd2, 0xcf, // CRC LOOKUP TABLE0x9c, 0x81, 0xa6, 0xbb,0xcd, 0xd0, 0xf7, 0xea,0xb9, 0xa4, 0x83, 0x9e, // 表生成规则:0x25, 0x38, 0x1f, 0x02,0x51, 0x4c, 0x6b, 0x76,0x87, 0x9a, 0xbd, 0xa0, // ---------------------------------------------------0xf3, 0xee, 0xc9, 0xd4,0x6f, 0x72, 0x55, 0x48,0x1b, 0x06, 0x21, 0x3c, // 宽度 WIDTH : 8 bits0x4a, 0x57, 0x70, 0x6d,0x3e, 0x23, 0x04, 0x19,0xa2, 0xbf, 0x98, 0x85, // 多项式 POLY : x^8 + x^4 + x^3 + x^2 + 10xd6, 0xcb, 0xec, 0xf1,0x13, 0x0e, 0x29, 0x34,0x67, 0x7a, 0x5d, 0x40, // 0x11d (1-0001-1101)0xfb, 0xe6, 0xc1, 0xdc,0x8f, 0x92, 0xb5, 0xa8,0xde, 0xc3, 0xe4, 0xf9, // [CRC8003]0xaa, 0xb7, 0x90, 0x8d,0x36, 0x2b, 0x0c, 0x11,0x42, 0x5f, 0x78, 0x65, // 初始值 INIT : 0x00x94, 0x89, 0xae, 0xb3,0xe0, 0xfd, 0xda, 0xc7,0x7c, 0x61, 0x46, 0x5b, // 结果异或值 XOROUT : 0x00x08, 0x15, 0x32, 0x2f,0x59, 0x44, 0x63, 0x7e,0x2d, 0x30, 0x17, 0x0a, // 输入数据反转 : false0xb1, 0xac, 0x8b, 0x96,0xc5, 0xd8, 0xff, 0xe2,0x26, 0x3b, 0x1c, 0x01, // 输出数据反转 : false0x52, 0x4f, 0x68, 0x75,0xce, 0xd3, 0xf4, 0xe9,0xba, 0xa7, 0x80, 0x9d,0xeb, 0xf6, 0xd1, 0xcc,0x9f, 0x82, 0xa5, 0xb8,0x03, 0x1e, 0x39, 0x24,0x77, 0x6a, 0x4d, 0x50,0xa1, 0xbc, 0x9b, 0x86,0xd5, 0xc8, 0xef, 0xf2,0x49, 0x54, 0x73, 0x6e,0x3d, 0x20, 0x07, 0x1a,0x6c, 0x71, 0x56, 0x4b,0x18, 0x05, 0x22, 0x3f,0x84, 0x99, 0xbe, 0xa3,0xf0, 0xed, 0xca, 0xd7,0x35, 0x28, 0x0f, 0x12,0x41, 0x5c, 0x7b, 0x66,0xdd, 0xc0, 0xe7, 0xfa,0xa9, 0xb4, 0x93, 0x8e,0xf8, 0xe5, 0xc2, 0xdf,0x8c, 0x91, 0xb6, 0xab,0x10, 0x0d, 0x2a, 0x37,0x64, 0x79, 0x5e, 0x43,0xb2, 0xaf, 0x88, 0x95,0xc6, 0xdb, 0xfc, 0xe1,0x5a, 0x47, 0x60, 0x7d,0x2e, 0x33, 0x14, 0x09,0x7f, 0x62, 0x45, 0x58,0x0b, 0x16, 0x31, 0x2c,0x97, 0x8a, 0xad, 0xb0,0xe3, 0xfe, 0xd9, 0xc4}; crc8 = initial_value; // crc 计算的初始值for (i = 0; i < d_length; i++) {crc8 = Crc8Table[crc8 ^ data[i]];} return crc8;
}
/****************************************************************************************************
报文发出回调函数
***************************************************************************************************/dword applILTxPending (long aId, dword aDlc, byte data[])
{dword i;byte crc8;if(aId == 0x322){data[6] = E2E_Counter(data,6); data[7] = E2E_CRC8_Table(data,7,0xff);}return 1; // don't prevent sending of the message
}
📙 理解基础:模2 运算
🍅 模2加减法(等同于异或操作)
- 简单记作: 同0异1
- 下图1±1 = 0, 写的时候笔误
🍅 模2乘法
- 要点: 中间累加计算时,采用 模2加法 ,也就是结果不进位
🍅 模2除法
-
模2除法 不借位减法 ,模2乘法不借位加法 (加法和减法一样,都是异或运算)
-
除数的首位肯定是1,这是规定,如果是0111,那除数就把0去掉,为111所以除数的首位肯定是1
-
余数先去掉首位,若此时余数最高位为1,商1,并对以它为除数继续模2除。 若最高位为0,则商0,重复步骤2。
-
直到余数位数小于除数位数时,运算结束,余数总比除数少一位
-
如下图: 1111000除以1101: 商为1011 ,余数为111
模2除法(CRC)循环冗余校验码在线计算器在线计算平台
- 模2除法(CRC)循环冗余校验码在线计算器在线计算平台
📙 理解基础:循环冗余校验
🍅 循环冗余校验简介
所谓循环冗余校验(CRC:Cyclic Redundancy Check)是一种错误检测算法,通常在通信协议中或存储设备中用于检测原始数据的意外变动。可以简单理解成对有用数据按照一定的算法进行计算后,提取出一个特征值,并附加在有用数据后。在应用中将有用数据按照特定的算法提取特征值与预先存储的特征值进行比对,如相等则校验通过,反之校验失败,从而识别出数据是否异常。
- 较为广泛的循环冗余校验技术
- 模2除法百度百科
🍅 为何要校验数据完整性(Data Integrity)?
- 数据在经过链路层、物理层、通信介质等,传输过程中有可能被干扰到,导致数据传输某些BIT错误
- 也有可能接收电路、发送电路、调制电路、解调电路都可能由于某些干扰原因导致工作失效而出现误码,所以数据传输要通过校验去确定数据是完整可靠的
- 循环冗余校验使用二进制除法作为算法原理,具有强大的错误检测机制,在通信领域被广泛使用
🍅 何为循环冗余校验?
- 这里有n位二进制数据需要被传输 比如 1111 ,根据CRC算法计算出m位冗余码,则实际传输或者存储的就是n+m位二进制数据。
- m位的冗余码 是多少,那这里引出一个概念:多项式,在CRC校验算法中多项式可做如下理解及表示
- 比如上面我们做
模2除法
用的例子,1101,那么他的多项式就是: - 根据CRC的规则 冗余码的位数要比 多项式的位数少一位 ,所以 m = 4 -1 =3
- 根据计算规则,要在要传输的数据后面,补上 m位 0 ,然后根据模2除法计算出 m位冗余码
- 所以 也就是上面的例子 被除数是 1111000 ,除数是 1101 ,则余数是111
📙 CRC的算法原理
🍅 CRC参数模型
前面都是理论基础,那么转换位程序语言该怎么描述和理解呢?
一个完整的CRC参数模型应该包含以下信息:WIDTH,POLY,INIT,REFIN,REFOUT,XOROUT。
-
NAME:参数模型名称。
-
WIDTH:宽度,即生成的CRC数据位宽,如CRC-8,生成的CRC为8位 ,比如我们上面测试用的1111000 模2除以1101 ,则宽度是4,因为后面3个0是模2运算加上去的。
-
POLY:十六进制多项式,省略最高位1,如 x8 + x2 + 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。
🍅 CRC8查表法,表怎么生成的?
- 下表列出了CRC8的生成参数,表的大小是256个字节,其实就是0-255(0x00- 0xFF) 这256个数的CRC校验值
byte Crc8Table[256] = {0x00, 0x1d, 0x3a, 0x27,0x74, 0x69, 0x4e, 0x53,0xe8, 0xf5, 0xd2, 0xcf, // CRC LOOKUP TABLE0x9c, 0x81, 0xa6, 0xbb,0xcd, 0xd0, 0xf7, 0xea,0xb9, 0xa4, 0x83, 0x9e, // 表生成规则:0x25, 0x38, 0x1f, 0x02,0x51, 0x4c, 0x6b, 0x76,0x87, 0x9a, 0xbd, 0xa0, // ---------------------------------------------------0xf3, 0xee, 0xc9, 0xd4,0x6f, 0x72, 0x55, 0x48,0x1b, 0x06, 0x21, 0x3c, // 宽度 WIDTH : 8 bits0x4a, 0x57, 0x70, 0x6d,0x3e, 0x23, 0x04, 0x19,0xa2, 0xbf, 0x98, 0x85, // 多项式 POLY : x^8 + x^4 + x^3 + x^2 + 10xd6, 0xcb, 0xec, 0xf1,0x13, 0x0e, 0x29, 0x34,0x67, 0x7a, 0x5d, 0x40, // 0x11d (1-0001-1101)0xfb, 0xe6, 0xc1, 0xdc,0x8f, 0x92, 0xb5, 0xa8,0xde, 0xc3, 0xe4, 0xf9, // [CRC8003]0xaa, 0xb7, 0x90, 0x8d,0x36, 0x2b, 0x0c, 0x11,0x42, 0x5f, 0x78, 0x65, // 初始值 INIT : 0x00x94, 0x89, 0xae, 0xb3,0xe0, 0xfd, 0xda, 0xc7,0x7c, 0x61, 0x46, 0x5b, // 结果异或值 XOROUT : 0x00x08, 0x15, 0x32, 0x2f,0x59, 0x44, 0x63, 0x7e,0x2d, 0x30, 0x17, 0x0a, // 输入数据反转 : false0xb1, 0xac, 0x8b, 0x96,0xc5, 0xd8, 0xff, 0xe2,0x26, 0x3b, 0x1c, 0x01, // 输出数据反转 : false0x52, 0x4f, 0x68, 0x75,0xce, 0xd3, 0xf4, 0xe9,0xba, 0xa7, 0x80, 0x9d,0xeb, 0xf6, 0xd1, 0xcc,0x9f, 0x82, 0xa5, 0xb8,0x03, 0x1e, 0x39, 0x24,0x77, 0x6a, 0x4d, 0x50,0xa1, 0xbc, 0x9b, 0x86,0xd5, 0xc8, 0xef, 0xf2,0x49, 0x54, 0x73, 0x6e,0x3d, 0x20, 0x07, 0x1a,0x6c, 0x71, 0x56, 0x4b,0x18, 0x05, 0x22, 0x3f,0x84, 0x99, 0xbe, 0xa3,0xf0, 0xed, 0xca, 0xd7,0x35, 0x28, 0x0f, 0x12,0x41, 0x5c, 0x7b, 0x66,0xdd, 0xc0, 0xe7, 0xfa,0xa9, 0xb4, 0x93, 0x8e,0xf8, 0xe5, 0xc2, 0xdf,0x8c, 0x91, 0xb6, 0xab,0x10, 0x0d, 0x2a, 0x37,0x64, 0x79, 0x5e, 0x43,0xb2, 0xaf, 0x88, 0x95,0xc6, 0xdb, 0xfc, 0xe1,0x5a, 0x47, 0x60, 0x7d,0x2e, 0x33, 0x14, 0x09,0x7f, 0x62, 0x45, 0x58,0x0b, 0x16, 0x31, 0x2c,0x97, 0x8a, 0xad, 0xb0,0xe3, 0xfe, 0xd9, 0xc4};
- 如上表 ,比如 数字0x8B的校验码是 0xE9 ,我们可以用 CRC(循环冗余校验)在线计算 计算看下:
- 模2除法 的完整运算测试结果,这里忽略商的值,因为我们要的是余数,看起来很长,只有自己参与运算之后,才能明白
- 当余数最高位是0的时候,是不需要参与运算的,可以直接借位(补0继续模2运算)
- 当余数最高位是1的时候,因为除数的最高位永远为1,所以,下个余数的最高位肯定是0,而0又是不需要参与运算,所以可以直接移一位后再进行模2运算
- 如果上面的能够理解了,那么简化后的运算如下图,遇到0直接后面补0就好了。
- 下面是VS 2019下的根据上面的CRC生成参数生成的表源代码
// PrintDeviceInfo.cpp : 定义控制台应用程序的入口点。
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <Windows.h>unsigned char crc8(unsigned char value)
{unsigned char i, crc;crc = value^0x00;/* 数据往左移了8位,需要计算8次 */for (i = 8; i > 0; --i){if (crc & 0x80) /* 判断最高位是否为1 */{crc = (crc << 1) ^ 0x1d;}else{/* 最高位为0时,不需要异或,整体数据往左移一位 */crc = (crc << 1);}}crc = crc ^ 0x00;return crc;
}int main(int argc, char* argv[])
{unsigned char retCRC;unsigned char testValue = 3;unsigned char Crc8Table[256];for(int i =0 ;i< 256 ;i++){Crc8Table[i] = crc8(i);printf("%5x ", Crc8Table[i]); if ((i+1) % 12 == 0)printf("\n");}getchar();return 0;
}
- 看下结果,是和上面的表内容一样的:
- 理解了模2运算的过程,和下面两句话,那么CRC8的算法核心也就自然明白了
- 当余数最高位是0的时候,是不需要参与运算的,可以直接借位(补0继续模2运算)
- 当余数最高位是1的时候,因为除数的最高位永远为1,所以,下个余数的最高位肯定是0,而0又是不需要参与运算,所以可以直接移一位后再进行模2运算
if (crc & 0x80) /* 判断最高位是否为1 */{crc = (crc << 1) ^ 0x1d;}else{/* 最高位为0时,不需要异或,整体数据往左移一位 */crc = (crc << 1);}
🍅 CRC8直接计算法
这个时候再看直接计算的算法,可能就好理解的多,对于在E2E保护中的CRC算法还是建议使用查表法的,因为报文发的很快,CRC校验的速度越快越好。
byte E2E_CRC8(byte data[],byte d_length, byte initial_value)
{int i, j;int crc8;const byte crc_poly = 0x1D;crc8 = initial_value; // crc 计算的初始值for (i = 0; i < d_length; i++){crc8 ^= data[i]; /* 每次先与需要计算的数据异或,计算完指向下一数据 */ for (j = 0; j < 8; j++) // 多项式宽度为8,所以需要计算8次{if (crc8 & 0x80)/* 判断最高位是否为1 */{crc8 = (crc8 << 1) ^ crc_poly;}else /* 最高位为0时,不需要异或,整体数据往左移一位 */{crc8 <<= 1;}}}return crc8;
}
End |
🌎总结
🍅 有需要演示中所用demo工程的,可以关注下方公众号网盘自取啦,感谢阅读。
- 🚩要有最朴素的生活,最遥远的梦想,即使明天天寒地冻,路遥马亡!
- 🚩 有微信的小伙伴可以关注下浪哥车载诊断,一个行业内小小圈子,群里有
网盘资料
,源码
,还有各路大神
闲时交流交流技术,聊聊工作机会啥的。
- 🚩如果这篇博客对你有帮助,请 “点赞” “评论”“收藏”一键三连 哦!码字不易,大家的支持就是我坚持下去的动力。