之前在做学校项目的时候用到了CRC 原理，但在网上查找的过程中，发现讲解CRC知识的资源很多，但是对新手比较友好的、讲的十分清楚的又很少，很多资料也不完善，读起来心中常常不由自主地…
之前在做学校项目的时候用到了CRC 原理，但在网上查找的过程中，发现讲解CRC知识的资源很多，但是对新手比较友好的、讲的十分清楚的又很少，很多资料也不完善，读起来心中常常不由自主地奔腾过上千个“为什么”“为什么”， 本文尽可能的对新手友好、解答CRC里面的一些知识点，而不是简单的应用。
依据学习目的不同，如果大家只想简单应用，不求原理，那么直接复制–粘贴最后的代码即可。
1. CRC 算法原理
在对信息的处理过程中，我们可以将要被处理的数据块M看成一个n阶的二进制多项式，其形式如下：
CRC校验就是基于这种多项式进行的运算，以GF(2)(The integers modulo 2)多项式算术为数学基础，即
(模-2)除法
的余数运算（其实说白了就是异或Xor（见2.2）），使用的除数不同，CRC的类型也就不一样。CRC传输实际上就是在长度为 k 的数据后面添加供差错检测(Frame Check Sequence) 用的 r 位冗余码（Redundant code 没错CRC里面的R就是这个），使原数据构成 n = k + r 位并发送出去, 此方式又叫（n, k）码。可以证明存在一个最高次幂为n-k=r的多项式G(x), 根据G(x)可以生成k位信息的校验码，而 G(x) 叫做这个CRC码的生成多项式( Poly )。而根据 k 值的不同，就形成了不同的CRC码的生成多项式，以下为各种常用的多项表达式：
这些多项表达式的值便是(模-2)除法的除数，本博客这里选取CRC-32多项式（即为对应除数）格式，通过取余做操，获取CRC检验码。
2. CRC 传输过程
2.1 传输原理
按 1. CRC 算法原理 所述，将长度为 k 位的数据块对应一个GF(2)多项式M，以 8 位数据块11100110举例，如果先传输MSB（Most Significant Bit），则它对应的多项式为x^7 + x^6 + x^5 + x^2 + x （8位对应x的7次幂，因为从x0 开始计数，2进制为1时有效）。发送端和接收端约定一个次数为 r 的CRC多项式，取CRC-4 为例：x^4 + x + 1，r = 4。在数据块后面加上r个0对应的多项式为M’，显然有M’ = Mx^r 。用 M’ 除以CRC-4 将得到一个次数等于或小于 r-1 的余数多项式 R，其对应的 r 位数值则为校验码。发送方通过指定的CRC多项式产生r位的CRC校验码，接收方则通过该CRC多项式来验证收到的报文码的CRC校验码是否为0。
假设发送信息用信息多项式C(x)表示，将C(x)左移 r 位，则可表示成C(x)x^r，这样C(x)的右边就会空出r位校验码的位置，使用GF(2)
（模2除法），得到的余数R就是校验码。发送的CRC编码是
, 至于验证接收到的报文编码是否至正确，方法依然是做模2除：
，若余数为0则正确。
2.2 逻辑异或运算
CRC校验是基于多项式进行的运算，其加减法运算以2为模GF(2) ，加减时不进（借）位，实际上与逻辑异或（XOR）运算是一致, XOR是将参加运算的两个数据，按二进制位进行“异或”运算。
异或运算规则（^）规则如下：
0^0=0； 0^1=1； 1^0=1； 1^1=0；
即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。
2.3 传输计算示例
以G(X)=X4+X3+1为例，设原数据为10110011。
（1）G(X)=X4+X3+1, 二进制比特串为11001。（在 X 的n 次方不为0处2的n次方的位=1 )
（2）因为校验码4位，所以10110011后面需加4个0，得到101100110000，用“模2除法” (即逻辑亦或^) 即可得出结果：
（3）即CRC^101100110000得到101100110100，并发送到接收端。
（4）接收端收到101100110100后除以11001(以“模2除法”方式去除),余数为0则无差错。
3. CRC 的实现（Reversed 反向校验模式）
一般来说CRC有多种实现方式，在本文中我们以C语言为例，并给出 直接生成法 和 查表法 两个例子。
直接生成法 适用于 CRC 次幂较小的格式，当CRC 次幂逐渐增高时，因为其复杂的Xor 逻辑运算会拖累系统运行速度，不再建议使用直接生成法，取而代之的是查表法——将数据块M 的一部分提前运算好，并将结果存入数组中，系统开始执行运算时，相当于省去了之前的操作，直接从类似中间的位置开始计算，所以会提高效率。
在计算CRC时也可以选择正向校验（Normal） 或者反向校验（Reversed），由于 Normal 和 Reversed 是镜像关系，两种方法会影响到最后的校验码，使得两种方式最后得到的校验码呈现镜像关系。但这对CRC 本身的成功率并没有影响，只不过是：正向走一遍，还是镜像走一遍罢了。
那为什么还会有Reversed格式呢？是因为在大多数硬件系统的传输中，普遍先发送LSB，而Reversed 的CRC 正是满足于这种LSB First 的格式，因此适用。
设数据块为Mx, CRC校验式为G(x) FCS位数为 r。
如下表所示，当采取反向校验设计时, 需进行以下操作：
|
|
Polynomial Representations
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
（1）将翻转后的Mx^r的后r位放入一个长度为r的寄存器中；
（2）如果寄存器的首位为1，将寄存器右移1位(将Mx^r剩下部分的MSB移入寄存器的MSB（高八位）)，再与G(x) 的后r位异或，否则仅将寄存器右移1位(将Mx^r剩下部分的LSB（低八位）移入寄存器的LSB)；
（3）重复第2步，直到M全部 Mx^r 移入寄存器；
unsigned int CRC;//int的大小是32位，作32位CRC寄存器
unsigned int CRC_32_Table[256];//用来保存CRC码表
void GenerateCRC32_Table()
{
for(int i=0;i<256;++i)//用++i以提高效率
{ CRC=i;
for(int j=0;j<8;++j)
{
if(CRC&1)// LSM为1
CRC=(CRC>>1)^0xEDB88320;//采取反向校验
else //0xEDB88320就是CRC-32多项表达式的reversed值
CRC>>=1;
}
CRC_32_Table[i]=CRC;
}
}
4. 生成多项式的选择
不同的CRC生成多项式，其检错能力是不同的。要使用R位校验码，生成多项式的次幂应为R。同时生成多项式应该包含项“1”，否则校验码的LSB(Least Significant Bit)将始终为0。如果数据块M (包括校验码) 在传输过程中产生了差错，则接收端收到的消息可以表示为M +R’。若R’ 不能被CRC 生成多项式G 除尽，则该差错可以被检测出。考虑以下几种情况：
1) 1位差错，即R’ = x^n = 100…00，n >= 0。只要G至少有2位1，R’就不能被G除尽。这是因为G x^k相当于将G左移k位，对任意多项式Q，QG相当于将多个不同的G的左移相加。如果G至少有两位1，它的多个不同的左移相加结果至少有两位1。
2)奇数位差错，只要G含有因子F = x + 1, R’ 就不能被G除尽。这是因为QG = Q’F，由1)的分析，F的多个不同的左移相加结果1的位数必然是偶数。
3)爆炸性差错，即R’ = (x^n + … + 1)x^m = 1…100…00，n >= 1，m >= 0，显然只要G包含项“1”，且次数大于n，就不能除尽R’。
4)2位差错，即R’ = (x^n + 1)x^m = 100…00100…00，n >= 0。设x^n + 1 = QG + R，则R’ = QGx^m + Rx^m，由3)可知R’能被G除尽当且仅当R为0。因此只需分析x^n + 1，对于次数R，总存在一个生成多项式G，使得n最小为2^R – 1时，才能除尽x^n + 1。称该生成多项式是原始的(primitive)，它提供了在该次数上检测2位差错的最高能力，因为当n = 2^R – 1时，x^n + 1能被任何R次多项式除尽。
5. Q & A
Q: 为什么寄存器初始化置0？
A: 寄存器的初始值不为 0，那么寄存器中的值就相当于是待测数据，这样算出的 CRC 结果并不正确。再考虑CRC32 模型的 Init=0xFFFFFFFF，待测数据的内容和长度为随机，如果寄存器初始值为 0，那么待测字节则为 1 字节 0x00，计算出来的 CRC32 值也就为 0。寄存器用0xFFFFFFFF 进行初始化，就可以避免这个问题
Q：为什么先移位再XOR？
A: 0xEDB88320已经是Gx 去掉最高项的简写，为了确保运算无误，所以需要先移位再XOR。这不会影响最后的结果，因为在做XOR运算时，gx 的最高位都会被消掉（因为在除法运算中每次循环都是从1 开始除， 而gx 的最高项就是1，所以每次都会被消掉）
Q: 查表法的index 是什么，而内容又是什么？
A: Index 为数据块M 的前8位，内容是前8位与CRC XOR后的值，用时需再与gx异或。
Q: 查表法为什么会有256个字符？
A: 在CRC-16和32中，一次移出的待测数据为 8 位 bits，即一次进行一个字节的计算，则表格有 2^8＝256 个表值。一个字节有8位二进制数，每一位都有2种选择。
文章整理自网络
关注微信公众号『玩转嵌入式』，后台回复“128”获取干货资料汇总，回复“256”加入技术交流群。
|
|
|
｜单片机编程如何查看版本之间代码的不同：代码比较工具
|
|
|
|
|
免责声明：本文内容由21ic获得授权后发布，版权归原作者所有，本平台仅提供信息存储服务。文章仅代表作者个人观点，不代表本平台立场，如有问题，请联系我们，谢谢！
Fatal error: Can't use function return value in write context in
/www/wwwroot/www.qianrushi.com.cn/wp-content/themes/news/footer.php on line
115
soufei
