国外ui设计网站,济宁网站建设 智雅,orion 响应式单页 wordpress主题,保险公司招聘网站1. CRC简介
循环冗余校验#xff08;英语#xff1a;Cyclic redundancy check#xff0c;简称CRC#xff09;#xff0c;由 W. Wesley Peterson 于 1961 年首次提出的一种纠错码理论。
CRC是一种数据纠错方法#xff0c;主要应用于数据通信或者数据存储的场合#xff…1. CRC简介
循环冗余校验英语Cyclic redundancy check简称CRC由 W. Wesley Peterson 于 1961 年首次提出的一种纠错码理论。
CRC是一种数据纠错方法主要应用于数据通信或者数据存储的场合用来检测或校验数据传输或者数据存储后可能出现的错误特别是擅长检测由传输通道中的噪声引起的常见错误。
CRC是数据通信领域中最流行的一种错误检测方法传输过程中的数据信息字段长度以及校验码的字段长度可以任意自定义的指定但是通信双方必须使用同一标准的CRC校验。
2. CRC模型及其相关概念
很多大佬们在研究CRC算法的时候设计了各种CRC的算法模型这些模型可以适用不同的校验场合比如 CRC-16 CRC-32 等不同的算法模型。
一般我们在具体的项目中要使用CRC校验的时候首先就要选择合适的算法模型根据选定的CRC算法模型才能计算得到对应的CRC校验码。然后通信双方约定好使用的CRC校验模型才能保证校验的一致性。
下图截图自一个CRC校验码在线计算工具网站的常用的CRC算法模型 注上面的多项式表示中是16进制数而且是省略了最高位的。
这些CRC算法模型中有几个重要的组成部分或者说计算CRC校验码时需要知道的一些概念如多项式公式、16进制多项式、宽度、初始值、结果异或值等等。
2.1 多项式公式
多项式公式是CRC校验中最重要的一个概念。
对任意的二进制数都可以构造一个与其对应的二进制系数多项式公式。
比如二进制10011b它对应的二进制系数多项式就是 P ( x ) x 4 x 1 P(x) x^4 x 1 P(x)x4x1
这个公式怎么来的呢
# 二进制数 1 0 0 1 1
# 下标 4 3 2 1 0
# 二进制多项式 1 * X4 0 * X3 0 * X2 1 * X1 1 * X0# 所以最后得出的多项式公式就是X4 X 1成为多项式要满足的条件
最高位和最低位都必须是1当数据在传输过程中出错时CRC的校验码不应该是0也就是要有余数该多项式要有最大的错误检测能力
2.2 16进制的多项式表示
一般在计算CRC校验码的时候我们习惯使用16进制的多项式这个16进制的多项式是被省略了最高位 1 的。
因为前面说了多项式的最高位和最低位都必须是1所以一般都会把这个多项式的最高位给省略掉这里我也没搞懂反正当它是一个不可描述的规定吧。
比如前面介绍的P(x) X4 X 1 这个多项式公式他对应的CRC模型就是 CRC-4/ITU 然后它的多项式使用16进制表示就是 0x03 本来这个多项式应该是0x13的但是省略了最高位所以变成了 0x03.
2.3 位宽
位宽指的就是CRC校验码的二进制位数。这个是和你选择的CRC模型有关的你选择不同的CRC模型那么CRC的多项式公式就不一样所以对应的CRC校验码数据位宽也不一样。
比如前面介绍的多项式公式 P(x) X4 X 1 那么CRC的校验码位宽就是 4 个二进制位数。因为多项式的最高位为4.
2.4 CRC变体相关的概念
前面介绍的3个参数概念是CRC模型中必须要有的概念。其他一些概念比如初始值、输入数据反转输出数据反转结果值是否异或处理等这些都属于CRC变体的处理。
如果没有特意规定的话那么这些参数默认都是没有的比如初始值没有规定则默认为0。没有说明是否反转那么一般不会对数据进行反转的操作等。
2.4.1 初始值
CRC模型中有些模型规定CRC的初始值不是0。这个初始值其实就是CRC校验码的计算过程中在第一次进行异或计算时是否有一个初始值。这个如果看C言语实现CRC计算过程就比较直观。
初始值的数据位宽和CRC校验码的位宽是一样的。
2.4.2 输出结果值异或
计算得到了CRC校验码后如果规定了输出的结果值要进行异或的数不为0那么最后得到CRC校验码时还得进行结果值异或这步操作。这样才能最终得到CRC校验码
2.4.3 输入输出值反转
在一些CRC模型中还会规定输入值与输出值是否反转。
输入值反转就是在计算CRC校验码之前是否对原始数据待测数据进行按位反转。比如1010001反转之后就是1000101
输出值反转就是最终得到的CRC结果值是否进行反转操作。
3. 模2运算
CRC校验的计算理论源自多项式除法它是一种二进制除法被叫做模2除法。待检测的数据除以多项式最终得到的余数就是CRC检验码。
模2运算是一种二进制运算是二进制编码理论中的运算基础。这种运算和我们以前学的四则运算的规则不同模2运算不考虑进位、借位这些规则它有着新的运算规则。
模2运算也有加减乘除下面是它们的运算示例。
3.1 模2加法
加法规则110 000 101 011 1 0 1 01 1 0 0
-----------0 1 1 03.2 模2减法
减法规则0-00 1-10 0-11 1-01 1 0 1 0
- 1 1 0 0
-----------0 1 1 03.3 模2乘法
乘法规则0×00 0×10 1×00 1×11
模2乘法与普通的乘法一样的演算规则只不过在按位相加时是按照模2加法规则进行的。 1 0 1 1x 1 0 1----------------1 0 1 10 0 0 01 0 1 1----------------1 0 0 1 1 13.4 模2除法
除法规则0÷10 1÷11
模2除法与普通的除法也是一样的演算规则但是就是在按位相减时是按照模2减法规则进行的。 1 1 1 0 (商)|-----------------
1 0 1 1 | 1 1 0 0 1 0 0 (被除数)1 0 1 1-----------------0 1 1 1 11 0 1 1-----------------0 1 0 0 01 0 1 1-----------------0 0 1 1 0 (最后余数)从上面的模2运算示例可以看出一些规律
模2的加减法运算结果是一样的他和C语言的异或运算有着一样的规则。所以我们软件实现这个算法时就是使用异或实现的。模2的乘除法运算与普通的运算有着类似的演算规则。但是在乘法时乘积相加除法时余数和除数相减就需要安装模2加减法规则运算。当余数的位数小于除数时模2除法停止运算当被除数或者在除法进行过程中得到的部分余数它们与除数位数一样多那么商1否则商0.
4. CRC校验码的计算和检测原理
4.1 CRC校验码的计算
CRC校验码的计算其实就是模2除法的运算过程。
在计算过程中我们首先要知道二进制多项式这个多项式其实就是除数而待校验的数据就是被除数最终进行模2除法运算得到的余数就是CRC校验码。
下面以多项式 P(x) x^4 x 1 为例该多项式对应的二进制数就是10011 进行计算演示。
第一步原始数据补充 n 个 0
假设要进行编码的原始数据为1100110而前面约定好了的多项式的最高位是4所以CRC校验码的位宽就是4。所以我们先假设余数是 0000 四个0补充在原始数据的后面那么最终参与计算的数就是11001100000
第二步进行模2除法运算
1 1 0 0 1 1 0 0 0 0 0 原始数据后面加了4个01 0 0 1 1 多项式
----------------------------------0 1 0 1 0 11 0 0 1 1
----------------------------------0 0 1 1 0 0 01 0 0 1 1
----------------------------------0 1 0 1 1 01 0 0 1 1
----------------------------------0 0 1 0 1 0 01 0 0 1 1
----------------------------------0 0 1 1 1当最终计算得到的余数的位数小于多项式的位数的时候运算停止然后得到的余数就是CRC的校验码。
在数据传输过程中就会把这个校验码放到原始数据的后面组成一个新的数11001100111 发送给接收方。当接收方在接收到这个数据后就会进行CRC校验也就是除以约定好的多项式如果最终的余数为0那么说明接收方接收的数据正确。
4.2 CRC校验检测原理
上面介绍计算CRC校验码说了我们首先要约定好收发双方的除数这个除数其实就是多项式。进行校验检测的大概过程就是
(1) 先约定好收发双方选择的CRC多项式 多项式这个多项式其实就是计算过程中的除数。
(2) 在待校验的数据可看作是发送方的数据后面加上 n 个0这个 n 是多少取决于你所选择的多 项式。比如你选择的多项式是P(x) x^4 x 1 。那么CRC检验码的位宽就是4也就是说你要补4个0
(3) 对待校验数据进行模2除法运算得出的余数就是CRC校验值。
(4) 然后把CRC检验码添加到待检验数据的末尾。这样就组成了一个新的数了这个是是添加了CRC校验码的。然后把这个新的数发送给接收方。
(5) 接收方把接收到的数据也进行模2除法的计算过程如果余数为0那么接收正确如果不为0那么数据在传输过程中出错。
5. CRC校验的软件代码
我们前面一直说了CRC校验码的计算其实就是模2除法。然后模2除法对应到C言语中来那就可以通过异或和移位操作来实现。
所以CRC算法的软件实现主要就是异或和移位操作实现的。实现方法主要有两种 按位校验和查表。按位校验法消耗更多的CPU算力查表法则消耗更多的RAM空间。
不同的CRC模型按位校验法有不同的算法实现主要是CRC变体的处理初始值的不同等。不过也是有相似的规律大致的代码实现过程是相同的。
网上也有大佬们已经实现了的各种CRC模型的算法库我这里给出一个网上比较全的CRC算法库如果有我们需要软件实现CRC校验的话可以去移植过来。
LibCRC官网https://www.libcrc.org/
LibCRC github仓库https://github.com/lammertb/libcrc
还有下面这个主要是按位校验法实现的CRC代码库
https://github.com/whik/crc-lib-c
5.1 软件实现的代码片段
下面是摘抄自 wiki 的其中一种按位校验方式实现的CRC算法大致的代码思路如下
function crc(byte array string[1..len], int len)
{remainderPolynomial : 0 // 多项式的初始值// 这里有一个流行的变体对剩余多项式进行补充比如输入数据是否进行反转for i from 1 to len{// 这个步骤要看不同的CRC模型有不同的处理。n是CRC的位宽如果小于8的位宽不用移位remainderPolynomial : remainderPolynomial xor (string[i] * (n 8))for j from 1 to 8 { // 每个字节是 8 bitif (remainderPolynomial最高位为1){remainderPolynomial : (remainderPolynomial 1) xor generatorPolynomial(多项式)}else {remainderPolynomial : (remainderPolynomial 1)}}}// 这里有一个流行的变体对剩余多项式进行补充比如是否对CRC校验码进行输出反转进行异或处理return remainderPolynomial
}基本上按位校验法的CRC代码实现就是上面的这个套路。
5.2 CRC32-MPEG-2 模型的代码实现
这里给出一个 CRC32-MPEG-2 这个模型的CRC代码实现。
uint32_t crc32_mpeg2(uint8_t data[], uint32_t length)
{uint32_t crc 0xffffffff;for (int i 0; i length; i){crc crc ^ (data[i] 24);for (int j 0; j 8; j){if ( crc 0x80000000 ){crc (crc 1) ^ 0x04C11DB7;}else{crc crc 1;}}}return crc;
}上面这个模型其实也是一些MCU硬件的CRC实现的模型比如STM32、APM32的MCU。
6. STM32的CRC外设使用
STM32 的 CRC 外设使用的算法模型是 CRC32-MPEG-2 。
STM32 CRC 的数据位宽为 32 位十六进制多项式为 0x4C11DB7 INIT0xFFFFFFFF, REFINfalseREFOUTfalse XOROUT0x00000000
对于 STM32 CRC外设的使用也很简单在使能了CRC外设时钟之后就可以调用SDK我使用的是STM32的标准固件库函数提供的CRC计算函数然后就可以得到对应数据的CRC校验码了。
下面以 STM32F407 为例使用CRC外设计算校验码的代码
static uint32_t CRC_Test_Buff[2] {0x01, 0x02};int main(void)
{uint32_t uCRCValue 0;/* Enable CRC Periph clock */RCC_AHB1PeriphClockCmd(RCC_AHB1Periph_CRC, ENABLE);/* Resets the CRC Data register */CRC_ResetDR();/* Calculate the 32-bit CRC value */uCRCValue CRC_CalcBlockCRC(CRC_Test_Buff, sizeof(CRC_Test_Buff) / 4);printf(CalculateBlockCRC 0x%08X \r\n, uCRCValue);while (1){}
}其中要注意的是CRC_CalcBlockCRC 这个函数提供的输入数据类型是 32 位 的。
运行上面的代码输出结果如下 然后我们到CRC校验码的在线计算工具验证下我们使用STM32 CRC外设计算得到的校验码是否一致。计算结果如下图 我们要选择的参数模型是 CRC32-MPEG-2 这个输入的数据类型要注意一下是16进制而且是1个字节。这个和我们STM32的代码是4个字节的数据不同要自己拆分为1个字节输入到那个框框里面。
然后最终的计算结果是0x298BE7BA 这个值和我们使用 STM32 外设计算出来的结果是一致的。
