【愚公系列】软考中级-软件设计师 005-计算机系统知识（校验码）

🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，CSDN商业化专家，阿里云专家博主，阿里云签约作者，腾讯云优秀博主，腾讯云内容共创官，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2023年华为云十佳博主，2022年CSDN博客之星TOP2，2022年华为云十佳博主等。 🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。 🏆🎉欢迎 👍点赞✍评论⭐收藏

🚀前言

校验码是计算机系统中一种用于验证数据完整性的技术。

常见的校验码包括奇偶校验码、循环冗余校验码（CRC）、校验和等。

奇偶校验码是最简单的一种校验码。它通过在数据中添加一个比特位，使得数据中的1的个数为奇数或偶数，从而验证数据的正确性。例如，对于一个字节（8位）的数据，奇偶校验码可以是最高位为0或1，使得整个字节中1的个数为偶数或奇数。

循环冗余校验码（CRC）是一种更复杂的校验码。它通过对数据进行多项式除法计算，生成一个固定长度的校验码。接收方同样通过进行多项式除法计算，验证接收到的数据是否正确。CRC码具有很高的错误检测能力，常用于存储介质、网络通信等领域。

校验和是对数据进行求和运算得到的一个校验码。发送方将数据的每个字节进行求和，并将结果作为校验码附加在数据后面发送。接收方同样对接收到的数据进行求和运算，并与接收到的校验码进行比较，来验证数据的正确性。校验和可以用于简单的错误检测，但对于多字节的数据，会存在一定的冲突概率。

校验码是计算机系统中保证数据完整性的一种重要技术，通过对数据添加校验信息，可以有效地检测数据是否被篡改或错误。不同的校验码适用于不同的应用场景，选择合适的校验码可以提高数据传输的可靠性。

🚀一、校验码

🔎1.奇偶校验

奇偶校验是一种错误检测方法，用于检测数据传输过程中的错误。它通过在数据中添加一个奇偶位来保证传输的数据的正确性。

奇偶校验分为奇校验和偶校验两种方式。

• 奇校验：在传输的数据中，如果数据中的1的个数为奇数，则奇校验位设置为0，否则设置为1。
• 偶校验：在传输的数据中，如果数据中的1的个数为偶数，则偶校验位设置为0，否则设置为1。

奇偶校验的原理是通过在数据中添加一个校验位来保证数据传输的正确性。发送方在传输数据的同时计算数据中1的个数，然后根据奇偶校验的方式设置校验位，并与数据一起传输。接收方在接收数据后，再次计算数据中1的个数，如果与校验位不匹配，则说明数据传输过程中发生了错误。

奇偶校验的优点是简单易实现，能够检测到单比特错误。缺点是无法检测到多比特错误，对于噪声干扰较大的环境，可靠性较低。在实际应用中，奇偶校验一般用于较低层的通信协议中，如串口通信中的RS-232协议。

注意：

• 如果有奇数个位发生误码，则奇偶性发生变化，可以检查出误码，但不能纠错。
• 如果有偶数个位发生误码，则奇偶性不发生变化，不能检查出误码(也称漏检)。

🔎2.模2运算

模2运算是一个对二进制数进行运算的操作，它的原理是将两个二进制数按位进行异或运算。具体来说，对于两个二进制数a和b，模2运算可以表示为a ⊕ b，其中⊕表示异或操作。

在模2运算中，每一位的结果只有两种可能：0和1。如果两个二进制数的对应位相同，那么结果为0；如果对应位不同，结果为1。模2运算常用于校验和计算、差错检测和纠错编码等领域。

例如，对于两个二进制数1010和1101，进行模2运算的结果为0111。

模2运算是一种二进制算法，CRC校验技术中的核心部分。本质是异或运算，且不考虑进位和借位。

🦋2.1 加法

模2加法是指对于两个二进制数的对应位进行相加，结果取模2。也就是说，如果两位都是0或者都是1，结果就是0，如果两位一个是0一个是1，结果就是1。

0＋0＝0   0＋1＝1  1＋0＝1   1＋1＝0

例如：0101 + 0011 = 0110，列竖式计算：

	0 1 0 1
+	0 0 1 1
—————————————	
	0 1 1 0

🦋2.2 减法

模2减法是指在模2的情况下进行减法运算。在模2的情况下，只有两个可能的值：0和1。因此，模2减法的规则如下：

0－0＝0   0－1＝1   1－0＝1   1－1＝0

例如：0110－0011＝0101，列竖式计算：

    0 1 1 0
 -  0 0 1 1
—————————————	
    0 1 0 1

🦋2.3 乘法

模2乘法指的是将两个数相乘后取模2的结果。换句话说，模2乘法就是判断两个数的乘积是奇数还是偶数。

在模2乘法中，如果两个数中有一个数是偶数，那么乘积一定是偶数；如果两个数都是奇数，那么乘积是奇数。

