1. 奇偶校验码

> 校验码

校验码是指能够发现或能够自动纠正错误的数据编码，也称检错纠错码。

校验码的原理是通过增加一些冗余码，来检验或纠错编码。

如上图，添加一位冗余码，这时当出现位错误时（如 100 -> 101），就会发现变为非法状态进而检错。

> 几个概念

• 码字： 由若干位代码组成的一个字
• 码字间的距离：两个码字逐位对比，具有不同位的个数
• 码距：各合法码字间的最小距离

当码距 d = 1 时，无检错能力；d >= 2 时，有检错能力。码距越大，检错、纠错能力越强。

> 奇偶校验码

• 奇校验码：整个校验码（有效信息位和校验位）中 1 的个数为奇数
• 偶校验码：整个校验码（有效信息位和校验位）中 1 的个数为偶数
  
  具体来说如何检验这就涉及到计网所学：
  

> 偶检验的硬件实现

各信息进行异或运算，得到的结果即为偶校验位：

2. 海明校验码

海明码实际上是一种多重奇偶校验码。其实现原理是将信息位分组进行奇偶校验，有多个校验位，并且多个校验位可以标注出出错位置。

> 确定校验位数目

设信息位为 $D_4{D}_3{D}_2{D}_1$ 共 4 位，则校验位 $P_3{P}_2{P}_1$ 共 3 位，对应海明码 $H_7{H}_6{H}_5{H}_4{H}_3{H}_2{H}_1$ 。

> 确定校验位的分布

海明码规定，校验位 $P_i$ 要放在海明位号为 $2^{i-1}$ 的位置上。因此，$H_1$ = $P_1$、$H_2$ = $P_2$、$H_4$ = $P_3$

对于信息位 $D_4{D}_3{D}_2{D}_1$ （1010），按顺序插入，则有：

> 校验位的值

将每个信息位所处的海明位号以二进制形式表示出来，校验位 $P_i$ 的值为第 i 组（由该校验位校验的数据位）所有位求异或，如下图：

则有下表：

> 海明的校验原理

每个校验组分布利用校验位和参与形成该校验位的信息位进行奇偶校验，构成 k 个校验方程：

• $S_1=P_1\oplus D_1\oplus D_2\oplus D_4$
• $S_2=P_2\oplus D_1\oplus D_3\oplus D_4$
• $S_3=P_3\oplus D_2\oplus D_3\oplus D_4$

若 $S_3{S}_2{S}_1$ 值为 $000$ ，则说明没有出错；否则说明出错，$S_3{S}_2{S}_1$ 即为错误位位号。具体来说：

注意：有的题目可能信息位和校验位顺序是颠倒的，如 $D_1{D}_2{D}_3{D}_4$、$P_1{P}_2{P}_3$，但是其做法是不变的，只不过调整顺序即可。

> 补充

海明码具有 1 个比特位的纠错能力，和 2 个比特位的检错能力。但是它无法区分到底是 1 位错误还是 2 位错误。

为了解决此问题，海明码使用时通常在首部加上 全校验位 ，对整体进行偶校验。

$S_3{S}_2{S}_1=000$ 且全体偶校验成功，则没有出错。
$S_3{S}_2{S}_1\ne 000$ 且全体偶校验失败，则有 1 位出错，纠错即可。
$S_3{S}_2{S}_1\ne 000$ 且全体偶校验成功，则有 2 位出错，需要重传。

ps：不得不说，海明太强了，怪不得获得了图灵奖

3. 循环冗余校验码

> 基本思想

收发双方约定好一个 生成多项式 G(x) ，发送方基于待发送的数据和生成多项式计算出 R 位校验码 ，将其添加到 K 位信息码 （待传输数据）的后面一起传输。

在接收端，利用生成多项式对接收到的 K+R 位 CRC 码 进行模 2 除法，若整除则说明没有出错，否则要进行重传或纠错。

> 具体来说

首先，计算出 R 位校验码，即下图所示余数，并拼接成 K + R 位 CRC 码发送给接收端：

之后，对接收收到的信息与生成多项式系数所构成的比特串相除，看余数是否为 0 ：

> 检错和纠错

对于上述例子，出错位置和对应余数如下图所示：

可以看出，即使计算出余数为 010 并不一定是第二位出错，也可能是第九位出错。

上图是从王道考研视频中扒下来的，其实从第二行开始数据就错了。用在这里只是想说明一下 CRC 码是否可以纠错与 R 的位数是相关的，如果能够一一对应，CRC 码是可以纠错的，只需取反即可。

其实，若生成多项式选择得当，满足 2^R ≥ K+R+1，则 CRC 码是可以纠正 1 位错误的。但一般在差错检测是信息位远大于检错位，所以循环冗余校验实际中只用来检错。

本文主要介绍以下三种校验码：检验位求解、校验码求解、纠错能能力

1. 奇偶校验码
2. 海明码（汉明码）
3. 循环冗余码（CRC码）

---

1.奇偶校验

• 校验原理
  
• 奇偶校验码
  
  

---

2. 海明校验码

• 海明码校验码思路简介
  
