前言：

海明码：

1. 海明码一般只能纠1位错。
2. 海明码默认进行偶校验(除非特殊说明使用奇校验)。
3. 海明码是一串只由0和1组成的序列

奇偶校验

奇校验：一串由0和1组成的序列中1的个数如果为偶数则在前面加个1，使1的个数变成奇数，否则加0。
偶校验：一串由0和1组成的序列中1的个数如果为奇数则在前面加个1，使1的个数变成偶数，否则加0。

例：

1111 奇校验就是 11111 偶校验就是 01111
1110 奇校验就是 01110 偶校验就是 11110

计算：

计算   1011  的海明码

一、计算校验位的个数

公式：2^r >= m + r + 1

（理解：在只出错一位的情况下，且出错只为0或1之间的出错，所以，2^r表示r位校验码最大可以校验的总位数，m+r意思为整个码中可能出错的次数，1为唯一正确的一次，所以2^r 要>= m + r + 1）

r：校验位的个数

m：信息位的个数  1011的信息位个数为：4

所以r最小为3，即校验位的个数为3

死记硬背：

二、分组

确定校验位在海明码中的位置

校验码只出现在第2的r次方位置上，这里用P表示

分组：对P进行按进制位分组

先从P1开始，P1位置二进制中的最后一位是1（不看0），所以将所有位置二进制中最后一位为1的分为一组

即：
L1，L3，L5，L7

以此类推

L1，L3，L5，L7        将对应位置的序列值替换        P1，1，1，1

L2，L3，L6，L7     =====================》   P2，1，0，1

L4，L5，L6，L7                                                        P3，1，0，1

校验码计算：

偶校验：一串由0和1组成的序列中1的个数如果为偶数则在前面加个1，使1的个数变成奇数，否则加0。

第一组中1的个数是3，为奇数，所以P1应为1，保证1的个数为偶数，同理P2=0，P3=0

将P带回序列得到偶校验码为 1010101

奇校验：一串由0和1组成的序列中1的个数如果为偶数则在前面加个1，使1的个数变成奇数，否则加0。

第一组中1的个数是3，为奇数，所以P1应为0，保证1的个数为奇数，同理P2=1，P3=1

将P带回序列得到奇校验码为 1011110

纠错：

假如传输过程中将1011传成了 1001

按照偶校验纠错：校验位P的值刚刚已经计算出P1=1，P2=0，P3=0

按照上方的方法进行分组

根据纠错位E进行判断错误的位置

E1，L1，L3，L5，L7        将对应位置的序列值替换       E1，1，1，0，1

E2，L2，L3，L6，L7     =====================》  E2，0，1，0，1

E3，L4，L5，L6，L7                                                       E3，0，0，0，1

根据偶校验得出E1=1，E2=0，E3=1，按照E3E2E1的顺序合并得到101，101为10进制的5，所以第5个位置出错，如表所示是正确的

网上看了好几篇文章后终于算是捋明白了，但是看到的这些资源要么说得云里雾里，要么干脆说得有问题（然后还被点了好多赞。。。），无论如何这些都容易误导小白。作为C站多年老潜水员，我还是把海明校验码的要点总结分享一下吧。

1. 海明码的特点：

其中m表示数据位的位数，k表示海明校验码的位数

k位海明校验码一共可以表示种校验信息结果，其中有一种要用来表示没有出错的情况，则其余还剩-1种结果，为了使校验结果可以指出任一位出错的位置，则需要满足以上不等式。

2. 举例说明：

发送端：

设要传输的数据为101101100

（1）可知m=9，由公式，可知k最小值为4，所以总共要传输的数据位数为9+4=13；

（2）海明校验码放在索引号为的位（n=0,1,2,...,k-1）上，本例中k=4，所以校验位的索引为第1，2，4，8位，于是在下表中把这几位空出来

（3）列出进制转换表：

上表中，先说每一行的内容：从第二行开始，每一行的第一列代表索引号，这个索引号是除去了海明校验位之外的其他所有位。后面几列为该索引号对应的二进制表示，其位数取决于第（1）步计算得出的海明校验码的位数，比如第二行，索引号是3，十进制3对应的二进制就是0011，之所以用4位表示是因为这段信息码需要4个海明校验位。

再看列信息：第一行最右边数字1所对应的列里，出现1的，就表示可以用第H1位完成校验，出现数字0则表示不能用H1位进行校验，因此，由上表可知：

校验位H1负责校验：第3，5，7，9，11，13位（上表黄色高亮显示部分），对应位置上的值进行异或得：1⊕0⊕1⊕0⊕1⊕0=1，由于海明校验做的是偶校验，则H1=1；

校验位H2负责校验：第3，6，7，10，11位（上表蓝色高亮显示部分），对应位置上的值进行异或得：1⊕1⊕1⊕1⊕1=1；
校验位H4负责校验：第5，6，7，12，13位，对应位置上的值进行异或得：0⊕1⊕1⊕0⊕0=0；
校验位H8负责校验：第9，10，11，12，13位，对应位置上的值进行异或得：0⊕1⊕1⊕0⊕0=0。

（4）得到最终要传输的数据串为

接收端：

（1）进行校验：

若此时接收方收到的数据相比源数据，在第11位发生了错误：

接收方先按照第③步中类似的方式进行计算校验，区别在于要加上校验位自身这一位，即：

C1的值为第H1，3，5，7，9，11，13位上的值进行异或，计算结果为1

C2的值为第H2，3，6，7，10，11位上的值进行异或，计算结果为1

C4的值为第H4，5，6，7，12，13位上的值进行异或，计算结果为0

C8的值为第H8，9，10，11，12，13位上的值进行异或，计算结果为1

（2）错误位判定：

由于海明校验采取的是偶校验，所以判断出C4监督式包含的数据位无错，错误位发生在C1,C2,C8三个监督式包含的位上。

此时的做法是：①找到C1,C2,C8这三个监督式共同包含的位；②找出共同包含的位之后，再剔除掉在C4中出现过的位（因为已经验证过C4监督式中的位是正确的）；③剩下的位就是发生传输错误的位。

这三个监督式都包含第11位，同时C4监督式中没有第11位，因此出错的位就是第11位。

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

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

例子：

码距：两个合法码字对应位上数字的不同位的个数
上图中，方案一的码距为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. 检错和纠错

六、总结