点击注册
点击注册
.
@      棋牌资讯 CRC8和CRC16算法

你的位置:麻将游戏 > 棋牌资讯 >

棋牌资讯 CRC8和CRC16算法

​1 什么是CRC校验CRC8校验在整车通信系统中应用比较广泛,相当于以前XOR(异或)的升级版,今天介绍下CRC8的校验算法。当我们要发送报文信息时,为了避免传输过程的干扰,一般会在8字节的CAN报文中,增加Rolling counter和Checksum校验。Rolling counter 校验,即滚动计数,是为了发现丢帧和漏帧情况,原理很简单,就是从0-15滚动计数,当接收的Rolling counter 和自己计算的counter相等或相差2以上,那就可以判断帧未对齐,或有丢帧、漏帧现象。例如,Rolling counter代码可以这么写:if ( RollingCounter < 15) { RollingCounter ++; } else { RollingCounter = 0; }Checksum,校验和,是为了发现同一时刻是否有错帧的情况,可以有效地降低数据的错误率。而我们提到的CRC8校验算法,就是对一帧报文进行校验和计算的算法。参考CRC源码的同学,请关注【汽车控制与人工智能】微信公众号,后台回复【CRC】获取。2 CRC8的原理在发送节点,根据要传送的m位二进制码序列,以一定的规则(CRC校验有不同的规则,在差错控制理论中称为“生成多项式”)产生一个校验用的n位校验码(CRC码),附在原始报文中(一般在报文的最后位置),构成一个新的二进制码序列数共m+n位,然后发送出去。在接收节点,根据报文信息和CRC码之间遵循的规则(即与发送时生成CRC校验码相同的规则)进行检验,校验采用计算机的模二除法(即生成多项式)做异或运算,进行异或运算时除数和被除数最高位对齐,进行按位异或运算,若最终的数据能被除尽,则传输正确;否则,传输错误。CRC8即最终生成的CRC校验码为1字节,其生成多项式,生成多项式为g(x)=x^8+x^5+x^4+1,相当于g(x)=1·x^8+0·x^7+0·x^6+1·x^5+1·x^4+0·x^3+0·x^2+0·x^1+1·x^0,即对应的二进制数为100110001。CRC8标准生成多项式CRC-8:x^8+x^5+x^4+1 0x31 (0x131)CRC-8:x^8+x^2+x^1+1 0x07 (0x107)CRC-8:x^8+x^6+x^4+x^3+x^2+x^1 0x5E (0x15E)由于多项式的最高为都为1,并且在代码的CRC8计算中,最高位也是不使用的, 所以在多项式记录时都去掉了最高位。3 报文的编码格式计算CRC8之前,还得介绍下报文的编码格式。报文的编码格式分为Intel格式与Motorola格式,对应平时说的小端和大端。当然,这两种编码格式,没有任何优劣之分,完全是设计者的习惯问题。有了这两种编码形式,在解析报文前,要清楚具体是哪种编码格式就显得尤为重要了。CAN 报文发送顺序为:先发送低位字节LSB,最后发送高位字节MSB(定义Byte0为 LSB,Byte7为MSB)。CAN数据段中每个字节传输规则是:首先传输一个字节的高位MSB,后传输该字节的低位MSB。Intel(小端):低字节LSB在前,高字节MSB在后。Motorola(大端):高字节MSB在前,低字节LSB在后。当一个信号的数据长度不超过1个字节(8位)时,Intel与Motorola两种格式的编码结果完全一样:信号的高位(S_msb)将被放在该字节的高位,信号的低位(S_lsb)将被放在该字节的低位。当信号的数据长度超过1个字节(8位)时,两者的编码结果出现了明显的不同。Intel:该信号的高位(S_msb)将被放在高字节(MSB)的高位,信号的低位(S_lsb)将被放在低字节(LSB)的低位。这样,信号的起始位就是低字节的低位。Motorola:该信号的高位(S_msb)将被放在低字节(LSB)的高位,信号的低位(S_lsb)将被放在高字节(MSB)的低位。这样,信号的起始位就是高字节的低位。举个例子。比如,现在要传输车速信号,数据为0x1024。Motorola:​数据位 data[0] data[1]数据值 0x10 0x24data[0] = 0x1024 & 0x0FF00>> 8;data[1] = 0x1024 & 0x000FF;value = data[0]*256 + data[1];Intel​数据位 data[0] data[1]数据值 0x24 0x10data[0] = 0x1024 & 0x000FF;data[1] = 0x1024 & 0x0FF00 >> 8;value = data[0] + data[1]*256;4 CRC计算过程下面,我们以x^8+x^5+x^4+1(0x31,二进制为:100110001)多项式为例,计算一个字节:0x11(二进制为:00010001) 计算过程: 1. 需要计算的数据左移8位,移位后数据为:0001 0001 0000 000 2. 先进行高9位异或,0001 0001 0000 0000,因为高9bit的最高bit为0,不需要进行异或,同理,接下来的两bit也是0,也不需要进行进行异或。这样处理后数据为:1 0001 0000 0000;3. 接下来最高位为1,需要进行异或操作了。当多项式最高位为1,才进行异或计算,异或后最高位为0,下次也不需要异或,这样需要采用代码计算的方式,就可以把最高位去掉,不需要异或,最后结果也是一样的。 对于上面的计算过程,采用代码实现的方式如下:unsigned char crc_high_first(unsigned char ptr, unsigned char len) { unsigned char i; unsigned char crc=0x00;/ 计算的初始crc值 */ while(len--) { crc ^= *ptr++; /* 每次先与需要计算的数据异或,计算完指向下一数据 */ for (i=8; i>0; --i) /* 下面这段计算过程与计算一个字节crc一样 */ { if (crc & 0x80) crc = (crc << 1) ^ 0x31; else crc = (crc << 1); } } return (crc); }上面的CRC计算是纯采用逻辑运行的方式,可以看出运行量还是挺大的。每一个字节都需要进行8次判断、移位、异或操作。如果采用查表法,可以大大减少计算量,先计算出0x00~0xFF每一个字节的crc校验结果,然后通过表来查出每个字节的crc结果,大大减少计算量。下面是一个表生成程序:(生成表对应多项式:0x31(多项式:x^8+x^5+x^4+1,100110001))void create_crc_table(void) { unsigned short i; unsigned char j; for (i=0; i<=0xFF; i++) { if (0 == (i)) printf("\n"); j = i&0xFF; printf("0x%.2x, ", cal_table_high_first (j)); /*依次计算每个字节的crc校验值*/ } }得到的表整理后如下:static const unsigned char crc_table[] = { 0x00,0x31,0x62,0x53,0xc4,0xf5,0xa6,0x97,0xb9,0x88,0xdb,0xea,0x7d,0x4c,0x1f,0x2e,0x43,0x72,0x21,0x10,0x87,0xb6,0xe5,0xd4,0xfa,0xcb,0x98,0xa9,0x3e,0x0f,0x5c,0x6d,0x86,0xb7,0xe4,0xd5,0x42,0x73,0x20,0x11,0x3f,0x0e,0x5d,0x6c,0xfb,0xca,0x99,0xa8,0xc5,0xf4,0xa7,0x96,0x01,0x30,0x63,0x52,0x7c,0x4d,0x1e,0x2f,0xb8,0x89,0xda,0xeb,0x3d,0x0c,0x5f,0x6e,0xf9,0xc8,0x9b,0xaa,0x84,0xb5,0xe6,0xd7,0x40,0x71,0x22,0x13,0x7e,0x4f,0x1c,0x2d,0xba,0x8b,0xd8,0xe9,0xc7,0xf6,0xa5,0x94,0x03,0x32,0x61,0x50,0xbb,0x8a,0xd9,0xe8,0x7f,0x4e,0x1d,0x2c,0x02,0x33,0x60,0x51,0xc6,0xf7,0xa4,0x95,0xf8,0xc9,0x9a,0xab,0x3c,0x0d,0x5e,0x6f,0x41,0x70,0x23,0x12,0x85,0xb4,0xe7,0xd6,0x7a,0x4b,0x18,0x29,0xbe,0x8f,0xdc,0xed,0xc3,0xf2,0xa1,0x90,0x07,0x36,0x65,0x54,0x39,0x08,0x5b,0x6a,0xfd,0xcc,0x9f,0xae,0x80,0xb1,0xe2,0xd3,0x44,0x75,0x26,0x17,0xfc,0xcd,0x9e,0xaf,0x38,0x09,0x5a,0x6b,0x45,0x74,0x27,0x16,0x81,0xb0,0xe3,0xd2,0xbf,0x8e,0xdd,0xec,0x7b,0x4a,0x19,0x28,0x06,0x37,0x64,0x55,0xc2,0xf3,0xa0,0x91,0x47,0x76,0x25,0x14,0x83,0xb2,0xe1,0xd0,0xfe,0xcf,0x9c,0xad,0x3a,0x0b,0x58,0x69,0x04,0x35,0x66,0x57,0xc0,0xf1,0xa2,0x93,0xbd,0x8c,0xdf,0xee,0x79,0x48,0x1b,0x2a,0xc1,0xf0,0xa3,0x92,0x05,0x34,0x67,0x56,0x78,0x49,0x1a,0x2b,0xbc,0x8d,0xde,0xef,0x82,0xb3,0xe0,0xd1,0x46,0x77,0x24,0x15,0x3b,0x0a,0x59,0x68,0xff,0xce,0x9d,0xac };采用查表法计算crc代码如下:unsigned char cal_crc_table(unsigned char *ptr, unsigned char len) { unsigned char crc = 0x00; while (len--) { crc = crc_table[crc ^ *ptr++]; } return (crc); }小端异或的计算小端异或与大端异或差异在数据先判断最低位,并且数据是向右移的,并且多项式数据位需要高低位反转一下。仍以多项式:x^8+x^5+x^4+1为例:则计算一个字节的CRC校验代码如下:unsigned char cal_table_low_first(unsigned char value) { unsigned char i, crc; crc = value; /* 同样需要计算8次 */ for (i=8; i>0; --i) { if (crc & 0x01) /* 反序异或变成判断最低位是否为1 */ /* 数据变成往右移位了 */ /* 计算的多项式从0x31(0011 0001)变成了0x8C (1000 1100) */ /* 多项式值,原来的最高位变成了最低位,原来的最低位变成最高位,8位数据高低位交换一下位置 */ crc = (crc >> 1) ^ 0x8C; else crc = (crc >> 1); } return crc; }多字节的CRC校验及CRC数据表的生成,只要把单字节的计算方式替换一下大端计算方式即可,这里不再列出。所以,只要明确了CRC校验使用的多项式,高位先校验还是低位先校验,计算CRC的初始值是什么,那CRC的计算就变得很简单了。5 CRC16计算除了CRC8校验外,还有CRC16,CRC32,再说下以下几种常见的CRC16标准,被用在各个规范中,算法原理基本一致,就是在数据的输入和输出有所差异,下将把这些标准的差异列出。CRC16_CCITT:多项式x^16+x^12+x^5+1(0x1021),初始值0x0000,低位在前,高位在后,结果与0x0000异或;CRC16_CCITT_FALSE:多项式x^16+x^12+x^5+1(0x1021),初始值0xFFFF,低位在后,高位在前,结果与0x0000异或;CRC16_XMODEM:多项式x^16+x^12+x^5+1(0x1021),初始值0x0000,低位在后,高位在前,结果与0x0000异或;CRC16_X25:多项式x^16+x^12+x^5+1(0x1021),初始值0x0000,低位在前,高位在后,结果与0xFFFF异或;CRC16_MODBUS:多项式x^16+x^15+x^2+1(0x8005),初始值0xFFFF,低位在前,高位在后,结果与0x0000异或;CRC16_IBM:多项式x^16+x^15+x^2+1(0x8005),初始值0x0000,低位在前,高位在后,结果与0x0000异或;CRC16_MAXIM:多项式x^16+x^15+x^2+1(0x8005),初始值0x0000,低位在前,高位在后,结果与0xFFFF异或;CRC16_USB:多项式x^16+x^15+x^2+1(0x8005),初始值0xFFFF,低位在前,高位在后,结果与0xFFFF异或;CRC16的算法原理:1. 根据CRC16的标准选择初值CRCIn的值;2. 将数据的第一个字节与CRCIn高8位异或;3. 判断最高位,若该位为 0 左移一位,若为 1 左移一位再与多项式Hex码异或;4. 重复3直至8位全部移位计算结束;5. 重复将所有输入数据操作完成以上步骤,所得16位数即16位CRC校验码。参考CRC源码的同学,请关注微信公众号【汽车控制与人工智能】后台回复【CRC】获取。

如果说没有确定明确的目标,那么不妨试试投石问路,以自摸为主棋牌资讯,然后舍闲张试探情况,最后确定所和牌型。其实,在牌型较差的情况下,我们可以通过摸牌来改变牌型整体结构棋牌资讯,拟定可靠的和牌方向,使对手减少你的阻截。