校验码

在原始传输的二进制码中，增加与传输信息无关的位，以用来检验或者纠错传输的信息

奇偶校验

名称是个错误，应该叫奇偶验码，因为他只能验不能校。

一、奇校验

整个校验码(奇校验位+有效信息位)中1的个数为奇(每位相加和为奇数)

二、偶校验

整个校验码(奇校验位+有效信息位)中1的个数为偶(每位相加和为偶数)
三、举例说明

四、局限性

只能发现奇数个位置出错，而且仅仅是发现不能纠正。

海明(Hamming)校验码

一、基本概念本质上是多重奇偶校验码，有一位出错可以影响多个奇偶校验码，然后比对这几个奇偶校验码都出现的位，这几个位就是出问题的。
如果出错的几组校验码都指向相同的位，那么就把这些位的数字取反即可，这就是校;如果出错的几组校验码都指向位不是唯一的，那么这几种情况的出错位就是可能出错，但是不确定到底是那个，这就是验。编码的最小码距为 L ，检测错误的位数D， 纠正位数为C ，则他们满足下列关系

二、举例说明

编码前有效信息为10011101，求校验码位数？

求海明码值——一般采用偶校验

到此整个编码工作结束，各校验码的码值和码位如下

求解海明码值

你会发现只有S1和S3的值为1,对比表格发现只有H5为两个共有的元素(阴影的那列)，所以判断是H5出了问题

循环冗余校验码(CRC码)

循环冗余码(Cyclic Redundancy Code, CRC)又称多项式码， 任何一个二进制串都可以跟一个只含01的多项式建立关系。

模二除法

循环冗余码组成

假设发送端传输K位二进制信息码，双方实现预订好G(x)(其中G(x)的阶数R)，将K左移r位，K与G(x)模2除法，得余数(正好也是R位)，放到K后面拼接成功。除数不是随便找一个多项式就可以用来计算的，事实上有一套标准。

举例说明

设要传输的信息码 101001 生成多项式

求对应的CRC码

1)移位

将原先的 K 左移 R位，得 101001 000，此时校验位为 000，信息位为 101001

2)模2除法

根据前面的模2除法求解得到余数 001

3)余数放到校验位

得到余数 001，重新放到校验位得到最终报文 101001001

捡错与纠错

在接收端收到了CRC码后用生成多项式为G(x)去做模2除，若得到余数为0,则码字无误。若如果有一位出错，则余数不为0，而且不同位出错，其余数也不同。可以证明，余数与出错位的对应关系只与码制及生成多项式有关，而与信息位无关。

但这个例子不太满足一般使用习惯，仅仅是用来举例说明CRC，所以，我们重新计算一个循环冗余码，假设传输信息为 1010 ，多项式为G(x)＝1011，可得下表

根据上面得到的结论，如果我们在求出余数不为0后，一边对余数补0继续做模2除，同时让被检测的校验码字循环左移。重新的CRC码说明，当出现余数(101)时，出错位也移到A7位置，当出现余数(100)，出错位也移到A3位置上，可通过异或门将它纠正后在下一次移位时送回A1。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时，循环码校验能有效地降低硬件代价，这是它得以广泛应用的主要原因。

eg:对上图的CRC码(G(x)＝1011，C(x)＝1010)，若接收端收到的码字为1010111，用G(x)＝1011做模2除得到一个不为0的余数100，说明传输有错。将此余数继续补0用G(x)＝1011作模2除，同时让码字循环左移1010111。做了4次后，得到余数为101，这时码字也循环左移4位，变成1111010。说明出错位已移到最高位A7，将最高位1取反后变成0111010。再将它循环左移3位，补足7次，出错位回到A3位，就成为一个正确的码字1010011。