0×0＝0   0×1＝0   1×0＝0   1×1＝1

多位二进制模2乘法类似于普通意义上的多位二进制乘法

不同之处在于后者累加中间结果（或称部分积）时采用带进位的加法

模2乘法对中间结果的处理方式采用的是模2加法

例如1011 × 101＝100111，列竖式计算：

      	1 0 1 1
×  	 	  1 0 1
———————————————————			
        1 0 1 1
      0 0 0 0
+   1 0 1 1
———————————————————		
    1 0 0 1 1 1
————————————————

🦋2.4 除法

模2除法是模2乘法的逆运算。模2除法具有下列三个性质：

1、当最后余数的位数小于除数位数时，除法停止。

2、当被除数的位数小于除数位数时，则商数为0，被除数就是余数。

3、只要被除数或部分余数的位数与除数一样多，且最高位为1，不管其他位是什么数，皆可商1。

🔎3.CRC循环冗余校验

CRC（Cyclic Redundancy Check）循环冗余校验是一种用于检测和纠正数据传输中可能出现的错误的技术。它利用一个固定的生成多项式来对数据进行计算，生成一个固定长度的校验码。接收方在接收到数据后，同样使用生成多项式对数据进行计算，并与发送方生成的校验码进行比较，以判断数据是否被传输过程中出现了错误。

CRC校验利用位运算的方式，在数据传输中具有快速计算和较高的检错能力。它在数据通信和存储中广泛应用，如以太网、串行通信协议、磁盘驱动器等。

CRC校验的原理是将数据看作二进制序列，并通过将每一位与生成多项式进行除法运算得到余数。发送方在发送数据时，将生成的校验码附加在数据后面一起发送；接收方在接收到数据后，同样使用生成多项式对数据进行计算，得到一个余数。如果余数为0，则说明数据没有错误；如果余数不为0，则说明数据在传输过程中出现了错误。

CRC校验的生成多项式决定了校验码的长度和检错能力。常用的CRC算法有CRC-8、CRC-16、CRC-32等。不同的生成多项式可以提供不同的校验能力，但也会引入不同的开销。因此，在选择CRC算法时需要根据具体的应用场景平衡校验能力和计算效率。

原始数据是：1101011011

多项式：

化简之后就是

把上面多项式中各项的系数取出来依次排列构成除数：10011

把原始数据后面加4（上面多项式最高幂次为x^4）个0构成被除数：1101011011--0000（原始数据--填充位）

如下图所示为这个除法的计算过程（模2除法）

算出来的余数为1110，这就是checksum，增加了checksum的数据就是：

1101011011--1110（原始数据--checksum）

🔎4.海明校验

海明校验是一种用于错误检测和纠正的校验码。它通过添加额外的校验位，可以检测和纠正比特错误。海明码的基本原理是，在数据位的基础上添加校验位，使得每个校验位覆盖特定的数据位。这样，通过校验位的变化可以检测出错误的位置，并且还可以根据校验位的变化进行纠正。

海明码的构造方式是将数据位按照一定规则分组，然后在每个组中添加校验位。校验位的值是通过对数据位进行异或操作得到的。校验位的个数取决于数据位的个数，一般是将数据位的个数加上校验位的个数加一。

在接收数据时，可以通过校验位的变化进行错误检测和纠正。如果某个校验位与接收到的数据位产生冲突，那么说明该数据位存在错误。通过对冲突的校验位进行异或操作，可以得到正确的数据位。

海明校验可以有效地检测和纠正单个比特错误，但对于多个比特错误的检测和纠正能力有限。此外，海明码还存在一定的冗余，会增加数据的传输量。因此，在实际应用中，需要根据具体的需求和信道的特性选择合适的校验码。

海明校验的规则：

🦋4.1 计算校验码位数

原始数据0110，n = 4

根据海明校验码公式可以得到需要添加的校验码位数k = 3

校验码放置的位置应为2的整数次幂，即Pi=2^i

于是我们得到了这样一个待计算的海明码：

其中，P0、P1、P2为三个我们添加的校验码

🦋4.2 确定校验组

接下来我们为每一个数据添加校验组，校验组是什么意思呢，就是这一下标对应的数据可以由一个校验组来唯一对应检验。通俗地讲，做法就是将每一个数据位的下标分解成校验码所在下标的和，（校验位不分解），拿我们的例子来看看：

🦋4.3 计算校验码的值得出海明校验码

计算海明校验码的最后一个步骤就是得出P0、P2、P3的具体值，其做法为：

计算Pi的值，就在校验组中将与Pi有关的那几组数据做 异或（相同为0，不同为1） 运算拿我们的例子来看看：

计算结束后，和原来的数据组合我们就得到了海明校验码：

我正在参与2024腾讯技术创作特训营第五期有奖征文，快来和我瓜分大奖！