大家好，我是南瓜~
在这篇文章中，我们将介绍软件评测师考试重点难点知识中的校验码(第一部分：奇偶校验码、海明码)。这是软考综合知识，也适合软件设计师等其他专业参考。
一、校验码的基础概念
计算机系统运行时，为了确保数据在传送过程中正确无误，一是提高硬件电路的可靠性，二是提高代码的校验能力，包括查错和纠错。通常使用校验码的方法来检测传送的数据是否出错。其基本思想是把数据可能出现的编码分为两类：合法编码和错误编码。合法编码用于传送数据，错误编码是不允许在数据中出现的编码。合理地设计错误编码以及编码规则，使得数据在传送中出现某种错误时会变成错误编码，这样就可以检测出接收到的数据是否有错。
一个编码系统中任意两个合法编码之间至少有多少个二进制位不同，就称为码距。（来自百度百科）
二、前置知识
1、二进制位的异或运算(⊕)
A⊕B：当A与B不相同时，结果为1；当A与B相同时，结果为0。
与零异或，结果为自己；
与自己异或，结果为0。
2、模2运算
(1)模2加法
模2加法相对于普通的算术加法，主要的区别在于模2加法不做进位处理。
具体结果如下：
0+0 = 0
0+1 = 1
1+1 = 0
1+0 = 1
由此可见，模2加法的计算结果同异或运算的结果一模一样。
(2)模2减法
模2减法相对于普通的算术减法，主要区别在于模2减法不做借位处理。
具体结果如下：
0-0 = 0
0-1 = 1
1-1 = 0
1-0 = 1
由此可见，模2减法的计算结果同模2加法，以及异或运算的结果一模一样。
(3)模2除法
模2除法相对于普通的算术除法，主要的区别在于模2除法既不向上借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。
模2除法就是二进制下的除法。
模2除法与算术除法类似，但每一位除的结果不影响其它位，即不向上一位借位，所以实际上就是异或运算。
在循环冗余校验码（CRC）的计算中有应用到模2除法。
模2除法要求除数和被除数以相同位数进行相除，它既不向上位借位，也不比较除数和被除数的相同位数值的大小。
除数和被除数以相同位数进行相除就是执行异或运算，商为1。
当已经除了几位后，余数位数小于除数，商为0，余数往右补一位；
如果余位数仍比除数少，则继续商为0；
当余数位数和除数位数一样时，商为1，进行异或运算，得到新的余数，以此直至被除数最后一位。
示例：模2除法1111000除以1101
计算过程如下图所示：
所以结果是商为1011，余数是0111。
三、校验码的分类
常用的3种校验码是：奇偶校验码、海明码、循环冗余校验码。
1、奇偶校验码(Parity Code)
奇偶校验码(Parity Code)是一种简单有效的校验方法。这种方法通过在编码中增加一位校验位来使编码中1的个数为奇数(奇校验)或者为偶数(偶校验)，从而使码距变为2。对于奇校验，它可以检测代码中奇数位出错的编码，但不能发现偶数位出错的情况，即当合法编码中的奇数位发生了错误时，即编码中的1变成0或0变成1，则该编码中1的个数的奇偶性就发生了变化，从而可以发现错误。
注：奇偶校验码的码距为2。
常见的奇偶校验码有3种：水平奇偶校验码、垂直奇偶校验码、水平垂直奇偶校验码。
奇偶校验多用在串行异步通信中，一般情况下，一个完整的串行数据帧包括11位，分别由起始位1位，数据位8位，奇偶校验位1位和停止位1位组成。这里的奇偶校验位就是本文所说的奇偶校验，它位于数据位和停止位之间。
如下图所示：
示例：A 和 B之间用串行异步通信，采用奇校验
假设A发送的数据帧(比特流)是“1 10100101 1 1”,
如果B收到的数据帧里，如果1的个数为偶数，则判断数据错误，需重传；
如果B收到的数据帧里，如果1的个数为奇数，则判断数据正确，正常接收。
奇偶校验码的应用场合：
一般在同步传输方式中采用奇校验（odd），在异步传输方式中采用偶校验（even）。
奇偶校验码的优缺点：
(1)优点
简单、实用
(2)缺点
首先，只能检测单比特的错误，对于多比特的错误，比如连续的两个比特或者多个比特的差错，奇偶校验无能为力。
其次，奇偶校验能够检测出的错误只有一部分，并不能检测出所有的错误。例如，如果传输过程中发生了连续的偶数比特翻转，那么奇偶校验的结果仍然是正确的，因此奇偶校验不能保证全面可靠的数据传输。
2、海明码(Hamming Code)
海明码(Hamming Code)是由贝尔实验室的Richard Hamming设计的，是一种利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的特定位置插入k个校验位，通过扩大码距来实现检错和纠错。
海明码计算过程：
假设数据位有n位，即D[n-1],D[n-2],...,D[1],D[0]，
则校验位有k位，即P[k],P[k-1],...,P[1]，
那么，根据海明码的编码规则，构成的海明码有n+k位，即H[n+k],H[n+k-1],...,H[1]。
满足以下规则：
(1) 2k-1>=n+k
(2)先根据“ P[i]=H[j], 且j=2i-1 ,i=1～k”插入校验位；
然后，剩余的位置，根据从低位到高位的次序，依次插入数据位的低位到高位。
(3)校验位的计算(以偶校验为例)
P1=P1以外的所有“以二进制表示”的下标倒数第1位是1的H[i]的异或值，i=1～n+k
P2=P2以外的所有“以二进制表示”的下标倒数第2位是1的H[i]的异或值，i=1～n+k
…
Pk=Pk以外的所有“以二进制表示”的下标倒数第k位是1的H[i]的异或值，i=1～n+k
注：如果采用奇校验，则只要把校验位的偶校验值取反即可。
示例：8位数据位的海明码的构造过程
第一步：计算校验位数k
根据“2k-1>=n+k，n=8”得出，k=4
第二步：根据海明码的位数相应标识二进制下标
由于n+k=12，故海明码共12位，构造如下图对应关系。
第三步：根据“ P[i]=H[j], 且j=2i-1 ,i=1～k”插入校验位
第四步：剩余的位置，根据从低位到高位的次序，依次插入数据位的低位到高位
第五步：计算校验位
P1=P1以外的所有“以二进制表示”的下标倒数第1位是1的H[i]的异或值，i=1～n+k
二进制下标倒数第1位是1的H[i]：H[1]，H[3]，H[5]，H[7]，H[9]，H[11]
对应(P1以外)：D0，D1，D3，D4，D6
故P1 = D0⊕D1⊕D3⊕D4⊕D6 //偶校验
同理，二进制下标倒数第2位是1的H[i]：H[2]，H[3]，H[6]，H[7]，H[10]，H[11]
对应(P2以外)：D0，D2，D3，D5，D6
故P2 = D0⊕D2⊕D3⊕D5⊕D6 //偶校验
同理，二进制下标倒数第3位是1的H[i]：H[4]，H[5]，H[6]，H[7]，H[12]
对应(P3以外)：D1，D2，D3，D7
故P3 = D1⊕D2⊕D3⊕D7 //偶校验
同理，二进制下标倒数第4位是1的H[i]：H[8]，H[9]，H[10]，H[11]，H[12]
对应(P4以外)：D4，D5，D6，D7
故P4 = D4⊕D5⊕D6⊕D7 //偶校验
总结如下：
注：如果采用奇校验，则只要把校验位的偶校验值取反即可。
(4)错误检测
首先，计算G1～Gk
G1=含P1的所有“以二进制表示”的下标倒数第1位是1的H[i]的异或值，i=1～n+k
G2=含P2的所有“以二进制表示”的下标倒数第2位是1的H[i]的异或值，i=1～n+k
…
Gk=含Pk的所有“以二进制表示”的下标倒数第k位是1的H[i]的异或值，i=1～n+k
其次，如果采用偶校验，则Gk…G2G1全为0时，表示数据正确；
反之，当Gk…G2G1不全为0时，表示数据错误。
错误的位置是H[i]，i=二进制表示的下标Gk…G2G1。
比如G4G3G2G1=1001，则H[i]=H[9]=D4，即D4错了，将其取反即可纠正错误。
相应的，如果采用奇校验，则Gk…G2G1全为1时，表示数据正确。
示例：8位数据位的海明码的错误检测
示例：假设数据为01101001，试采用4个校验位求其偶校验方式的海明码。
根据前面的计算步骤，得出结果如下图所示。
所以，数据01101001采用偶校验对应的海明码为：011001001101
海明码的应用场合：
海明校验码广泛应用于数字通信、数据存储、计算机存储器和数字电路中。
在数字通信和数据存储中，海明校验码能够有效地检测和纠正数据传输中的错误，可以保证数据传输的可靠性和完整性。
在计算机存储器和数字电路中，海明码能够检测硬件故障，对系统的稳定性和可靠性具有重要作用。
海明码的优缺点：
相对于其他纠错码，海明码的优点在于它可以检测和纠正多个比特位错误，而不仅仅是单个比特位错误。此外，海明码还具有较低的编码和解码复杂度，这也使得它成为一种流行的纠错码。
然而，海明码也有一些缺点。
首先，它需要额外的校验比特位来实现检测和纠错，这也意味着它需要更多的存储空间。
其次，海明码的识别和校验过程相对复杂，需要较高的计算效率，这在一些高速数据传输的场合可能会成为瓶颈。
======》以上是校验码的第一部分，剩下的部分正在抓紧整理中，敬请期待。。。
