循环诊断算法

❶ CRC循环冗余校验算法

CRC循环冗余校验算法

CRC，全称Cyclic Rendancy Check，即循环冗余校验，是一种用于检查通信内容是否发生错误的算法。它通过除法运算得到的余数来检测数据的完整性。如果数据在传输过程中被干扰，使用相同的除数计算出来的余数会不同，从而可以判断数据是否发生了变化。

一、CRC校验的基本原理

CRC校验的原理与余数检查法类似。在CRC校验中：

• 被除数对应于需要CRC校验的数据。
• 除数对应于CRC算法的多项式。
• 余数对应于最后算出来的CRC校验码。

但是，CRC算法中的除法和普通的算术除法有所不同，它采用的是模2除法，得到的余数为模2余数。模2除法是一种不带借位和进位的二进制除法，其加减运算等同于异或运算。

二、有限域内的运算

为了理解模2除法和模2余数，需要了解有限域（Finite Field）内的加减乘除运算。在计算机中，数据以二进制形式表示，因此可以定义在0-1有限域内的运算。

• 加法（不带进位）：0+0=0，0+1=1，1+0=1，1+1=0（等同于异或运算）。
• 减法（不带借位）：与加法相同，因为不带借位的二进制减法也等同于异或运算。
• 乘法：0×0=0，0×1=0，1×0=0，1×1=1。
• 除法：在有限域内，除法可以简化为通过乘法逆元来计算，但通常我们更关注模2除法下的余数计算。

三、CRC算法参数

CRC算法包含五个主要参数：

1. Poly（Polynomial）：生成多项式，即模2除法的除数。这个多项式不是随意选择的，而是根据数据的位数、CRC长度和数据错误类型来设计的，以尽可能提高错误检测的概率。
2. Init（Initialization）：初始值，用于被检查数据减去（异或）的值。这个值可以在计算CRC之前对数据进行预处理。
3. RefIn（Reflect the bits in each byte of input）：输入翻转，指将被检查数据的输入方向翻转过来。
4. RefOut（Reflect the bits in each byte of output）：输出翻转，指将算出的CRC校验值翻转过来。
5. XorOut：异或输出，用于与最后算出的CRC校验值进行异或的值。这个值可以在输出CRC之前对校验值进行后处理。

四、CRC计算过程

1. 数据预处理：根据Init参数对数据进行异或运算，得到预处理后的数据。
2. 数据左移：将预处理后的数据左移与CRC长度相同的位数，为CRC校验码的放置留出空间。
3. 模2除法：使用生成多项式（Poly）对左移后的数据进行模2除法运算，得到余数作为CRC校验码。
4. CRC校验码处理：根据RefOut和XorOut参数对CRC校验码进行翻转和异或运算，得到最终的CRC校验码。

五、CRC校验过程

接收方收到数据后，将数据和CRC校验码整体作为被除数，再次使用相同的生成多项式进行模2除法运算。如果计算出的余数为0，则说明数据传输没有错误；如果余数不为0，则说明数据传输存在错误。

六、示例

以CRC-8算法为例，假设数据为0xAABB（1010 1010 1011 1011），生成多项式为0x07（对应x^8+x^2+x+1的省略形式），其他参数为默认值。

1. 数据预处理：由于Init为0x00，所以不进行预处理。
2. 数据左移：将0xAABB左移8位，得到0xAABB00。
3. 模2除法：使用0x07对0xAABB00进行模2除法运算，得到余数0xB2作为CRC校验码。
4. CRC校验码处理：由于RefOut和XorOut均为默认值False和0x00，所以不进行翻转和异或运算。

最终，发送方发送的数据为0xAABBB2（0xAABB00+0x0000B2），接收方对收到的0xAABBB2进行CRC-8计算，如果余数为0，则说明数据传输没有错误。

以上即为CRC循环冗余校验算法的基本介绍和计算过程。通过CRC校验，可以有效地检测数据传输过程中的错误，提高通信的可靠性。