8 校验码
计算机只能识别二进制数，在信息传输过程中，都是以电信号/光信号的形式进行传输。由于传输距离远，可能会导致信号衰减产生误差，在信息使用前需要进行相应的检验，以便判别信息是否正确，这种用于检查的信息，称为校验码。
校验码是在信息中额外增加的一些数据，来帮助校验。
最常用的校验码有3种：
- 奇偶校验：能检错，不能纠错。
- CRC循环冗余校验：能检错，不能纠错。
- 海明校验：能检错，能纠错。
考试考点：
- 3者的比对；
- CRC循环冗余校验的计算过程 或 编码过程。
奇偶校验
奇偶校验码的编码方法：由若干位有效信息的头部或尾部，再加上一个二进制位（校验位）组成校验码。实际包括两种校验：
- 奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。
- 偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数。
如：有效信息为：1011，则：
- 奇校验位为 0，校验码为 10110；
- 偶校验位为1，校验码为 10111。
如果有奇数个位发生误码，则奇偶性发生变化，可以检查出误码，但不能纠错。
如果有偶数个位发生误码，则奇偶性不发生变化，不能检查出误码（也称漏码）。
例：给出编码 1001101 的奇校验码和偶校验码（ ）。
A）10011011,10011010 B）10011011,10011011
C）10011010,10011010 D）10011010,10011011
解：由于奇偶校验位一定是互斥的，因此B、C校验码相同的情况可以排除。奇校验需要确保校验码“1”总数为奇数，偶校验需要确保校验码“1”总数为偶数。因此选：A
CRC循环冗余校验
CRC循环冗余校验的预备知识：
1 异或
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0
2 模2运算
- 被除数首位是几商几；
- 异或运算；
- 异或后首位一定是0舍弃掉这个0首位（去首位补末位）；
- 补末位（落数），再上商。
例：1011 0010 000 模二除 11001
解：商1101010，余数1010。
3 CRC校验码
CRC校验码：通信领域最常用的差错校验码。有两个部分：
- 左侧信息位：待发送数据；
- 右侧差错检测码：基于待发送数据与生成多项式的差错检测码，也称冗余码。
冗余位数越多，校验能力越强。
具体过程：
- 收发双方约定好生成多项式G(x)；
- 发送方基于待发送数据和生成多项式计算出差错检测码（冗余码），将其添加到待传输数据的后面一起传输；
- 接收方通过生成多项式来计算收到的数据是否产生了误码。
【注】算法要求：生成多项式必须包含最低此项，即x的0次项。
设：
完整形式：
因此生成多项式的bit形式为：10111。
在计算时，信息进行补零后形成被除数，生成多项式串是除数，最终的校验检测码是模2运算的余数。
例1：待发信息位101001，生成多项式为
计算编码后的信息。
解题的步骤如下：
- 构造被除数：待发送信息后添加生成多项式最高次数个0；
- 构造除数：生成多项式各项系数构成的比特串；
- 做模二除法运算；
- 检查余数：余数的位数应与生成多项式最高次数相同，如果位数不够，则在余数前补0来凑足位数。
解：
- 由生成多项式最高次项为3次，待发信息补3个0，除数101001000；
- 生成多项式1101；
- 进行模二除法：
- 冗余校验码为001，因此编码后的信息为：101001001。
例2：接收到的信息为101101001，生成多项式为：
判断传输是否有误码。
解题的步骤如下：
- 构造被除数：接收到的信息就是被除数；
- 构造函数：生成多项式各项系数沟通的比特串；
- 做模二除法运算；
- 检查余数：余数为0，传输过程无误码；余数不为0，传输过程产生误码。
解：
- 除数：101101001；
- 构造除数：1101；
- 做模二除法：
- 由于余数不为0，所以该信息为误码。
另外，如果是例1编码后的值101101001，模二除后，余数为0。
例3：在（ ）校验方法中，采用模二运算来构造检验位。（2019年上半年考题）
A）水平奇偶 B）垂直奇偶 C）海明码 D）循环冗余
答案：D
海明码校验
利用奇偶性来检错纠错的方法。在数据中增加冗余位来进行检错纠错的方法，以提高传输、存储的准确性。
海明码的原理
将原始数据分成若干个数据块，每一块数据中又开辟若干位校验位，用于检出错误后，利用校验位进行纠错，最终得到正确的数据。
数据之间的特定位上，加入K个校验位，通过扩大码距从而实现检错、纠错。
海明码实现方法
设数据位是n位，校验位是k位，则 n 和 k 必须满足以下关系：
【注】2^k 之所以减1，是因为数据所有可能情况中有一种情况位正确，因此要减1。
海明码的编码规则如下：
设k个校验位为：
n 个数位为：
对应的海明码为：
- 校验码Pi要放在2^(i-1)的位置；
- 海明码中的任何一位都是由若干个校验位来检验的；
- 被校验的海明位的下标等于所有参与校验该位的校验位的小标之和，而校验位由自身校验。
例：待传送信息为1010，若采用海明码校验，则奇校验规则下的海明码是（ ）。
A）0110010 B）0110011 C）1110010 D）1110011
解：
根据：
n = 4，
可以将 k = 1, 2, 3, ... 带入不等式，得到最小的 k = 3。
则H位数为：3 + 4 = 7 （位）
校验位分别为：
则校验位 Pi 与 数据 Dk的排列如下：
位数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Pi | P1 | P2 | D1 | P3 | D2 | D3 | D4 |
Dk | 1 | 0 | 1 | 0 |
建立海明码对应表：
校验码的位数 | 1 | 2 | 4 | 方法 |
海明码 | P1 | P2 | P3 | |
H1(P1) | √ | P1自己 | ||
H2(P2) | √ | P2自己 | ||
H3(D1) | √ | √ | 第3位：1+2（P1、P2代表的位数相加等于第3位） | |
H4(P3) | √ | P3自己 | ||
H5(D2) | √ | √ | 第5位：1+4（P1、P3代表的位数相加等于第5位） | |
H6(D3) | √ | √ | 第6位：2+4（P2、P3代表的位数相加等于第6位） | |
H7(D4) | √ | √ | √ | 第7位：1+2+4（P1、P2、P3代表的位数相加等于第7位） |
将表逐列向下看：
P1校验：D1、D2、D4 → 1 0 0 → P1 = 0；
P2校验：D1、D3、D4 → 1 1 0 → P2 = 1；
P3校验：D2、D3、D4 → 0 1 0 → P3 = 0。
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
Pi | P1 | P2 | D1 | P3 | D2 | D3 | D4 |
Dk | 1 | 0 | 1 | 0 | |||
H | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
则海明码为：0110010，选A