• 海明码求解步骤
  
  
  
• 海明码的纠错能力与检错能力
  

---

3.循环冗余校验码（CRC码）

• CRC码思想
  
• CRC码构造
  
• 示例
• 模2除运算：根据被除数第一位判断商1或商0，剩余位数值与被除数进行异或运算（被除数首位只判断是否商1，不参与运算，剩余位数都要参与运算）
  
  
• 检错和纠错能力
  

BCD码

十进制数用二进制编码的形式，通过专门的十进制数运算指令进行处理。计算机中有专门的逻辑线路在BCD码运算时使每4位二进制数按十进制进行处理。

每位十进制数的取值可以是0-9这十个数之一，因此，每一个十进制数位必须至少由4位二进制位来表示。而4位二进制位可以组合成16种状态，去掉10种状态后还有6种冗余状态，所以从16种状态中选取10种状态来表示十进制数位0-9的方法很多，可以产生多种BCD种。

8421码的映射关系：

4个二进制位 ------>16种不同的状态

BCD码值使用其中10种 ------>不同的映射方案

注：0000-1001分别对应0-9，进行加法后若超出该范围，则需+0110进行修正（强制向高位进1）

余3码：8421码+$(0011{)}_2$

2421码：改变权值定义

2、4、 2、 1分别对应，每一位的权值

表示0-4时最高位为0，表示5-9时最高位为1

奇偶校验码

几个简单的概念：

码字：由若干位代码组成的一个字

两个码字间的距离：将两个码字逐位进行对比，具有不同的位的个数

码距：一种编码方案可能有若干个合法码字，各合法码字间的最小距离

当码距d=1时，无检错能力；当d=2时，有检错能力；当d>=3，若设计合理，可能具有检错、纠错能力。

奇偶校验码

奇校验码：整个校验码（有效信息位和校验位）中“1”的个数为奇数

偶校验码：整个校验码（有效信息位和校验位）中“1”的个数为偶数

例：给出两个编码1001101和1010111的奇校验码和偶校验码。
设最高位为校验位，余7位是信息位，则对应的奇偶校验码为：
奇校验：11001101 01010111
偶校验：01001101 11010111

偶校验的硬件实现：各信息进行异或（模2加）运算，得到的结果即为偶校验位

⊕：异或（模2加）

0⊕0=0
0⊕1=1
1⊕0=1
1⊕1=0

求偶校验位：

1⊕0⊕0⊕1⊕1⊕0⊕1=0

1⊕0⊕1⊕0⊕1⊕1⊕1=1

进行偶校验（所有位进行异或，若结果为1说明出错）：

0⊕1⊕0⊕0⊕1⊕1⊕0⊕1=0

海明校验码

偶校验：1010 ->01010，能发现奇数位错误，但无法确定是哪一位出错。

海明码设计思路：将信息位分组进行偶校验 ->多个校验位 ->多个校验位标注出错位置

信息位：n
校验位：k ------->2^k种状态
信息位+校验位：n+k
——————> 2^k>=n+k+1

其中n+k位中任何一位都可能出错，1表示1中正确状态

海明码求解步骤：

例：信息位：1010

1.确定海明码的位数：2^k>=n+k+1

n=4 ----> k=3
设信息位$D_4$$D_3$$D_2$$D_1$(1010)，共4位，校验位$P_3$$P_2$$P_1$，共3位，对应的海明码为$H_7$$H_6$$H_5$$H_4$$H_3$$H_2$$H_1$

2.确定校验位的分布

校验位$P_i$放在海明位号位2^i-1 的位置上，信息位按顺序放在其余位置

3.求校验位的值

二进制：

$H_3$：3 -->011

$H_5$：5 -->101

$H_6$：6 -->110

$H_7$：7 -->111

将末尾为1的值进行偶校验：

$P_1$=$H_3$⊕$H_5$⊕$H_7$=$D_1$⊕$D_2$⊕$D_4$=0⊕1⊕1=0

同理中间一位：

$P_2$=$H_3$⊕$H_6$⊕$H_7$=$D_1$⊕$D_3$⊕$D_4$=0⊕0⊕1=1

第一位：

$P_3$=$H_5$⊕$H_6$⊕$H_7$=$D_2$⊕$D_3$⊕$D_4$=1⊕0⊕1=0

4.纠错

对各个分组进行偶校验运算
校验方程：

$S_1$=$P_1$⊕$D_1$⊕$D_2$⊕$D_4$

$S_2$=$P_2$⊕$D_1$⊕$D_3$⊕$D_4$

$S_3$=$P_3$⊕$D_2$⊕$D_3$⊕$D_4$

接收到：1010010

$S_1$=$P_1$⊕$D_1$⊕$D_2$⊕$D_4$=0⊕0⊕1⊕1=0

$S_2$=$P_2$⊕$D_1$⊕$D_3$⊕$D_4$=1⊕0⊕0⊕1=0

$S_3$=$P_3$⊕$D_2$⊕$D_3$⊕$D_4$=0⊕1⊕0⊕1=0

海明码的检错、纠错能力：纠错——1位
检错——2位