1.写在前面

在使用编码技术进行差错控制的技术中分为了 ARQ（自动请求重传）和 FEC（前向纠错）。而前向纠错不仅能发现错误还能确定具体的二进制错误位置，因而广泛使用。

前向纠错又可以分为检错编码和纠错编码。检错编码中，常用的是奇偶校验码和循环冗余校验，而纠错编码中，常用的是海明码。

2.奇偶校验码

奇偶校验时校验码中最简单的一种实现手段。它的思想就是，当采用偶（奇）校验的时候，冗余位+原始码流中 1 的个数是偶（奇）数个。

2.1偶校验

当采用偶校验的时候，原始码流中有 3 个 1 了。我需要让总的 1 的个数为偶数个，所以校验位填充 1 。

奇校验的方式相同，就是让 1 的总个数为奇数个。如上图，那么此时校验位就应该填充 0 。

2.2水平垂直奇偶校验

上面的校验码也叫水平校验码。但当我们将水平扩展到二维的时候，我们还可以对列进行校验。

上图采用水平垂直偶校验，可以观察到，列校验和行校验都是保证列和行 1 的个数总数为偶数。

3.循环冗余校验

相比较于奇偶校验，循环冗余校验检错的能力更加强大，当然也相对而言稍稍复杂。

基本思想

1. 循环冗余校验是在原始码流后面加上一串二进制数字，生成新的帧发送出去。
2. 这个二进制的数不是随便加的，它是生成的新的帧同发送方与接收方共同选定的特定的数整除的余数。（这个特定的数，又叫 CRC 生成多项式，作为除数使用）
3. 这里的整除采用的是模2运算，不进位，不借位
4. 收发双方共同约定的特殊的数，这个数可以是随机选取的，也可以是依照国际标准来选取。你可以在维基百科中找到这些标准。
5. 校验码的位数比除数的位数少一个
6. 原始码流作为被除数，CRC 生成多项式作为除数

实际操作

单单是描述思想是很抽象的，下面用一个实例来讲解。

首先我们选取其中一个 CRC 生成国际标准：$G（X） = X^4 + X^3 + 1$G（X）=X4+X3+1
原始码流是 1011 0011 ，下面开始计算最终的包含 CRC 校验的新帧

1. 根据 CRC 生成标准，我们可以推出除数是 11001 ，那么校验码的个数就是 4 个（因为校验码的个数比生成的除数的个数少一个），此时临时校验码就是 0000 ，填充到原始码流，得到 1011 0011 0000
2. 用 1011 0011 0000 除以 11001 得到余数 0100。如下图所示。
   
3. 将余数 0100 （这就是最终的校验码校验码）填充到原始码流的后面，得到 1011 0011 0100

4.海明码（汉明码）

海明码的思想

1. 海明码将原始码流和校验码按照一定的计算方法混合在一起（不像上面的编码，是把校验位放在最后），每一位校验码负责几位信息码（把原始码流分开后形成的一个个数码）的校验。

海明码的计算

现在以 1101 为例。

1. 其中信息码（m）的个数是 4 个，那么假设有 r 个校验码，则需要满足不等式 $2^r>=m+r+1$2r>=m+r+1。由此试算出 r 为 4。所以校验码有 r 个。总的码流是 m+r 个，也就是 8 位数据。

2. 由海明码规定可知，校验位必须以 2 的幂次方排列（如，$第2^0位，第2^1位，第2^2位....$第20位，第21位，第22位....），剩下的位数填充数据位（信息码），如下图。
   
   我们知道信息码是 1101 ，所以数据位依次填入 1101

3. 接下来确定校验码的值。（确定校验位值得方式有几种，这里选择最容易讲解的）

   将数据位有 1 的位置的位数号写成二进制的形式，如下图。
   

4. 把所有二进制数进行异或运算，如上表中，$0011 \bigoplus0101\bigoplus0110\bigoplus0111=$0011⨁0101⨁0110⨁0111=