C 语言 CRC 程序

在数据传输过程中，可能会出现噪声干扰，导致发送方到接收方的数据数字信号发生变化。因此，发送方提供的数据可能与接收方接收到的数据不匹配。我们将数据位的变化称为错误，为了避免这种情况，使用各种错误检测技术来检查接收到的数据。循环冗余校验（CRC）算法就是其中一种。

范围

• 本文将通过示例解释循环冗余校验（CRC）算法的基本原理。
• 提供了两种不同的方法来实现CRC程序。
• 阐述了两种不同的C语言CRC程序实现方法，以及它们各自的算法和时间复杂度。

引言

循环冗余校验（CRC）算法用于检测错误并验证发送方发送的数据的准确性。除了需要传输的数据外，CRC还需要一个生成多项式来通过二进制除法计算校验值。为了确保数据的真实性，校验值或CRC会与数据一起发送给接收方。

可以使用多项式的次数来表示将要传输给接收方的数据，以多项式形式表示。例如，长度为7的二进制数据1010101可以表示为：

x7+x5+x3+1

由于该表示形式的值为0，因此不表示位值0。

生成多项式也可以用二进制数据表示。数据多项式的次数必须小于生成多项式的次数，并且必须大于0。根据生成多项式的次数，CRC可以分为多种标准。CRC-8标准使用次数为8的生成多项式，CRC-16标准使用次数为16的生成多项式。这是一个简单的生成多项式示例。

x5+x4+x2

需要注意的是，循环冗余校验（CRC）也可以用作哈希函数。然而，由于CRC-8只能产生256（2^8）种不同的值。

CRC的步骤如下：发送方：

• 准备好长度为l的生成多项式和长度为n的数据。
• 在要传输的数据末尾附加(l-1)个零。
• 以生成多项式的二进制形式作为除数，以数据作为被除数进行二进制除法。校验值是二进制除法的余数。
• 将校验值附加到数据末尾，然后发送信号。

校验值，即CRC，用数学公式表示为：

在此n指的是生成多项式的位数。接收方：

• 再次使用二进制运算对接收到的数据进行除法，以数据作为被除数，以生成多项式的二进制形式作为除数。
• 如果二进制除法的余数为零，则表示发送方发送的数据没有错误。如果余数不等于零，则表示信号已被错误污染。

二进制除法的步骤与常规多项式除法相同，如下所示：

• 在除法的每一步，必须对被除数和除数进行XOR运算。只使用除数的前n位，其中n是当前被除数的位数。
• 根据n位数据，商要么是1，要么是0。商由数据的最后一位确定。如果最后一位是1，则商为1；如果是0，则商为0。
• 在上述操作得到余数后，从数据中提取第n+1位并将其附加。该余数部分用作下一个操作的除数。
• 该过程重复进行，直到所有数据位都用于计算为止。

循环冗余校验（CRC）的一个有趣特性是以下过程：CRC(x^y^z) == crc(x)^ crc(y)^ crc(z)。

符号^表示XOR运算。如果我们对三段数据进行XOR运算，然后再对结果进行CRC计算，那么CRC结果将与分别对每段数据进行CRC计算然后对结果进行XOR运算相同。

注意：当两个输入相同时，XOR运算符返回0；而在所有其他情况下，它返回1。

C语言CRC实现

CRC程序可以在C语言中使用两种方法实现。第一种方法使用字符数组，第二种方法使用位操作策略。

算法

CRC程序的实现算法如下：

• 获取数据和生成多项式。
• 令n表示生成多项式的长度。
• 在数据后附加n-1个零。
• 调用CRC函数。

CRC函数的算法如下：

• 获取数据的前n位。
• 如果第一位是1，则将生成多项式与数据的前n位进行XOR运算。
• 向左移动一位以保留第一位。
• 附加数据的一小部分。继续此过程，直到所有数据位都已插入。

XOR函数所用的方法基于以下XOR运算符的真值表：

• 当第一位和第二位相同时，结果为0。
• 如果位不同，则结果为1，否则为0。

以下是接收方用于错误检查的算法：

• 对新接收到的数据执行循环冗余校验（CRC），以识别剩余数据。
• 迭代条件是余数不得包含1，并且其长度必须小于生成多项式。
• 如果我们迭代完所有项目，就可以确定没有错误；否则，则存在错误。
• 为了确定字符数组的大小，请使用strlen()函数。要使用此函数，必须包含string.h头文件。

代码

输出

Enter data to be transmitted: 1001101
Enter the Generating polynomial: 1011
----------------------------------------
Data padded with n-1 zeros : 1001101000
----------------------------------------
CRC or Check value is : 101
----------------------------------------
Final data to be sent : 1001101101
----------------------------------------
Enter the received data: 1001101101
-----------------------------
Data received: 1001101101
No error detected

说明

由于传输和接收的数据相同，因此没有信号错误。

Enter the received data: 1001001101
-----------------------------
Data received: 1001001101
Error detected

存在信号错误，因为发送的数据与接收的数据不同。

程序的执行时间和空间需求分别由时间复杂度和空间复杂度表示。使用大O符号表示时间复杂度和空间复杂度。由于同时推断出两个for循环，因此程序的time complexity为O(n^2)。

由于使用了单维字符数组来存储n个字符，因此程序的space complexity为O(n)。

使用位操作实现CRC

CRC程序通过位操作技术实现如下。

算法

使用位操作技术实现C语言CRC的方法如下：

• 获取数据和生成多项式。
• 将生成多项式和输入数据转换为十进制。
• 为了在数据末尾附加零，将数据中的位左移n-1位，其中n是生成多项式的长度。
• 借助对数函数，确定需要移动多少位。
• 通过计算的位数左移数据，并使用生成多项式执行XOR运算。
• 识别程序的剩余部分，然后向其中添加一些数据，以便可以进一步处理。
• 继续此过程，直到所有数据位都已用于计算为止。

用于将数字从十进制转换为二进制的算法如下：

• 使用数字和2进行取模运算以确定余数。
• 确定10的余数次幂的值，然后乘以该值。
• 将上一步中发现的值相加。
• 将十进制数除以二后增加计数器。持续此过程，直到十进制数不再等于0。

输出

Enter the data to be transmitted: 1001101
Enter the generator polynomial: 1011
Check value or CRC: 101
Data to be sent:  1001101101
......................................
Process executed in 1.11 seconds.

说明

程序的执行时间和空间需求分别由时间复杂度和空间复杂度表示。使用大O符号表示程序的复杂度。由于一次只假定一个for循环，因此程序的time complexity为O(n)，并且由于字符存储在单维字符数组中，因此其space complexity也为O(n)。

结论

• 循环冗余校验（CRC）是一种错误验证过程，用于确定发送方发送的信号是否存在错误。
• 使用生成多项式计算数据的CRC值，然后同时传输数据和CRC。
• 在过程的每个阶段，都使用XOR运算来确定CRC值。
• 接收方通过确定计算出的CRC是否为零来验证自身。
• 可以使用字符数组和位操作方法在C语言中创建CRC程序。
• 这两种方法在时间和空间复杂度方面具有相同的水平。