计算机组成原理——校验码（奇偶校验码、汉明校验码、循环冗余校验码）

一、为什么要使用校验码？

数据在计算机系统内加工、存取和传送的过程中可能会产生错误。为了减少和避免这类错误，引入了数据校验码。数据校验码是一种常用的带有发现某些错误，甚至带有一定自动改错能力的数据编码方法。

例子：

码距：两个合法码字对应位上数字的不同位的个数
上图中，方案一的码距为1，因为00和01之间只有1位数字不同。而方案二的码距为2，因为00和11之间有2位数字不同。
奇校验：保证一段数据中出现奇数个1，仅需1位
在上图方案一中，使用奇校验方法，则A的码字变为100，B的码字变为001。码字中的最高位（即加粗的数字）就是校验码。增加校验码后，可以发现方案一的码距变为了2。
将奇校验改变规则->海明码、CRC

二、奇偶校验码

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

【例2-3】给出两个编码1001101和1010111的奇校验码和偶校验码。
答：
设最高位为校验位，余7位是信息位，则对应的奇偶校验码为：
1001101 —— 11001101（奇校验）01001101（偶校验）
1010111 —— 01010111（奇校验）11010111（偶校验）

三、海明校验码思路简介

海明码设计思路：分组校验一>多个校验位一>校验位标注出错位置

1010->1011 如果1010在传输过程中，变成了1011，我们希望通过校验位来告诉我们数据的哪个位置出现了错误！显然这里的校验位应该为001。

四、海明码求解步骤

信息位：1010

1. 确定海明码的位数：2^k >= n+k+1
   n=4 ------> k=3
   设信息位D4D3D2D1（1010），共4位，校验位P3P2P1，共3位，对应的海明码为H7、H6、H5、H4、H3、H2、H1。
2. 确定校验位的分布
   
   校验位P，放在海明位号为的位置上
   信息位按顺序放到其余位置
3. 求校验位的值
   
   
4. 纠错
   经过检验方程计算后得到的结果全为0，则说明数据传输过程中没有出错。否则，说明出现了错误，出现1的位置，即为数据传输过程中中出错的位置！
   

五、循环冗余校验码

【例2-5】设生成多项式为G（x）=x3+x2+1，信息码为101001，求对应的CRC码。

1. 确定K、R以及生成多项式对应的二进制码
   
2. 移位
   信息码左移R位，也就是低位补R个0
3. 相除
   对移位后的信息码，用生成多项式进行模2除法，产生余数
   对应的CRC码：101001001

模2除法的方法如下：
1）最高位为1则商1，最高位为0则商0
2）减法规则为：对应位上相同，结果为0，不同，结果为1

4. 检错和纠错

六、总结